結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー pengin_2000
提出日時 2025-03-21 22:41:20
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 558 ms / 6,000 ms
コード長 1,262 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 200 ms
コンパイル使用メモリ 41,068 KB
最終ジャッジ日時 2026-02-22 13:22:30
ジャッジサーバーID
（参考情報） 		judge2 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
char s[402][402];
long long int dp1[402][402], dp2[402][402];
int main()
{
	long long int h, w;
	scanf("%lld %lld", &h, &w);
	long long int i, j, k;
	for (i = 0; i < h; i++)
		scanf("%s", s[i]);
	for (j = 0; j <= w; j++)
		s[i][j] = '#';
	const long long int p = 998244353;
	for (i = 0; i < h; i++)
		for (j = 0; j < h; j++)
			dp1[i][j] = dp2[i][j] = 0;
	dp1[1][0] = 1;
	for (k = 2; k < h + w - 1; k++)
	{
		for (i = 0; i < h; i++)
			for (j = 0; j < h; j++)
				dp2[i][j] = 0;
		for (i = 0; i < h; i++)
		{
			if (k - i < 0 || k - i > w)
				continue;
			for (j = 0; j < h; j++)
			{
				if (k - j < 0 || k - j > w)
					continue;
				if (i == j)
					continue;
				if (i < h - 1 && s[i + 1][k - i - 1] == '.')
				{
					if (j < h - 1 && s[j + 1][k - j - 1] == '.')
						dp2[i + 1][j + 1] += dp1[i][j];
					if (k - j < w && s[j][k - j] == '.')
						dp2[i + 1][j] += dp1[i][j];
				}
				if (k - i < w && s[i][k - i] == '.')
				{
					if (j < h - 1 && s[j + 1][k - j - 1] == '.')
						dp2[i][j + 1] += dp1[i][j];
					if (k - j < w && s[j][k - j] == '.')
						dp2[i][j] += dp1[i][j];
				}
			}
		}
		for (i = 0; i < h; i++)
			for (j = 0; j < h; j++)
				dp1[i][j] = dp2[i][j] % p;
	}
	printf("%lld\n", dp1[h - 1][h - 1]);
	return 0;
}
0