QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611272#7034. Honeycombucup-team4906#WA 3ms9776kbC++203.0kb2024-10-04 20:09:032024-10-04 20:09:18

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 20:09:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:9776kb
  • [2024-10-04 20:09:03]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define pii pair<int, int>

using namespace std;
const int inf = 1e9;

int n, m, idx = 0;
char a[4010][6010];
int id[1005][1005];
const int N = 1e6 + 10;
vector<int> ed[N];
int dis[N], vst[N];

int s, t;
void init(vector<vector<char>> x, int now, int i, int j) {
    if(x[2][4] == 'S') s = now;
    if(x[2][4] == 'T') t = now;
    if(x[0][3] != '-') { // 上面
        ed[now].push_back(id[i - 1][j]);
    } 
    if(x[4][3] != '-') {
        ed[now].push_back(id[i + 1][j]);
    }
    if(x[1][1] != '/') {
        if(j % 2) ed[now].push_back(id[i - 1][j - 1]);
        else ed[now].push_back(id[i][j - 1]);
    }
    if(x[3][1] != '\\') {
        if(j % 2) ed[now].push_back(id[i][j - 1]);
        else ed[now].push_back(id[i + 1][j - 1]);
    }
    if(x[1][7] != '\\') {
        if(j % 2) ed[now].push_back(id[i - 1][j + 1]);
        else ed[now].push_back(id[i][j + 1]);
    }
    if(x[3][7] != '/') {
        if(j % 2) ed[now].push_back(id[i][j + 1]);
        else ed[now].push_back(id[i + 1][j + 1]);
    }
} 

void sol() {
    cin >> n >> m;
    getchar();
    F(i, 0, 4 * n + 2) {
        string s;
        getline(cin, s);
        int now = 0;
        for(auto x : s) a[i][now ++] = x;  
        for(int j = s.size(); j < 6 * m + 3; j ++) a[i][j] = ' ';
    }
    idx = 0;
    F(i, 1, n) F(j, 1, m) id[i][j] = ++ idx;
    F(i, 1, idx) ed[i].clear();
    F(i, 1, n) F(j, 1, m) {
        vector<vector<char>> now(5);
        int cnt = 0;
        if(j % 2) {
            F(c, 4 * (i - 1), 4 * i) {
                F(r, 6 * (j - 1), 6 * (j - 1) + 8) 
                    now[cnt].push_back(a[c][r]);
                cnt ++;
            }
        } else {
            F(c, 4 * (i - 1) + 2, 4 * i + 2) {
                F(r, 6 * (j - 1), 6 * (j - 1) + 8) 
                    now[cnt].push_back(a[c][r]);
                cnt ++;
            }
        }
        init(now, id[i][j], i, j);
    }
    F(i, 1, idx) dis[i] = inf, vst[i] = 0;
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while(q.size()) {
        auto u = q.front();
        q.pop();
        if(vst[u]) continue;
        vst[u] = 1;
        for(auto v : ed[u]) {
            if(dis[u] + 1 < dis[v]) {
                dis[v] = dis[u] + 1;
                q.push(v);
            } 
        }
    }
    if(dis[t] == inf) cout << "-1\n";
    else cout << dis[t] + 1 << "\n";
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    F(i, 1, t) sol();
    return 0;
}
/*
1
3 4
  +---+       +---+
 /     \     /     \
+       +---+       +---+
 \           \     /     \
  +   +   S   +---+   T   +
 /     \     /           /
+       +---+       +   +
 \           \     /     \
  +---+       +---+       +
 /                       /
+       +---+       +   +
 \                 /     \
  +---+       +---+       +
       \     /     \     /
        +---+       +---+

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 9776kb

input:

1
3 4
  +---+       +---+
 /     \     /     \
+       +---+       +---+
 \           \     /     \
  +   +   S   +---+   T   +
 /     \     /           /
+       +---+       +   +
 \           \     /     \
  +---+       +---+       +
 /                       /
+       +---+       +   +
 \         ...

output:

1

result:

wrong answer 1st lines differ - expected: '7', found: '1'