結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:34:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 3,000 ms |
コード長 | 3,462 bytes |
コンパイル時間 | 1,266 ms |
コンパイル使用メモリ | 118,932 KB |
実行使用メモリ | 13,696 KB |
最終ジャッジ日時 | 2025-07-11 22:34:31 |
合計ジャッジ時間 | 4,102 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:63:9: warning: ‘GX’ may be used uninitialized [-Wmaybe-uninitialized] 63 | int GX, GY; | ^~ main.cpp:63:13: warning: ‘GY’ may be used uninitialized [-Wmaybe-uninitialized] 63 | int GX, GY; | ^~
ソースコード
#include <iostream> #include <iomanip>//小数点出力用 //cout << fixed << setprecision(10) << ans; #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <unordered_map> using ll = long long; using namespace std; #define modPHash (ll)((1LL<<61)-1) #define modP (ll)998244353 bool chkrng0idx(int pos, int sup) { return (0 <= pos && pos < sup); } int clk4(int num) { return (num - 2) * (num % 2); } void yn(bool tf) { cout << (tf ? "Yes\n" : "No\n"); } int P[200000]; int S[200000]; void init() { for (int i = 0;i < 200000;i++) { P[i] = -1; S[i] = 1; } } int find(int x) { if (P[x] == -1) { return x; } else { P[x] = find(P[x]); return P[x]; } } ll unite(int x, int y) { int a = find(x); int b = find(y); if (a != b) { P[b] = a; S[a] += S[b]; return (ll)((ll)(S[a] - S[b]) * (ll)S[b]); } return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int H, W; cin >> H >> W; int M; cin >> M; string F[500]; vector<pair<int, int>>doors(M); vector<pair<int, int>>keys(M); queue<pair<int, pair<int, int>>>Q; int GX, GY; int dist[10][500][500]; for (int i = 0;i < 10;i++)for (int j = 0;j < 500;j++)for (int k = 0;k < 500;k++)dist[i][j][k] = 1e9; for (int i = 0;i < H;i++) { cin >> F[i]; for (int j = 0;j < W;j++) { if (F[i][j] == 'S') { Q.push({ 0,{i,j} }); dist[0][i][j] = 0; } if (F[i][j] == 'G') { GX = i; GY = j; } } } while (!Q.empty()) { int nowK = Q.front().first; int X = Q.front().second.first; int Y = Q.front().second.second; Q.pop(); for (int r = 0;r < 4;r++) { if (chkrng0idx(X + clk4(r), H) && chkrng0idx(Y + clk4(r + 1), W)) { int newK = nowK; if (0 <= F[X + clk4(r)][Y + clk4(r + 1)] - 0x30 && F[X + clk4(r)][Y + clk4(r + 1)] - 0x30 <= 9) { newK = F[X + clk4(r)][Y + clk4(r + 1)] - 0x30; } if (F[X + clk4(r)][Y + clk4(r + 1)] != '#' && dist[newK][X + clk4(r)][Y + clk4(r + 1)] == 1e9) { if (0x30 <= F[X + clk4(r)][Y + clk4(r + 1)] && F[X + clk4(r)][Y + clk4(r + 1)] <= 0x39) { dist[newK][X + clk4(r)][Y + clk4(r + 1)] = dist[nowK][X][Y] + 1; Q.push({ newK,{X + clk4(r), Y + clk4(r + 1)} }); } else if (0x60 <= F[X + clk4(r)][Y + clk4(r + 1)] && F[X + clk4(r)][Y + clk4(r + 1)] <= 0x69) { if (F[X + clk4(r)][Y + clk4(r + 1)] - 0x60 == nowK) { dist[nowK][X + clk4(r)][Y + clk4(r + 1)] = dist[nowK][X][Y] + 1; Q.push({ nowK,{X + clk4(r), Y + clk4(r + 1)} }); } } else { dist[nowK][X + clk4(r)][Y + clk4(r + 1)] = dist[nowK][X][Y] + 1; Q.push({ nowK,{X + clk4(r), Y + clk4(r + 1)} }); } } } } } int ans = 1e9; for (int i = 0;i <= M;i++) { ans = min(ans, dist[i][GX][GY]); } if (ans == 1e9) { ans = -1; } cout << ans; }