結果

問題 No.1916 Making Palindrome on Gird
コンテスト
ユーザー SidewaysOwl
提出日時 2022-04-29 23:51:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,770 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 89,448 KB
最終ジャッジ日時 2024-06-29 05:41:42
合計ジャッジ時間 5,980 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 8 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
from collections import defaultdict
l = []
for i in range(h):
    for j in range(w):
        if (h+w-1) & 1 and i + j == (h+w-1)//2:
            l.append(((i,j),(i,j)))
        if (h+w) & 1 and i + j == (h+w-1)//2-1:
            if j + 1 <= w-1:
                l.append(((i,j),(i,j+1)))
            if i + 1 <= h-1:
                l.append(((i,j),(i+1,j)))
if (h+w-1):
    nn = (h+w-1)//2
else:
    nn = (h+w-1)//2-1
ans = 0
mod = 10**9 + 7
for L,r in l:
    if s[0][0] != s[h-1][w-1]:break
    l_i , l_j = L
    r_i , r_j = r
    dp1 = [[0]*(l_j+1) for _ in range(l_i+1)]
    dp2 = [[0]*(w - r_j) for _ in range(h-r_i)]
    dp1[0][0] = 1
    dp2[0][0] = 1
#     print(dp1,dp2)
    for i in range(1,nn+1):
        hoge = []
        for x in range(i+1):
            y = i-x
            hoge.append((x,y))
        
        for x,y in hoge:
            for xx,yy in hoge:
                if 0 <= x <= l_i and 0 <= y <= l_j:
#                     print(x,y,h-xx,w - yy)
                    if r_i <= h-xx-1 <= h-1 and r_j <= w - yy-1 <= w-1:
                        if s[x][y] == s[h-xx-1][w-yy-1]:
                            if dp1[x][y] == 0:
                                flg = False
                                if r_i <= h-xx <= h-1 and r_j <= w - yy-1 <= w-1:
                                    flg|= dp2[xx-1][yy] > 0
                                if r_i <= h-xx-1  <= h-1 and r_j <= w - yy  <= w-1:
                                    flg|= dp2[xx][yy-1] > 0
                                if flg:
                                    if 0 <= x-1 <= l_i and 0 <= y <= l_j:
                                        dp1[x][y] += dp1[x-1][y]
                                    if 0 <= x <= l_i and 0 <= y-1 <= l_j:
                                        dp1[x][y] += dp1[x][y-1]
                            if dp2[xx][yy] == 0:
                                flg = False
                                if 0 <= x-1 <= l_i and 0 <= y <= l_j:
                                    flg|= dp1[x-1][y] > 0
                                if 0 <= x <= l_i and 0 <= y-1 <= l_j:
                                    flg|= dp1[x][y-1] > 0
                                
                                if flg:
                                    if r_i <= h-xx <= h-1 and r_j <= w - yy-1 <= w-1:
                                        dp2[xx][yy] += dp2[xx-1][yy]
                                    if r_i <= h-xx-1  <= h-1 and r_j <= w - yy  <= w-1:
                                        dp2[xx][yy] += dp2[xx][yy-1]
                            dp1[x][y] %= mod
                            dp2[xx][yy] %= mod
#     print(dp1,dp2)
    ans += dp1[-1][-1] * dp2[-1][-1]
    ans %= mod
print(ans)
0