結果

問題 No.5006 Hidden Maze
ユーザー netyo715netyo715
提出日時 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 #
プレゼンテーションモードにする

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0