結果
| 問題 |
No.3199 Key-Door Grid
|
| コンテスト | |
| ユーザー |
 SHIN KIMURA
|
| 提出日時 | 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;
}