Problem: A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i-th row from the top and the j-th column from the left - (i,j) \- is a wall if S_{ij} is `#` and a road if S_{ij} is `.`.  There is a magician in (C_h,C_w). He can do the following two kinds of moves:    * Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.   * Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.  In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w)?

Submission attempts (in order):
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  


walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  の場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  の場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

h = 0
w = 0
reached = []
maze = []
dh = 0
dw = 0


def main():
    global h
    global w
    global dh
    global dw
    h, w = map(int, input().split())    
    ch, cw = map(int, input().split())  
    dh, dw = map(int, input().split())  
    for i in range(h):
        maze.append(list(input()))
    # for (i, row) in enumerate(maze, 1):
    #     print('{}: {}'.format(i, row))
    warp_count = 0
    while True:
        if walk_to(ch, cw):
            
            # print('Goal!')
            print(warp_count)
            break
        else:
            
            mch, mcw = most_close()
            
            warped_hw = warp_from(mch, mcw)
            if warped_hw is not None:
                warp_count += 1
                ch, cw = warped_hw
            else:
                不能
                
                print(-1)
                break


def warp_from(mch, mcw):
    start_h = max(mch - 2, 1)
    end_h = min(mch + 2, h)
    start_w = max(mcw - 2, 1)
    end_w = min(mcw + 2, w)

    min_distance = None
    min_hw = None
    for i in range(start_h, end_h + 1):
        for j in range(start_w, end_w + 1):
            # print(i, j)
            if get_block(i, j) == '.' and yet(i, j):
                
                distance = abs(dh - i) + abs(dw - j)
                if min_distance is None or distance < min_distance:
                    min_distance = distance
                    min_hw = [i, j]
    return min_hw


def most_close():
    min_hw = []
    min_distance = None
    for r in reached:
        distance = max(abs(dh - r[0]), abs(dw - r[1]))
        if min_distance is None or distance < min_distance:
            min_distance = distance
            min_hw = [r[0], r[1]]
    return min_hw


def walk_to(current_h, current_w):
    reached.append([current_h, current_w])    済み
    if current_h == dh and current_w == dw:
        return True
    
    if current_h > 1 and get_block(current_h - 1, current_w) == '.' and yet(current_h - 1, current_w):
        
        return walk_to(current_h - 1, current_w)
    
    if current_w < w and get_block(current_h, current_w + 1) == '.' and yet(current_h, current_w + 1):
        
        return walk_to(current_h, current_w + 1)
    
    if current_h < h and get_block(current_h + 1, current_w) == '.' and yet(current_h + 1, current_w):
        
        return walk_to(current_h + 1, current_w)
    
    if current_w > 1 and get_block(current_h, current_w - 1) == '.' and yet(current_h, current_w - 1):
        
        return walk_to(current_h, current_w - 1)

    
    return False


def get_block(target_h, target_w):
    return maze[target_h - 1][target_w - 1]


def yet(check_h, check_w):
    for r in reached:
        if check_h == r[0] and check_w == r[1]:
            return False
    return True


if __name__ == "__main__":
    main()


from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    
    walled_maze = ['##{}##'.format(row) for row in maze]
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))

    INF = 10 ** 12
    path = [[INF] * (W + 4) for _ in range(H + 4)]
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    yet = deque()
    yet.append((Ch + 2, Cw + 2, 0))    
    path[Ch + 2][Cw + 2] = 0
    done = deque()

    while yet:
        y, x, s = yet.popleft()
        done.append((y, x, s))
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                yet.append((ny, nx, s))
        if len(yet) == 0:
            while done:
                y, x, s = done.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                        path[ny][nx] = s + 1
                        yet.append((ny, nx, s + 1))
    ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)


Verdicts: Time Limit Exceeded

Wrong Answer

Accepted