結果
問題 |
No.367 ナイトの転身
|
ユーザー |
|
提出日時 | 2021-07-18 03:32:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 2,503 bytes |
コンパイル時間 | 2,036 ms |
コンパイル使用メモリ | 200,716 KB |
最終ジャッジ日時 | 2025-01-23 03:06:24 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; int H, W; int dist[501][501][2]; char board[501][501]; int dy0[8] = { -1,-2,-2,-1,1,2,2,1 }; int dx0[8] = { -2,-1,1,2,2,1,-1,-2 }; int dy1[4] = { -1,-1,1,1 }; int dx1[4] = { -1,1,1,-1 }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); int gy = -1; int gx = -1; int sy = -1; int sx = -1; cin >> H >> W; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> board[i][j]; if (board[i][j] == 'S') { sy = i; sx = j; } else if (board[i][j] == 'G') { gy = i; gx = j; } } } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { dist[i][j][0] = 1e9; dist[i][j][1] = 1e9; } } dist[sy][sx][0] = 0; priority_queue <pair<int, pair<pair<int, int>, int>>,vector<pair<int, pair<pair<int, int>, int>>>,greater<pair<int, pair<pair<int, int>, int>>>> pque; pque.push(make_pair(dist[sy][sx][0], make_pair(make_pair(sy, sx), 0))); while (!pque.empty()) { int y = pque.top().second.first.first; int x = pque.top().second.first.second; int t = pque.top().second.second; if (dist[y][x][t] < pque.top().first) { pque.pop(); continue; } pque.pop(); if (t == 0) { for (int k = 0; k < 8; k++) { int ny = y + dy0[k]; int nx = x + dx0[k]; if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue; if (board[ny][nx] == 'R') { if (dist[ny][nx][1] > dist[y][x][0] + 1) { dist[ny][nx][1] = dist[y][x][0] + 1; pque.push(make_pair(dist[ny][nx][1], make_pair(make_pair(ny, nx), 1))); } } else { if (dist[ny][nx][0] > dist[y][x][0] + 1) { dist[ny][nx][0] = dist[y][x][0] + 1; pque.push(make_pair(dist[ny][nx][0], make_pair(make_pair(ny, nx), 0))); } } } } else { for (int k = 0; k < 4; k++) { int ny = y + dy1[k]; int nx = x + dx1[k]; if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue; if (board[ny][nx] == 'R') { if (dist[ny][nx][0] > dist[y][x][1] + 1) { dist[ny][nx][0] = dist[y][x][1] + 1; pque.push(make_pair(dist[ny][nx][0], make_pair(make_pair(ny, nx), 0))); } } else { if (dist[ny][nx][1] > dist[y][x][1] + 1) { dist[ny][nx][1] = dist[y][x][1] + 1; pque.push(make_pair(dist[ny][nx][1], make_pair(make_pair(ny, nx), 1))); } } } } } int res = min(dist[gy][gx][0], dist[gy][gx][1]); if (res >= 1e9) res = -1; cout << res << '\n'; return 0; }