結果
| 問題 | No.367 ナイトの転身 |
| ユーザー |
 xuzijian629
|
| 提出日時 | 2018-11-05 20:09:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 43 ms / 2,000 ms |
| コード長 | 4,192 bytes |
| コンパイル時間 | 2,458 ms |
| コンパイル使用メモリ | 213,488 KB |
| 実行使用メモリ | 9,472 KB |
| 最終ジャッジ日時 | 2024-04-30 22:04:34 |
| 合計ジャッジ時間 | 3,929 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,940 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,944 KB |
| testcase_08 | AC | 2 ms
6,944 KB |
| testcase_09 | AC | 1 ms
6,944 KB |
| testcase_10 | AC | 36 ms
9,472 KB |
| testcase_11 | AC | 43 ms
9,472 KB |
| testcase_12 | AC | 27 ms
6,940 KB |
| testcase_13 | AC | 19 ms
6,944 KB |
| testcase_14 | AC | 23 ms
6,940 KB |
| testcase_15 | AC | 3 ms
6,940 KB |
| testcase_16 | AC | 24 ms
6,940 KB |
| testcase_17 | AC | 5 ms
6,940 KB |
| testcase_18 | AC | 6 ms
6,940 KB |
| testcase_19 | AC | 7 ms
6,944 KB |
| testcase_20 | AC | 4 ms
6,940 KB |
| testcase_21 | AC | 9 ms
6,944 KB |
| testcase_22 | AC | 2 ms
6,940 KB |
| testcase_23 | AC | 2 ms
6,940 KB |
| testcase_24 | AC | 2 ms
6,940 KB |
| testcase_25 | AC | 2 ms
6,940 KB |
| testcase_26 | AC | 2 ms
6,940 KB |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:31:16: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
31 | nowk[sx][sy] = 0;
| ^
main.cpp:11:13: note: 'sy' was declared here
11 | int sx, sy, gx, gy;
| ^~
main.cpp:31:12: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
31 | nowk[sx][sy] = 0;
| ^
main.cpp:11:9: note: 'sx' was declared here
11 | int sx, sy, gx, gy;
| ^~
main.cpp:119:42: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
119 | i64 k = min(nowk[gx][gy], nowb[gx][gy]);
| ^
main.cpp:11:21: note: 'gy' was declared here
11 | int sx, sy, gx, gy;
| ^~
main.cpp:119:38: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
119 | i64 k = min(nowk[gx][gy], nowb[gx][gy]);
| ^
main.cpp:11:17: note: 'gx' was declared here
11 | int sx, sy, gx, gy;
| ^~
ソースコード
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
int main() {
int h, w;
cin >> h >> w;
vvi b(h, vi(w));
int sx, sy, gx, gy;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
char c;
cin >> c;
if (c == 'S') {
sx = i, sy = j;
} else if (c == 'G') {
gx = i, gy = j;
} else if (c == 'R') {
b[i][j] = 1;
}
}
}
using ii = pair<int, int>;
using iii = pair<ii, int>;
vvi nowk(h, vi(w, 1e18)), nowb(h, vi(w, 1e18));
queue<iii> que;
que.push(iii(ii(sx, sy), 0));
nowk[sx][sy] = 0;
int dxk[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dyk[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dxb[] = {1, 1, -1, -1};
int dyb[] = {-1, 1, -1, 1};
auto ok = [&](int i, int j) {
return 0 <= i && i < h && 0 <= j && j < w;
};
while (que.size()) {
iii t = que.front();
int x = t.first.first;
int y = t.first.second;
que.pop();
if (t.second == 0) {
for (int i = 0; i < 8; i++) {
int xx = x + dxk[i];
int yy = y + dyk[i];
if (ok(xx, yy)) {
if (b[xx][yy]) {
if (t.second == 0) {
int p = nowk[x][y] + 1;
if (p < nowb[xx][yy]) {
nowb[xx][yy] = p;
que.push(iii(ii(xx, yy), 1));
}
} else {
int p = nowb[x][y] + 1;
if (p < nowk[xx][yy]) {
nowk[xx][yy] = p;
que.push(iii(ii(xx, yy), 0));
}
}
} else {
if (t.second == 0) {
int p = nowk[x][y] + 1;
if (p < nowk[xx][yy]) {
nowk[xx][yy] = p;
que.push(iii(ii(xx, yy), 0));
}
} else {
int p = nowb[x][y] + 1;
if (p < nowb[xx][yy]) {
nowb[xx][yy] = p;
que.push(iii(ii(xx, yy), 1));
}
}
}
}
}
} else {
for (int i = 0; i < 4; i++) {
int xx = x + dxb[i];
int yy = y + dyb[i];
if (ok(xx, yy)) {
if (b[xx][yy]) {
if (t.second == 0) {
int p = nowk[x][y] + 1;
if (p < nowb[xx][yy]) {
nowb[xx][yy] = p;
que.push(iii(ii(xx, yy), 1));
}
} else {
int p = nowb[x][y] + 1;
if (p < nowk[xx][yy]) {
nowk[xx][yy] = p;
que.push(iii(ii(xx, yy), 0));
}
}
} else {
if (t.second == 0) {
int p = nowk[x][y] + 1;
if (p < nowk[xx][yy]) {
nowk[xx][yy] = p;
que.push(iii(ii(xx, yy), 0));
}
} else {
int p = nowb[x][y] + 1;
if (p < nowb[xx][yy]) {
nowb[xx][yy] = p;
que.push(iii(ii(xx, yy), 1));
}
}
}
}
}
}
}
i64 k = min(nowk[gx][gy], nowb[gx][gy]);
cout << (k == 1e18 ? -1 : k) << endl;
}