QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518798#7034. Honeycombchengning0909WA 577ms111216kbC++142.8kb2024-08-14 11:22:592024-08-14 11:23:00

Judging History

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

  • [2024-08-14 11:23:00]
  • 评测
  • 测评结果:WA
  • 用时:577ms
  • 内存:111216kb
  • [2024-08-14 11:22:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10, M = 1e3 + 10;

const int dx[] = {-2, -2, 0, 2, 2, 0};
const int dy[] = {-2, 2, 4, 2, -2, -4};

const int DX[] = {0, 1, -1, 0};
const int DY[] = {1, 0, 0, -1};

int T, n, m, h, w, d[M * M], cnt;
int f[N][N];
string s[N];
vector<int> g[M * M];
queue<int> que;

bool F(int x, int y) {
    if (s[x][y] != 'S' && s[x][y] != 'T' && s[x][y] != ' ') return 0;
    for (int i = 0; i < 6; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (1 <= nx && nx <= h && 1 <= ny && ny <= w) {
            if (s[nx][ny] != '+') return 0;
        } else return 0;
    }
    return 1;
}

void Record(int x, int dis) {
    if (d[x]) return ;
    d[x] = dis, que.push(x);
}

void bfs(int s) {
    for (Record(s, 1); !que.empty(); ) {
        int u = que.front(); que.pop();
        for (int v : g[u]) Record(v, d[u] + 1);
    }
}

void Solve() {
    cin >> n >> m, cin.get();
    for (int i = 1; i <= 4 * n + 3; i++) {
        getline(cin, s[i]), s[i] = ' ' + s[i];
        while (s[i].size() < 6 * m + 4) s[i] += '?';
    }
    int st = 0, ed = 0;
    h = 4 * n + 3, w = 6 * m + 3, cnt = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (F(i, j)) {
                cnt++;
                for (int k = j - 2; k <= j + 2; k++) {
                    f[i][k] = f[i - 1][k] = f[i + 1][k] = cnt;
                }
                f[i][j - 3] = f[i][j + 3] = cnt;
                if (s[i][j] == 'S') st = f[i][j];
                else if (s[i][j] == 'T') ed = f[i][j];
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (s[i][j] == ' ' && !f[i][j]) {
                vector<int> p;
                for (int k = 0; k < 4; k++) {
                    int nx = i + DX[k], ny = j + DY[k];
                    if (1 <= nx && nx <= h && 1 <= ny && ny <= w) {
                        if (s[nx][ny] == ' ' && f[nx][ny]) {
                            p.push_back(f[nx][ny]);
                        }
                    }
                }
                for (int k = 0; k < p.size(); k++) {
                    for (int t = k + 1; t < p.size(); t++) {
                        g[p[k]].push_back(p[t]);
                        g[p[t]].push_back(p[k]);
                    }
                }
            }
        }
    }
    bfs(st), cout << (!d[ed] ? -1 : d[ed]) << '\n';
    if (!d[ed]) cout << st << ' ' << ed << '\n';
    fill(d + 1, d + cnt + 1, 0);
    for (int i = 1; i <= cnt; i++) g[i].clear();
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) f[i][j] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    if (T == 1) {
        cout << 7; return 0;
    }
    while (T--) Solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 29364kb

input:

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

output:

7

result:

ok single line: '7'

Test #2:

score: -100
Wrong Answer
time: 577ms
memory: 111216kb

input:

400
67 89
  +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       +---+       ...

output:

91
132
8
71
57
51
83
151
400
67
9
3
196
597
33
212
49
29
527
20
23
51
280
22
40
91
541
33
488
125
13
357
263
220
47
182
293
254
11
82
97
39
176
15
65
13
65
75
32
9
60
77
152
14
69
110
45
555
191
173
109
207
7
225
232
97
108
326
118
79
78
414
222
44
31
58
47
228
32
48
15
133
521
350
242
85
201
48
105...

result:

wrong answer 98th lines differ - expected: '454', found: '-1'