結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
|
提出日時 | 2022-04-29 22:53:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 554 ms / 3,000 ms |
コード長 | 2,352 bytes |
コンパイル時間 | 1,865 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 143,684 KB |
最終ジャッジ日時 | 2024-06-29 04:31:37 |
合計ジャッジ時間 | 8,238 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
h,w = map(int, input().split())s = [input() for i in range(h)]if s[0][0] != s[-1][-1]:print(0)exit()n = (h+w)//2dp = [[[0 for k in range(w)]for j in range(w)]for i in range(n)]dp[0][0][w-1] = 1mod = 10**9 + 7for i in range(n-1):for j in range(w):for k in range(w):now = dp[i][j][k]if now == 0:continue#print(i,j,k)ni = i + 1nj = jnk = k - 1nx1 = ni-njny1 = njnx2 = h+w-2-ni-nkny2 = nk#print(nx1,ny1,nx2,ny2)if 0 <= nx1 < h and 0 <= ny1 < w and 0 <= nx2 < h and 0 <= ny2 < w and s[nx1][ny1] == s[nx2][ny2]:dp[ni][nj][nk] += nowdp[ni][nj][nk] %= modni = i + 1nj = jnk = knx1 = ni-njny1 = njnx2 = h+w-2-ni-nkny2 = nkif 0 <= nx1 < h and 0 <= ny1 < w and 0 <= nx2 < h and 0 <= ny2 < w and s[nx1][ny1] == s[nx2][ny2]:dp[ni][nj][nk] += nowdp[ni][nj][nk] %= modni = i + 1nj = j + 1nk = k - 1nx1 = ni-njny1 = njnx2 = h+w-2-ni-nkny2 = nk#print(nx1,ny1,nx2,ny2)if 0 <= nx1 < h and 0 <= ny1 < w and 0 <= nx2 < h and 0 <= ny2 < w and s[nx1][ny1] == s[nx2][ny2]:dp[ni][nj][nk] += nowdp[ni][nj][nk] %= modni = i + 1nj = j + 1nk = knx1 = ni-njny1 = njnx2 = h+w-2-ni-nkny2 = nkif 0 <= nx1 < h and 0 <= ny1 < w and 0 <= nx2 < h and 0 <= ny2 < w and s[nx1][ny1] == s[nx2][ny2]:dp[ni][nj][nk] += nowdp[ni][nj][nk] %= modif (h+w-1)%2:ans = 0for j in range(w):ans += dp[n-1][j][j]ans %= modprint(ans)else:ans = 0ni = n-1for nj in range(w):for nk in range(w):nx1 = ni-njny1 = njnx2 = h+w-2-ni-nkny2 = nkif 0 <= nx1 < h and 0 <= ny1 < w and 0 <= nx2 < h and 0 <= ny2 < w and abs(nx1-nx2)+abs(ny1-ny2)<=1:ans += dp[ni][nj][nk]ans %= modprint(ans)