結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2020-05-30 18:52:09 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,459 bytes |
コンパイル時間 | 1,603 ms |
コンパイル使用メモリ | 173,676 KB |
実行使用メモリ | 17,664 KB |
最終ジャッジ日時 | 2024-11-07 22:44:13 |
合計ジャッジ時間 | 3,157 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:34:16: warning: ‘sy’ may be used uninitialized in this function [-Wmaybe-uninitialized] 34 | dist[sx][sy][0] = 0; | ^ main.cpp:34:12: warning: ‘sx’ may be used uninitialized in this function [-Wmaybe-uninitialized] 34 | dist[sx][sy][0] = 0; | ^ main.cpp:71:46: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized] 71 | int ans = min(dist[gx][gy][0],dist[gx][gy][1]); | ^ main.cpp:71:42: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized] 71 | int ans = min(dist[gx][gy][0],dist[gx][gy][1]); | ^
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2020.05.30 18:52:06 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; int main() { int h,w;cin >> h >> w; vector<string> g(h); int sx,sy,gx,gy; for (int i = 0; i < h; i++) { cin >> g[i]; for (int j = 0; j < w; j++) { if (g[i][j] == 'S') { sx = i; sy = j; } else if (g[i][j] == 'G') { gx = i; gy = j; } } } int k_dx[] = {-2,-1,1,2,2,1,-1,-2},k_dy[] = {1,2,2,1,-1,-2,-2,-1}; int b_dx[] = {-1,1,1,-1}, b_dy[] = {1,1,-1,-1}; constexpr int INF = 1e9 + 6; vector<vector<vector<int>>> dist(h,vector<vector<int>>(w,vector<int>(2,INF))); queue<tuple<int,int,int>> que; que.push(make_tuple(sx,sy,0)); dist[sx][sy][0] = 0; while(!que.empty()) { auto p = que.front(); que.pop(); int nx = get<0>(p); int ny = get<1>(p); int t = get<2>(p); if (t == 0) { for (int k = 0; k < 8; k++) { int x = nx + k_dx[k], y = ny + k_dy[k]; if (x >= 0 && x < h && y >= 0 && y < w) { if (g[x][y] == 'R' && dist[x][y][1] == INF) { dist[x][y][1] = dist[nx][ny][0] + 1; que.push(make_tuple(x,y,1)); } else if (g[x][y] != 'R' && dist[x][y][0] == INF) { dist[x][y][0] = dist[nx][ny][0] + 1; que.push(make_tuple(x,y,0)); } } } } else { for (int k = 0; k < 4; k++) { int x = nx + b_dx[k], y = ny + b_dy[k]; if (x >= 0 && x < h && y >= 0 && y < w) { if (g[x][y] == 'R' && dist[x][y][0] == INF) { dist[x][y][0] = dist[nx][ny][1] + 1; que.push(make_tuple(x,y,0)); } else if (g[x][y] != 'R' && dist[x][y][1] == INF) { dist[x][y][1] = dist[nx][ny][1] + 1; que.push(make_tuple(x,y,1)); } } } } } int ans = min(dist[gx][gy][0],dist[gx][gy][1]); if (ans == INF) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }