D - Takahashi the Wall Breaker https://atcoder.jp/contests/abc400/tasks/abc400_d

abc400_d.py

from collections import deque

H, W = map(int, input().split())
S = [list(input().strip()) for _ in range(H)]
A, B, C, D = map(lambda x: int(x) - 1, input().split())

dist = [[float("inf")] * W for _ in range(H)]
dist[A][B] = 0

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

dq = deque()
dq.append((A, B))

while dq:
    y, x = dq.popleft()
    if y == C and x == D:
        break
    # コスト0の移動
    for dy, dx in dirs:
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if S[ny][nx] != ".":
            continue
        if dist[ny][nx] > dist[y][x]:
            dist[ny][nx] = dist[y][x]
            dq.appendleft((ny, nx))

    # コスト1の前蹴り
    for dy, dx in dirs:
        for k in (1, 2):
            ny, nx = y + k * dy, x + k * dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if dist[ny][nx] > dist[y][x] + 1:
                dist[ny][nx] = dist[y][x] + 1
                dq.append((ny, nx))

print(dist[C][D])