結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー pengin_2000
提出日時 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]);
      |                 ^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0