結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-02-22 01:32:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 781 ms / 3,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,640 KB |
実行使用メモリ | 144,564 KB |
最終ジャッジ日時 | 2024-06-30 08:52:53 |
合計ジャッジ時間 | 14,351 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
mod=10**9+7h,w=map(int,input().split())s=[]for i in range(h):s.append(list(input()))dp=[[[0]*h for i in range(w)] for j in range(h)]if (h+w)%2==0:for i1 in range(h):j1=(h+w-2)//2-i1if 0<=j1<w:dp[i1][j1][i1]=1else:for i1 in range(h):j1=(h+w-3)//2-i1if 0<=j1<w:for i2,j2 in [(i1+1,j1),(i1,j1+1)]:if 0<=i2<h and 0<=j2<w and s[i1][j1]==s[i2][j2]:dp[i1][j1][i2]=1for m in range((h+w-2)//2,0,-1):for i1 in range(h):j1=m-i1if 0<=j1<w:for i2 in range(h):j2=h+w-2-m-i2if 0<=j2<w:for ni1,nj1,ni2,nj2 in ((i1-1,j1,i2+1,j2),(i1,j1-1,i2+1,j2),(i1-1,j1,i2,j2+1),(i1,j1-1,i2,j2+1)):if 0<=ni1<h and 0<=nj1<w and 0<=ni2<h and 0<=nj2<w and s[ni1][nj1]==s[ni2][nj2]:dp[ni1][nj1][ni2]+=dp[i1][j1][i2]dp[ni1][nj1][ni2]%=modprint(dp[0][0][h-1])