結果

問題 No.5006 Hidden Maze
コンテスト
ユーザー netyo715
提出日時 2022-06-12 15:53:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,705 ms / 2,000 ms
コード長 2,813 bytes
コンパイル時間 447 ms
実行使用メモリ 107,984 KB
スコア 66,939
平均クエリ数 331.46
最終ジャッジ日時 2022-06-12 15:58:05
合計ジャッジ時間 67,111 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heapify, heappop as pop, heappush as push
D = ((-1, 0), (0, -1), (0, 1), (1, 0))
def solve(H, W, P):
    stop_cnt = [[0]*(H*W) for _ in range(H*W)]
    is_empty = [[False]*(H*W) for _ in range(H*W)]
    def rc2idx(row, col):
        return row*W+col
    def idx2rc(idx):
        return idx//W, idx%W
    def is_empty_idx(idx1, idx2):
        return is_empty[idx1][idx2]
    def is_empty_rc(row1, col1, row2, col2):
        return is_empty_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def empty_per_idx(idx1, idx2):
        return 0
    def empty_per_rc(row1, col1, row2, col2):
        return empty_per_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def through_per_idx(idx1, idx2):
        if is_empty_idx(idx1, idx2):
            return (100-P)/100
        return (pow(P, stop_cnt[idx1][idx2])/pow(100, stop_cnt[idx1][idx2]-1)-P)/100

    def through_per_rc(row1, col1, row2, col2):
        return through_per_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def cmd_rc(row1, col1, row2, col2):
        if row1 > row2:
            return "U"
        if row1 < row2:
            return "D"
        if col1 > col2:
            return "L"
        if col1 < col2:
            return "R"

    for try_cnt in range(1, 1000+1):
        q = [(-1, 0, 0)]
        fixed = [[False]*W for _ in range(H)]
        dist = [[10]*W for _ in range(H)]
        prev = [[None]*W for _ in range(H)]
        while q:
            qper, qh, qw = pop(q)
            if fixed[qh][qw]:
                continue
            fixed[qh][qw] = True
            for a, b in D:
                h = qh+a; w = qw+b
                if not 0 <= h < H:
                    continue
                if not 0 <= w < W:
                    continue
                if fixed[h][w]:
                    continue
                per = -(-qper*through_per_rc(qh, qw, h, w))
                if dist[h][w] < per:
                    continue
                q.append((per, h, w))
                prev[h][w] = (qh, qw)
                dist[h][w] = per
        nodes = []
        h, w = H-1, W-1
        while h+w:
            nodes.append((h, w))
            h, w = prev[h][w]
        nodes.append((0, 0))
        nodes.reverse()
        cmd = []
        for i in range(len(nodes)-1):
            cmd.append(cmd_rc(nodes[i][0], nodes[i][1], nodes[i+1][0], nodes[i+1][1]))
        
        print(*cmd, sep="")
        through_cnt = int(input())
        if through_cnt == -1:
            return
        for i in range(through_cnt):
            idx1, idx2 = rc2idx(*nodes[i]), rc2idx(*nodes[i+1])
            is_empty[idx1][idx2] = True
            is_empty[idx2][idx1] = True
        idx1, idx2 = rc2idx(*nodes[through_cnt]), rc2idx(*nodes[through_cnt+1])
        stop_cnt[idx1][idx2] += 1

H, W, P = map(int, input().split())
solve(H, W, P)
0