結果

問題 No.367 ナイトの転身
ユーザー legendcn666
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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;
}
0