結果

問題 No.659 徘徊迷路
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:26:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 245 ms / 2,000 ms
コード長 2,636 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 78,132 KB
最終ジャッジ日時 2025-03-20 20:27:54
合計ジャッジ時間 2,761 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    R, C, T = map(int, sys.stdin.readline().split())
    Sy, Sx = map(int, sys.stdin.readline().split())
    Gy, Gx = map(int, sys.stdin.readline().split())
    B = [sys.stdin.readline().strip() for _ in range(R)]

    start = (Sy, Sx)
    goal = (Gy, Gx)

    visited = set()
    q = deque()
    q.append(start)
    visited.add(start)
    while q:
        y, x = q.popleft()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < R and 0 <= nx < C and B[ny][nx] == '.' and (ny, nx) not in visited:
                visited.add((ny, nx))
                q.append((ny, nx))
    
    if goal not in visited:
        print("0.0000000000000000")
        return

    states = list(visited)
    n = len(states)
    coord_to_idx = {(y, x): i for i, (y, x) in enumerate(states)}
    s = coord_to_idx[start]
    g = coord_to_idx[goal]

    M = [defaultdict(float) for _ in range(n)]
    for i in range(n):
        y, x = states[i]
        valid_moves = []
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < R and 0 <= nx < C and B[ny][nx] == '.':
                if (ny, nx) in coord_to_idx:
                    valid_moves.append((ny, nx))
        P = len(valid_moves)
        if P == 0:
            j = coord_to_idx[(y, x)]
            M[i][j] += 1.0
        else:
            prob = 1.0 / P
            for (ny, nx) in valid_moves:
                j = coord_to_idx[(ny, nx)]
                M[i][j] += prob

    def multiply(a, b):
        res = [defaultdict(float) for _ in range(n)]
        for i in range(n):
            for k in a[i]:
                a_ik = a[i][k]
                if a_ik == 0:
                    continue
                for j in b[k]:
                    res[i][j] += a_ik * b[k][j]
        for i in range(n):
            row = res[i]
            to_remove = [j for j in row if abs(row[j]) < 1e-12]
            for j in to_remove:
                del row[j]
        return res

    def matrix_power(mat, power):
        result = [defaultdict(float) for _ in range(n)]
        for i in range(n):
            result[i][i] = 1.0
        current = mat
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, current)
            current = multiply(current, current)
            power //= 2
        return result

    MT = matrix_power(M, T)
    probability = MT[s].get(g, 0.0)
    print("{0:.15f}".format(probability))

if __name__ == "__main__":
    main()
0