ABC170F - Pond Skater - 競プロはじめました

考え方
回答例

考え方

最短経路問題 - 競プロはじめました
コストゼロで行けるものを優先してみればBFSで解ける．
キューからpopしたものから更新される頂点はコスト＋1される．

コストゼロで到達できる頂点で，自分のコスト以下のものに出会ったら，その先は見なくて良い．

回答例

from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
c = [list(input()) for _ in range(H)]

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
INF = 1 << 60
dist = [[INF] * W for _ in range(H)]
dist[x1][y1] = 0
q = deque()
q.append((x1, y1, 0))
while q:
    x, y, d = q.popleft()
    if dist[x][y] < d:
        continue
    for i in range(4):
        for j in range(1, K + 1):
            xx, yy = x + j * dx[i], y + j * dy[i]
            if not(0 <= xx < H and 0 <= yy < W):
                break
            if c[xx][yy] == '@':
                break
            if dist[xx][yy] <= dist[x][y]:
                break
            if dist[x][y] + 1 < dist[xx][yy]:
                dist[xx][yy] = dist[x][y] + 1
                q.append((xx, yy, dist[xx][yy]))

print(dist[x2][y2] if dist[x2][y2] < INF else -1)

以下は不要だった．

    if dist[x][y] < d:
        continue