QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518798 | #7034. Honeycomb | chengning0909 | WA | 577ms | 111216kb | C++14 | 2.8kb | 2024-08-14 11:22:59 | 2024-08-14 11:23:00 |
Judging History
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'