結果
問題 | No.367 ナイトの転身 |
ユーザー |
|
提出日時 | 2016-04-29 22:47:22 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,153 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 171,892 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-10-04 18:24:24 |
合計ジャッジ時間 | 2,129 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:49:27: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized] 49 | if (dist[gy][gx][1] == -1) dist[gy][gx][1] = 1e9; | ~~~~~~~~~~~~~~^ main.cpp:49:27: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]
ソースコード
#include <bits/stdc++.h> using namespace std; string g[500]; int dist[500][500][2]; vector<int> dy[2] = { {1, 2, 2, 1, -1, -2, -2, -1}, {1, 1, -1, -1}, }; vector<int> dx[2] = { {2, 1, -1, -2, -2, -1, 1, 2}, {1, -1, -1, 1}, }; int main() { int h, w; int sy, sx, gy, gx; cin >> h >> w; for (int i = 0; i < h; i++) { cin >> g[i]; for (int j = 0; j < w; j++) { if (g[i][j] == 'S') sy = i, sx = j; if (g[i][j] == 'G') gy = i, gx = j; } } memset(dist, -1, sizeof(dist)); dist[sy][sx][0] = 0; queue<tuple<int, int, int>> q; q.emplace(sy, sx, 0); while (!q.empty()) { int y, x, t; tie(y, x, t) = q.front(); q.pop(); for (int k = 0; k < dy[t].size(); k++) { int ny = y + dy[t][k]; int nx = x + dx[t][k]; if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue; int nt = g[ny][nx] == 'R' ? !t : t; if (dist[ny][nx][nt] != -1) continue; dist[ny][nx][nt] = dist[y][x][t] + 1; q.emplace(ny, nx, nt); } } if (dist[gy][gx][0] == -1) dist[gy][gx][0] = 1e9; if (dist[gy][gx][1] == -1) dist[gy][gx][1] = 1e9; int ans = min(dist[gy][gx][0], dist[gy][gx][1]); if (ans == 1e9) ans = -1; cout << ans << endl; }