結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:07:32 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 117 ms / 3,000 ms |
コード長 | 1,407 bytes |
コンパイル時間 | 850 ms |
コンパイル使用メモリ | 27,904 KB |
実行使用メモリ | 20,480 KB |
最終ジャッジ日時 | 2025-07-11 22:07:56 |
合計ジャッジ時間 | 3,479 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:8:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 8 | scanf("%d %d %d", &h, &w, &m); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:11:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | scanf("%s", s[i]); | ^~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> char s[502][502]; int dp[502][502][10]; int q[3000006], l, r; int main() { int h, w, m; scanf("%d %d %d", &h, &w, &m); int i, j, k; for (i = 0; i < h; i++) scanf("%s", s[i]); m++; for (i = 0; i < h; i++) for (j = 0; j < w; j++) for (k = 0; k < m; k++) dp[i][j][k] = 1e9; l = r = 0; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { if (s[i][j] == 'S') { dp[i][j][0] = 0; q[r] = m * w * i + m * j + 0; r++; } } } int ii, jj, kk; int di[4] = { -1,0,1,0 }; int dj[4] = { 0,-1,0,1 }; int c; while (l < r) { i = q[l]; l++; k = i % m; i /= m; j = i % w; i /= w; for (c = 0; c < 4; c++) { ii = i + di[c]; jj = j + dj[c]; kk = k; if (ii < 0 || jj < 0 || ii >= h || jj >= w) continue; if (s[ii][jj] == '#') continue; if ('1' <= s[ii][jj] && s[ii][jj] <= '9') kk = s[ii][jj] - '0'; if ('a' <= s[ii][jj] && s[ii][jj] <= 'z') { if (s[ii][jj] != 'a' + kk - 1) continue; } if (dp[ii][jj][kk] > dp[i][j][k] + 1) { dp[ii][jj][kk] = dp[i][j][k] + 1; q[r] = m * w * ii + m * jj + kk; r++; } } } int ans = 1e9; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { if (s[i][j] != 'G') continue; for (k = 0; k < m; k++) { if (ans > dp[i][j][k]) ans = dp[i][j][k]; } } } if (ans > 1e7) ans = -1; printf("%d\n", ans); return 0; }