結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 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 |
ソースコード
from heapq import heapify, heappop as pop, heappush as pushD = ((-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+coldef idx2rc(idx):return idx//W, idx%Wdef 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 0def 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)/100return (pow(P, stop_cnt[idx1][idx2])/pow(100, stop_cnt[idx1][idx2]-1)-P)/100def 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]:continuefixed[qh][qw] = Truefor a, b in D:h = qh+a; w = qw+bif not 0 <= h < H:continueif not 0 <= w < W:continueif fixed[h][w]:continueper = -(-qper*through_per_rc(qh, qw, h, w))if dist[h][w] < per:continueq.append((per, h, w))prev[h][w] = (qh, qw)dist[h][w] = pernodes = []h, w = H-1, W-1while 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:returnfor i in range(through_cnt):idx1, idx2 = rc2idx(*nodes[i]), rc2idx(*nodes[i+1])is_empty[idx1][idx2] = Trueis_empty[idx2][idx1] = Trueidx1, idx2 = rc2idx(*nodes[through_cnt]), rc2idx(*nodes[through_cnt+1])stop_cnt[idx1][idx2] += 1H, W, P = map(int, input().split())solve(H, W, P)