結果

問題 No.3428 Palindromic Path (Easy)
コンテスト
ユーザー pengin_2000
提出日時 2026-01-11 14:54:34
言語 C
(gcc 15.2.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,138 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 288 ms
コンパイル使用メモリ 40,712 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 14:54:48
合計ジャッジ時間 750 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
char s[202][202];
long long int dp[202][202][202];
int main()
{
	long long int n;
	scanf("%lld", &n);
	long long int i, j, k;
	for (i = 0; i < n; i++)
		scanf("%s", s[i]);
	for (i = 0; i <= n; i++)
		for (j = 0; j <= n; j++)
			for (k = 0; k <= n; k++)
				dp[i][j][k] = 0;
	const long long int p = 998244353;
	if (s[0][0] == s[n - 1][n - 1])
		dp[0][0][n - 1] = 1;
	int ii, jj;
	for (k = 1; k < n; k++)
	{
		for (i = 0; i < n; i++)
		{
			j = k - i;
			if (j < 0 || j >= n)
				continue;
			for (ii = 0; ii < n; ii++)
			{
				jj = 2 * n - 2 - k - ii;
				if (jj < 0 || jj >= n)
					continue;
				if (s[i][j] != s[ii][jj])
					continue;
				if (i > 0)
				{
					if (ii < n - 1)
						dp[k][i][ii] += dp[k - 1][i - 1][ii + 1];
						if (jj < n - 1)
							dp[k][i][ii] += dp[k - 1][i - 1][ii];
				}
				if (j > 0)
				{
					if (ii < n - 1)
						dp[k][i][ii] += dp[k - 1][i][ii + 1];
					if (jj < n - 1)
						dp[k][i][ii] += dp[k - 1][i][ii];
				}
				dp[k][i][ii] %= p;
			}
		}
	}
	long long int ans = 0;
	for (k = n - 1, i = 0; i < n; i++)
		ans = (ans + dp[k][i][i]) % p;
	printf("%lld\n", ans);
	return 0;
}
0