Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [input().strip() for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

INF = float('inf')

def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input()) for _ in range(H)]

row = []
col = []
cost = []

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                row.append(rc_to_v(y, x))  # head
                col.append(rc_to_v(ny, nx))  # tail
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    cost.append(0)
                else:
                    cost.append(1)


AM = coo_matrix((cost, (row, col)), shape = (H * W, H * W)).tocsr()
cost = dijkstra(AM, directed = False, indices = rc_to_v(sy, sx))

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from collections import defaultdict
from itertools import combinations
INF = float('inf')

def dijkstra_al(s, n, ALcost, start_index = 0):
    '''
    ダイクストラ法 O(|E|log|V|)
    グラフを隣接リストで表す場合
    始点sから各頂点への最短距離
    n: 頂点の数、s: 始点
    cost存在しないときはinf
    start_index: 0のときvertexは0, 1, ..., n-1
                 1のときvertexは1, 2, ..., n
    '''
    import heapq


    fixed = [False] * (n + 1) # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * (n + 1)  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        # for v, edge_cost in ALcost[u]:
        for v in ALcost[u]:
            edge_cost = 1
            if fixed[v]: continue
            newcost = u_cost + edge_cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    if start_index == 0:
        return vertex_cost[:n]
    else:
        return vertex_cost # index 0はダミー

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input()) for _ in range(H)]
grp = [[-1 for _ in range(W)] for _ in range(H)]

y = 0
x = 0
k = 0
for iy in range(H):
    for ix in range(W):
        if S[iy][ix] == '#' or grp[iy][ix] >= 0: continue
        que = deque([(iy, ix)])
        grp[iy][ix] = k
        while que:
            y, x = que.popleft()
            for dy, dx in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#' or grp[ny][nx] >= 0: # 行けないか訪問済み
                    continue
                grp[ny][nx] = k
                que.append((ny, nx))
        k += 1


AL = [[] for _ in range(k)]
E = defaultdict(bool)

for iy in range(H):
    for ix in range(W):
        if grp[iy][ix] < 0: continue

        que = deque([(iy, ix)])
        while que:
            y, x = que.popleft()
            for dy, dx in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#' or grp[ny][nx] >= 0:  # 行けないか訪問済み
                    continue
                grp[ny][nx] = k
                que.append((ny, nx))

w = min(3, W)
h = min(3, H)
for y in range(H - h + 1):
    for x in range(W - w + 1):
        dict = defaultdict(bool)
        for dy in range(h):
            for dx in range(w):
                ny = y + dy
                nx = x + dx
                if grp[ny][nx] >= 0:
                    dict[grp[ny][nx]] = True
        for a, b in combinations(dict.keys(), 2):
            if E[(a, b)] == True:  continue
            E[(a, b)] = True
            E[(b, a)] = True
            AL[a].append(b)
            AL[b].append(a)


cost = dijkstra_al(grp[sy][sx], k, AL)
ans = cost[grp[gy][gx]]
print(-1 if ans == INF else ans)


Fixed submission:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))