結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 23:19:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,553 bytes |
コンパイル時間 | 1,679 ms |
コンパイル使用メモリ | 138,660 KB |
実行使用メモリ | 16,072 KB |
最終ジャッジ日時 | 2025-07-11 23:19:49 |
合計ジャッジ時間 | 6,375 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | TLE * 1 -- * 36 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:175:15: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized] 175 | visited[sx][sy] = true; | ^ main.cpp:164:9: note: ‘sx’ was declared here 164 | int sx, sy, gx, gy; | ^~ In file included from /usr/include/c++/13/vector:67, from main.cpp:4: In member function ‘std::vector<bool, _Alloc>::reference std::vector<bool, _Alloc>::operator[](size_type) [with _Alloc = std::allocator<bool>]’, inlined from ‘int main()’ at main.cpp:175:19: /usr/include/c++/13/bits/stl_bvector.h:1087:23: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized] 1087 | { return begin()[__n]; } | ~~~~~~~^ main.cpp: In function ‘int main()’: main.cpp:164:13: note: ‘sy’ was declared here 164 | int sx, sy, gx, gy; | ^~ main.cpp:171:19: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized] 171 | que.push({ gx * W + gy,0 }); | ~~~^~~ main.cpp:164:17: note: ‘gx’ was declared here 164 | int sx, sy, gx, gy; | ^~ main.cpp:171:23: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized] 171 | que.push({ gx * W + gy,0 }); | ~~~~~~~^~~~ main.cpp:164:21: note: ‘gy’ was declared here 164 | int sx, sy, gx, gy; | ^~
ソースコード
//#define _GLIBCXX_DEBUG #include <iostream> #include <vector> #include <queue> #include <climits> #include <algorithm> #include <map> #include <set> #include <iterator> #include <unordered_map> #include <stack> #include <string> #include <cmath> #include <iomanip> #include <deque> #include <unordered_set> #include <locale> using namespace std; using ll = long long; const ll MOD = 998244353; const ll MOD2 = 1'000'000'007; class SegTree { public: vector<ll> dat; ll siz = 1; SegTree(ll n) { while (siz < n) siz *= 2; dat.resize(2 * siz, -LLONG_MAX); } void update(int id, ll x) { id += siz; dat[id] = x; while (id != 0) { id /= 2; dat[id] = max(dat[2 * id], dat[2 * id + 1]); } } ll getval(int id) { return dat[id + siz]; } ll getmax(ll L, ll R, ll a, ll b, ll u) { if (b <= L || R <= a) return -LLONG_MAX / 2; if (L <= a && b <= R) return dat[u]; ll m = (a + b) / 2; return max(getmax(L, R, a, m, 2 * u), getmax(L, R, m, b, 2 * u + 1)); } }; class UnionFind { public: vector<int> siz, par; UnionFind(int n) { siz.assign(n, 1); par.assign(n, -1); } int root(int x) { return par[x] == -1 ? x : par[x] = root(par[x]); } void unite(int x, int y) { int rx = root(x), ry = root(y); if (rx == ry) return; if (siz[rx] < siz[ry]) { par[rx] = ry; siz[ry] += siz[rx]; } else { par[ry] = rx; siz[rx] += siz[ry]; } } bool same(int x, int y) { return root(x) == root(y); } }; long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 }; //ios::sync_with_stdio(false); //cin.tie(nullptr); int H, W, M; ll add_cost(vector<string> S, int sx, int sy, int gx, int gy) { for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)if (S[i][j] != '.')S[i][j] = '#'; queue<pair<int, int>> que; vector<vector<bool>> visited(H, vector<bool>(W, false)); que.push({ sx * W + sy,0 }); visited[sx][sy] = true; while (!que.empty()) { int u = que.front().first, cost = que.front().second; int x = u / W, y = u % W; que.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx == gx && ny == gy)return cost + 1; if (nx < 0 || nx >= H || ny < 0 || W <= ny)continue; if (S[nx][ny] == '#' || visited[nx][ny])continue; visited[nx][ny] = true; que.push({ nx * W + ny,cost + 1 }); } } return LLONG_MAX / 4;//たどり着けなかったらめっちゃ増やしとく } int main() { //ゴールからスタートしてBFSでゴールを目指す //途中で扉に引っかかったら //扉から対応する鍵まで行く道の最短経路+スタートから鍵までの最短距離 を計算する cin >> H >> W >> M; vector<string> S(H); for (int i = 0; i < H; i++)cin >> S[i]; map<char, int> keyx, keyy; for (int i = 1; i <= 9; i++) { keyx[i] = -1, keyy[i] = -1; } for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) { if (!('1' <= S[i][j] && S[i][j] <= '9'))continue; keyx[S[i][j] - '1' + 'a'] = i, keyy[S[i][j] - '1' + 'a'] = j; } int sx, sy, gx, gy; for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) { if (S[i][j] == 'S')sx = i, sy = j; if (S[i][j] == 'G')gx = i, gy = j; } queue<pair<int, int>> que; que.push({ gx * W + gy,0 }); ll ans = LLONG_MAX / 2; vector<vector<bool>> visited(H, vector<bool>(W, false)); visited[sx][sy] = true; while (!que.empty()) { int u = que.front().first; ll cost = que.front().second; int x = u / W, y = u % W; que.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (nx < 0 || H <= nx || ny < 0 || W <= ny)continue;//範囲外ならやめる if (S[nx][ny] == 'S') {//ゴール着いたら出力する cout << min(ans, cost + 1) << endl; return 0; } if (S[nx][ny] == '#')continue; if (visited[nx][ny])continue; visited[nx][ny] = true; if (islower(S[nx][ny])) {//扉に来たら ll C = cost + 1; //cout << cost << endl; //cout << "check:" << add_cost(S, nx, ny, keyx[S[nx][ny]], keyy[S[nx][ny]]) << " " << add_cost(S, keyx[S[nx][ny]], keyy[S[nx][ny]], sx, sy) << endl; C += add_cost(S, nx, ny, keyx[S[nx][ny]], keyy[S[nx][ny]]) + add_cost(S, keyx[S[nx][ny]], keyy[S[nx][ny]], sx, sy); ans = min(ans, C); continue;//queにはくわえずそのままスルー } //扉以外(道か鍵)のマスに来た時 que.push({ nx * W + ny,cost + 1 }); } } cout << (ans < LLONG_MAX / 8 ? ans : -1) << endl; }