結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー hato336
提出日時 2025-03-21 22:40:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,711 bytes
コンパイル時間 546 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 89,856 KB
最終ジャッジ日時 2025-03-21 22:40:50
合計ジャッジ時間 9,584 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random
#sys.setrecursionlimit(10**9)
#sys.set_int_max_str_digits(0)
#input = sys.stdin.readline
#n = int(input())
#alist = list(map(int,input().split()))
#alist = []
#s = input()
h,w = map(int,input().split())
s = [list(input().rstrip()) for i in range(h)]
mod = 998244353
#for i in range(n):
#    alist.append(list(map(int,input().split())))
cnt = [0 for i in range(h+w-2+1)]
v = [[] for i in range(h+w-2+1)]
for i in range(h):
    for j in range(w):
        cnt[i+j] += 1
        v[i+j].append((i,j))
dp = [[[0 for k in range(cnt[i])] for j in range(cnt[i])] for i in range(len(cnt))]
#print(dp)
dp[1][0][1] = 1
#print(cnt,v)
v_id = [[-1 for i in range(w)] for j in range(h)]

for i in range(len(v)):
    idx = 0
    for x,y in v[i]:
        v_id[x][y] = idx
        idx += 1

for i in range(len(dp)-1):
    for j in range(cnt[i]):
        for k in range(cnt[i]):
            if j == k:
                continue
            xj,yj,xk,yk = v[i][j][0],v[i][j][1],v[i][k][0],v[i][k][1]
            xj += 1
            xk += 1
            if 0 <= xj < h and 0 <= yj < w and 0 <= xk < h and 0 <= yk < w and s[xj][yj] == '.' and s[xk][yk] == '.':
                tj,tk = v_id[xj][yj],v_id[xk][yk]
                if (i == len(dp)-2 or tj != tk):
                    dp[i+1][tj][tk] += dp[i][j][k]
                    dp[i+1][tj][tk] %= mod
            xj,yj,xk,yk = v[i][j][0],v[i][j][1],v[i][k][0],v[i][k][1]
            xj += 1
            yk += 1
            if 0 <= xj < h and 0 <= yj < w and 0 <= xk < h and 0 <= yk < w and s[xj][yj] == '.' and s[xk][yk] == '.':
                tj,tk = v_id[xj][yj],v_id[xk][yk]
                if (i == len(dp)-2 or tj != tk):
                    dp[i+1][tj][tk] += dp[i][j][k]
                    dp[i+1][tj][tk] %= mod
            xj,yj,xk,yk = v[i][j][0],v[i][j][1],v[i][k][0],v[i][k][1]
            yj += 1
            xk += 1
            if 0 <= xj < h and 0 <= yj < w and 0 <= xk < h and 0 <= yk < w and s[xj][yj] == '.' and s[xk][yk] == '.':
                tj,tk = v_id[xj][yj],v_id[xk][yk]
                if (i == len(dp)-2 or tj != tk):
                    dp[i+1][tj][tk] += dp[i][j][k]
                    dp[i+1][tj][tk] %= mod
            xj,yj,xk,yk = v[i][j][0],v[i][j][1],v[i][k][0],v[i][k][1]
            yj += 1
            yk += 1
            if 0 <= xj < h and 0 <= yj < w and 0 <= xk < h and 0 <= yk < w and s[xj][yj] == '.' and s[xk][yk] == '.':
                tj,tk = v_id[xj][yj],v_id[xk][yk]
                if (i == len(dp)-2 or tj != tk):
                    dp[i+1][tj][tk] += dp[i][j][k]
                    dp[i+1][tj][tk] %= mod
print(dp[-1][-1][-1])
0