結果

問題 No.3504 Insert Maze
コンテスト
ユーザー pengin_2000
提出日時 2026-04-24 11:33:14
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,627 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 743 ms
コンパイル使用メモリ 40,520 KB
実行使用メモリ 52,912 KB
最終ジャッジ日時 2026-04-24 11:33:27
合計ジャッジ時間 10,907 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 81 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
char s[2003][2003];
int dist[2][2003][2003];
int q[4000006], left, right;
int main()
{
	int h, w;
	scanf("%d %d", &h, &w);
	int i, j;
	for (i = 0; i < h; i++)
		scanf("%s", s[i]);
	for (i = 0; i < h; i++)
		for (j = 0; j < w; j++)
			dist[0][i][j] = dist[1][i][j] = 1e9;
	int k, ii, jj;
	int di[4] = { -1,0,1,0 };
	int dj[4] = { 0,-1,0,1 };
	dist[0][0][0] = 0;
	left = right = 0;
	q[right++] = 0;
	while (left < right)
	{
		i = q[left++];
		j = i % w;
		i /= w;
		for (k = 0; k < 4; k++)
		{
			ii = i + di[k];
			jj = j + dj[k];
			if (ii < 0 || jj < 0 || ii >= h || jj >= w)
				continue;
			if (s[ii][jj] == '#')
				continue;
			if (dist[0][ii][jj] > dist[0][i][j] + 1)
			{
				dist[0][ii][jj] = dist[0][i][j] + 1;
				q[right++] = w * ii + jj;
			}
		}
	}
	dist[1][h - 1][w - 1] = 0;
	left = right = 0;
	q[right++] = h * w - 1;
	while (left < right)
	{
		i = q[left++];
		j = i % w;
		i /= w;
		for (k = 0; k < 4; k++)
		{
			ii = i + di[k];
			jj = j + dj[k];
			if (ii < 0 || jj < 0 || ii >= h || jj >= w)
				continue;
			if (s[ii][jj] == '#')
				continue;
			if (dist[1][ii][jj] > dist[1][i][j] + 1)
			{
				dist[1][ii][jj] = dist[1][i][j] + 1;
				q[right++] = w * ii + jj;
			}
		}
	}
	if (dist[0][h - 1][w - 1] == h + w - 2)
	{
		printf("%d\n", h + w - 2);
		return 0;
	}
	int f1, f2;
	for (i = 0; i < h - 1;)
	{
		f1 = f2 = 0;
		for (j = 0; j < w; j++)
			if (dist[0][i][j] == i + j)
				f1++;
		i++;
		for (j = 0; j < w; j++)
			if (dist[1][i][j] == h - i - 1 + w - j - 1)
				f2++;
		if (f1 * f2 > 0)
		{
			printf("%d\n", h + w - 1);
			return 0;
		}
	}
	printf("%d\n", h + w);
	return 0;
}
0