結果

問題 No.2646 Cycle Maze
ユーザー NP
提出日時 2024-02-26 10:23:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,165 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 82,548 KB
最終ジャッジ日時 2024-09-29 11:35:43
合計ジャッジ時間 10,315 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush

H, W, T = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
grid = [list(input()) for _ in range(H)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

# Check if the start or goal position is '0' right after input
if grid[sy][sx] == '0' or grid[gy][gx] == '0':
    print('No')
    exit()

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def is_reachable(mid):
    INF = 10**18
    dist = [[INF]*W for _ in range(H)]
    dist[sy][sx] = 0
    heap = [(0, sy, sx)]

    while heap:
        d, y, x = heappop(heap)
        if d > dist[y][x]:
            continue
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or W <= nx or ny < 0 or H <= ny:
                continue
            cost = mid if grid[ny][nx] == '#' else 1
            if d + cost < dist[ny][nx]:
                dist[ny][nx] = d + cost
                heappush(heap, (d + cost, ny, nx))
    return dist[gy][gx] <= T

left, right = 1, T
while right - left > 1:
    mid = (left + right) // 2
    if is_reachable(mid):
        left = mid
    else:
        right = mid

print('Yes' if left != 1 else 'No')
0