結果
| 問題 | No.367 ナイトの転身 |
| ユーザー |
 xuzijian629
|
| 提出日時 | 2018-11-05 20:09:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 66 ms / 2,000 ms |
| コード長 | 4,192 bytes |
| コンパイル時間 | 2,332 ms |
| コンパイル使用メモリ | 204,996 KB |
| 最終ジャッジ日時 | 2025-01-06 15:35:42 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,820 KB |
| testcase_04 | AC | 2 ms
6,816 KB |
| testcase_05 | AC | 2 ms
6,820 KB |
| testcase_06 | AC | 2 ms
6,820 KB |
| testcase_07 | AC | 1 ms
6,820 KB |
| testcase_08 | AC | 2 ms
6,820 KB |
| testcase_09 | AC | 2 ms
6,820 KB |
| testcase_10 | AC | 35 ms
9,728 KB |
| testcase_11 | AC | 47 ms
9,600 KB |
| testcase_12 | AC | 66 ms
6,824 KB |
| testcase_13 | AC | 19 ms
6,820 KB |
| testcase_14 | AC | 26 ms
6,824 KB |
| testcase_15 | AC | 3 ms
6,820 KB |
| testcase_16 | AC | 25 ms
6,816 KB |
| testcase_17 | AC | 5 ms
6,820 KB |
| testcase_18 | AC | 6 ms
6,820 KB |
| testcase_19 | AC | 8 ms
6,820 KB |
| testcase_20 | AC | 4 ms
6,816 KB |
| testcase_21 | AC | 11 ms
6,816 KB |
| testcase_22 | AC | 2 ms
6,816 KB |
| testcase_23 | AC | 3 ms
6,820 KB |
| testcase_24 | AC | 2 ms
6,820 KB |
| testcase_25 | AC | 3 ms
6,820 KB |
| testcase_26 | AC | 2 ms
6,816 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
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;
| ^~
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;
| ^~
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from main.cpp:1:
In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = std::pair<int, int>; _U2 = int; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = std::pair<int, int>; _T2 = int]’,
inlined from ‘int main()’ at main.cpp:30:14:
/usr/include/c++/13/bits/stl_pair.h:688:11: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
688 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y))
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:11:9: note: ‘sx’ was declared here
11 | int sx, sy, gx, gy;
| ^~
In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = std::pair<int, int>; _U2 = int; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = std::pair<int, int>; _T2 = int]’,
i
ソースコード
#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;
}