結果

問題 No.659 徘徊迷路
ユーザー roaris
提出日時 2019-11-02 20:27:30
言語 PyPy3
(7.0.0)
結果
TLE  
実行時間 -
コード長 1,341 Byte
コンパイル時間 2,012 ms
使用メモリ 73,952 KB
最終ジャッジ日時 2019-11-02 20:27:55

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 192 ms
70,912 KB
sample2.txt AC 704 ms
72,336 KB
sample3.txt AC 168 ms
70,596 KB
sample4.txt AC 125 ms
69,044 KB
sample5.txt AC 980 ms
73,952 KB
test1.txt AC 220 ms
69,596 KB
test2.txt AC 221 ms
70,176 KB
test3.txt AC 169 ms
70,188 KB
test4.txt AC 1,011 ms
73,508 KB
test5.txt TLE -
test6.txt TLE -
test7.txt TLE -
test8.txt AC 601 ms
71,668 KB
test9.txt TLE -
test10.txt TLE -
test11.txt TLE -
test12.txt TLE -
テストケース一括ダウンロード

ソースコード

diff #
def mat_mul(A, B):
    C = [[0]*len(B[0]) for _ in range(len(A))]
    
    for i in range(len(A)):
        for j in range(len(B[0])):
            C[i][j] = sum(A[i][k]*B[k][j] for k in range(len(A[0])))

    return C

def mat_pow(A, n):
    res = [[0]*len(A) for _ in range(len(A))]
    
    for i in range(len(A)):
        res[i][i] = 1
    
    while n > 0:
        if n&1:
            res = mat_mul(A, res)
        
        n >>= 1
        A = mat_mul(A, A)
    
    return res

R, C, T = map(int, input().split())
Sx, Sy = map(int, input().split())
Gx, Gy = map(int, input().split())
B = [input() for _ in range(R)]
#変換行列Tr: Tr[i][j]: jからiへ移動する確率
Tr = [[0]*(R*C) for _ in range(R*C)]

for i in range(R):
    for j in range(C):
        if B[i][j] == '#':
            continue
        
        cnt = 0
        
        for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if B[ni][nj] == '.':
                cnt += 1
        
        if cnt == 0:
            Tr[C*i+j][C*i+j] = 1
            continue
        
        p = 1/cnt
        
        for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if B[ni][nj] == '.':
                Tr[C*ni+nj][C*i+j] = p

before = [[0] for _ in range(R*C)]
before[C*Sx+Sy][0] = 1
after = mat_mul(mat_pow(Tr, T), before)

print(after[C*Gx+Gy][0])
0