結果
問題 |
No.367 ナイトの転身
|
ユーザー |
|
提出日時 | 2024-08-18 17:09:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,093 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 173,524 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-18 17:09:12 |
合計ジャッジ時間 | 3,067 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
# include <bits/stdc++.h> using namespace std; typedef long long ll; // # define int long long # define lc u << 1 # define rc u << 1 | 1 # define fi first # define se second const int N = 505; int n, m; char mp[N][N]; struct node { int x, y, op; }; int dis[N][N][2]; int dx1[8] = {1, 2, 1, 2, -1, -2, -1, -2}, dy1[8] = {2, 1, -2, -1, 2, 1, -2, -1}; int dx2[4] = {1, 1, -1, -1}, dy2[4] = {1, -1, 1, -1}; queue <node> q; signed main () { scanf ("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) scanf (" %c", &mp[i][j]); } int sx = 0, sy = 0, ex = 0, ey = 0; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { if (mp[i][j] == 'S') sx = i, sy = j; else if (mp[i][j] == 'G') ex = i, ey = j; } } memset (dis, 0x3f, sizeof dis); dis[sx][sy][0] = 0; q.push ({sx, sy, 0}); while (!q.empty ()) { int x = q.front ().x, y = q.front ().y, op = q.front ().op; q.pop (); if (op == 0) { for (int i = 0; i < 8; i ++ ) { int nx = x + dx1[i], ny = y + dy1[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; int nop = op ^ (mp[nx][ny] == 'R'); if (dis[nx][ny][nop] > dis[x][y][op] + 1) { dis[nx][ny][nop] = dis[x][y][op] + 1; q.push ({nx, ny, nop}); } } } else { for (int i = 0; i < 4; i ++ ) { int nx = x + dx2[i], ny = y + dy2[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; int nop = op ^ (mp[nx][ny] == 'R'); if (dis[nx][ny][nop] > dis[x][y][op] + 1) { dis[nx][ny][nop] = dis[x][y][op] + 1; q.push ({nx, ny, nop}); } } } } int ans = min (dis[ex][ey][0], dis[ex][ey][1]); if (ans == 0x3f3f3f3f) ans = -1; printf ("%d\n", ans); return 0; }