結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-12 11:05:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 3,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 840 ms |
コンパイル使用メモリ | 63,484 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2025-07-12 11:05:35 |
合計ジャッジ時間 | 3,100 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:36:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf("%d%d%d", &h, &w, &m); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:38:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | for (int i = 0; i < h; i++) scanf("%s", fs + i * w); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3199.cc: No.3199 Key-Door Grid - yukicoder */ #include<cstdio> #include<queue> #include<algorithm> using namespace std; /* constant */ const int MAX_H = 500; const int MAX_W = 500; const int MAX_M = 9; const int MAX_HW = MAX_H * MAX_W; const int MAX_GN = MAX_HW * (MAX_M + 1); const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 }; /* typedef */ using qi = queue<int>; /* global variables */ char fs[MAX_HW + 4]; int ds[MAX_GN]; /* subroutines */ /* main */ int main() { int h, w, m; scanf("%d%d%d", &h, &w, &m); int hw = h * w; m++; for (int i = 0; i < h; i++) scanf("%s", fs + i * w); int st = -1, gl = -1; for (int i = 0; i < hw; i++) { if (fs[i] == 'S') st = i; else if (fs[i] == 'G') gl = i; } //printf(" st=%d, gl=%d\n", st, gl); int gn = hw * m; fill(ds, ds + gn, -1); ds[st * m] = 0; qi q; q.push(st * m); int gd = -1; while (! q.empty()) { auto u = q.front(); q.pop(); int up = u / m, uk = u % m; int uy = up / w, ux = up % w; //printf(" %d,%d,%d\n", uy, ux, uk); if (up == gl) { gd = ds[u]; break; } for (int di = 0; di < 4; di++) { int vy = uy + dys[di], vx = ux + dxs[di], vp = vy * w + vx; if (vy >= 0 && vy < h && vx >= 0 && vx < w && fs[vp] != '#') { if (fs[vp] >= 'a' && fs[vp] <= 'i' && fs[vp] - 'a' + 1 != uk) continue; int vk = (fs[vp] >= '1' && fs[vp] <= '9') ? fs[vp] - '0' : uk; int v = vp * m + vk; if (ds[v] < 0) ds[v] = ds[u] + 1, q.push(v); } } } printf("%d\n", gd); return 0; }