043 - Maze Challenge with Lack of Sleep（★4）

from collections import deque

INF = 10 ** 8

def _01BFS(x, y, G):			#始点sからの最短距離のリストを返す
    V = len(G)
    d = [INF for _ in range(V)]
    for i in range(4):
        d[calc(x, y, i)] = 0
    que = deque([(calc(x, y, i), 0) for i in range(4)])
    
    while que:
        p = que.popleft()
        for x in G[p[0]]:
            if d[x[0]] > p[1] + x[1]:
                d[x[0]] = p[1] + x[1]
                if x[1] == 0:
                    que.appendleft((x[0], d[x[0]]))
                else:
                    que.append((x[0], d[x[0]]))
    return d

def calc(x, y, direction):
    return x * W * 4 + y * 4 + direction

H, W = map(int,input().split())
rs, cs = map(int,input().split())
rt, ct = map(int,input().split())
S = [list(input()) for _ in range(H)]

V = 4 * H * W
G = [[] for _ in range(V)]

for i in range(H - 1):
    for j in range(W):
        if S[i][j] == '.' and S[i + 1][j] == '.':
            G[calc(i, j, 3)].append((calc(i + 1, j, 3), 0))
            G[calc(i + 1, j, 1)].append((calc(i, j, 1), 0))

for i in range(H):
    for j in range(W - 1):
        if S[i][j] == '.' and S[i][j + 1] == '.':
            G[calc(i, j, 0)].append((calc(i, j + 1, 0), 0))
            G[calc(i, j + 1, 2)].append((calc(i, j, 2), 0))

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        for k in range(3):
            for l in range(k + 1, 4):
                if k != l and (k - l) % 2 == 1:
                    G[calc(i, j, k)].append((calc(i, j, l), 1))
                    G[calc(i, j, l)].append((calc(i, j, k), 1))
ans = INF
d = _01BFS(rs - 1, cs - 1, G)
for i in range(4):
    ans = min(ans, d[calc(rt - 1, ct - 1, i)])
print(ans)