import heapq

INF = 1e7

def main():

    H,W=list(map(int, input().split()))

    sx, sy = list(map(int, input().split()))

    dh, dw = list(map(int, input().split()))

    sx -= 1

    sy -= 1

    S = [eval(input()) for _ in range(H)]

    def dijkstra(sx, sy):

        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)

        D[sx][sy] = 0

        PQ = [(0, (sx, sy))]

        heapq.heapify(PQ)

        while PQ: # PQに候補がある限り

            _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu

            for dx in range(-2, 3):

                for dy in range(-2, 3):

                    xx, yy = ux+dx, uy+dy

                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":

                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)

                        # neighborでなければコストが1増える

                        if abs(dx) + abs(dy) == 1:

                            if D[ux][uy] < D[xx][yy]:

                                D[xx][yy] = D[ux][uy]

                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))

                        else:

                            if D[ux][uy] + 1 < D[xx][yy]:

                                D[xx][yy] = D[ux][uy] + 1

                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))

        return D

    D = dijkstra(sx, sy)

    if D[dh-1][dw-1] >= INF:

        print((-1))

    else:

        print((D[dh-1][dw-1]))

main()
from itertools import product

from collections import deque

INF = 1e7

def main():

    H, W = list(map(int, input().split()))

    ch, cw = [int(x)+1 for x in input().split()]

    dh, dw = [int(x)+1 for x in input().split()]

    S = [["#"]*(W+4) for _ in range(H+4)]

    whites = [] #　道であるindex

    for i in range(2, H+2):

        tmp = eval(input())

        for j in range(2, W+2):

            S[i][j] = tmp[j-2]

            if S[i][j] == ".":

                whites.append((i,j))



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

    magic = list(product(list(range(-2, 3)), repeat=2))

    magic.remove((0, 0))

    for to_remove in dxdy:

        magic.remove(to_remove)

    

    # graph = {idx: deque() for idx in whites}

    # for idx in whites:

    #     x = idx[0]

    #     y = idx[1]

    #     for dx, dy in dxdy:

    #         if S[x+dx][y+dy] == ".":

    #             graph[idx].append((x+dx, y+dy))

    # graph2 = {idx: deque() for idx in whites}

    # for idx in whites:

    #     x = idx[0]

    #     y = idx[1]

    #     for mx, my in magic:

    #         if S[x+mx][y+my] == ".":

    #             graph2[idx].append((x+mx, y+my))

    

    def bfs(u,v):

        dist = [[INF] * (W+4) for _ in range(H+4)] #indexed from 1

        # seen = [[0] * (W+4) for _ in range(H+4)] #indexed from 1

        queue = deque()

        # seen[u][v] = 1

        dist[u][v] = 0

        queue.append((u,v))

        while queue:

            p, q = queue.popleft()

            # if not graph[(p,q)]:

            #     queue.popleft()

            #     continue

            # g,h = graph[(p,q)].popleft()

            # if seen[g][h]:

            #     continue

            # seen[g][h] = 1

            # dist[g][h] = min(dist[g][h], dist[p][q])

            for dx, dy in dxdy:

                g = p+dx

                h = q+dy

                if S[g][h]=="." and dist[g][h] > dist[p][q]:

                    dist[g][h] = dist[p][q]

                    queue.appendleft((g,h))

            for dx, dy in magic:

                g = p+dx

                h = q+dy

                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:

                    dist[g][h] = dist[p][q]+1

                    queue.append((g,h))

            # dist[g][h] = min(dist[g][h], dist[p][q]+1)

            # queue.append((g,h))

        return dist



    D = bfs(ch, cw)

    ans = D[dh][dw]

    if ans == INF:

        print((-1))

    else:

        print(ans)



if __name__ == "__main__":

    main()
import heapq

INF = 1e7


def main():
    H, W = list(map(int, input().split()))
    sx, sy = list(map(int, input().split()))
    dh, dw = list(map(int, input().split()))
    sx -= 1
    sy -= 1
    S = [eval(input()) for _ in range(H)]

    def dijkstra(sx, sy):
        D = [[INF] * (W) for _ in range(H)]  # 始点からの距離(重み)
        D[sx][sy] = 0
        PQ = [(0, (sx, sy))]
        heapq.heapify(PQ)
        while PQ:  # PQに候補がある限り
            _, (ux, uy) = heapq.heappop(PQ)  # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux + dx, uy + dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == ".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if abs(dx) + abs(dy) == 1:
                            if D[ux][uy] < D[xx][yy]:
                                D[xx][yy] = D[ux][uy]
                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
                        else:
                            if D[ux][uy] + 1 < D[xx][yy]:
                                D[xx][yy] = D[ux][uy] + 1
                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
        return D

    D = dijkstra(sx, sy)
    if D[dh - 1][dw - 1] >= INF:
        print((-1))
    else:
        print((D[dh - 1][dw - 1]))


main()

from itertools import product
from collections import deque

INF = 1e7


def main():
    H, W = list(map(int, input().split()))
    ch, cw = [int(x) + 1 for x in input().split()]
    dh, dw = [int(x) + 1 for x in input().split()]
    S = [["#"] * (W + 4) for _ in range(H + 4)]
    whites = []  # 　道であるindex
    for i in range(2, H + 2):
        tmp = eval(input())
        for j in range(2, W + 2):
            S[i][j] = tmp[j - 2]
            if S[i][j] == ".":
                whites.append((i, j))
    dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    magic = list(product(list(range(-2, 3)), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    # graph = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for dx, dy in dxdy:
    #         if S[x+dx][y+dy] == ".":
    #             graph[idx].append((x+dx, y+dy))
    # graph2 = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for mx, my in magic:
    #         if S[x+mx][y+my] == ".":
    #             graph2[idx].append((x+mx, y+my))
    def bfs(u, v):
        dist = [[INF] * (W + 4) for _ in range(H + 4)]  # indexed from 1
        # seen = [[0] * (W+4) for _ in range(H+4)] #indexed from 1
        queue = deque()
        # seen[u][v] = 1
        dist[u][v] = 0
        queue.append((u, v))
        while queue:
            p, q = queue.popleft()
            # if not graph[(p,q)]:
            #     queue.popleft()
            #     continue
            # g,h = graph[(p,q)].popleft()
            # if seen[g][h]:
            #     continue
            # seen[g][h] = 1
            # dist[g][h] = min(dist[g][h], dist[p][q])
            for dx, dy in dxdy:
                g = p + dx
                h = q + dy
                if S[g][h] == "." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g, h))
            for dx, dy in magic:
                g = p + dx
                h = q + dy
                if S[g][h] == "." and dist[g][h] > dist[p][q] + 1:
                    dist[g][h] = dist[p][q] + 1
                    queue.append((g, h))
            # dist[g][h] = min(dist[g][h], dist[p][q]+1)
            # queue.append((g,h))
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print((-1))
    else:
        print(ans)


if __name__ == "__main__":
    main()

-import heapq +from itertools import product +from collections import deque -    sx, sy = list(map(int, input().split())) -    dh, dw = list(map(int, input().split())) -    sx -= 1 -    sy -= 1 -    S = [eval(input()) for _ in range(H)] +    ch, cw = [int(x) + 1 for x in input().split()] +    dh, dw = [int(x) + 1 for x in input().split()] +    S = [["#"] * (W + 4) for _ in range(H + 4)] +    whites = []  # 　道であるindex +    for i in range(2, H + 2): +        tmp = eval(input()) +        for j in range(2, W + 2): +            S[i][j] = tmp[j - 2] +            if S[i][j] == ".": +                whites.append((i, j)) +    dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)] +    magic = list(product(list(range(-2, 3)), repeat=2)) +    magic.remove((0, 0)) +    for to_remove in dxdy: +        magic.remove(to_remove) +    # graph = {idx: deque() for idx in whites} +    # for idx in whites: +    #     x = idx[0] +    #     y = idx[1] +    #     for dx, dy in dxdy: +    #         if S[x+dx][y+dy] == ".": +    #             graph[idx].append((x+dx, y+dy)) +    # graph2 = {idx: deque() for idx in whites} +    # for idx in whites: +    #     x = idx[0] +    #     y = idx[1] +    #     for mx, my in magic: +    #         if S[x+mx][y+my] == ".": +    #             graph2[idx].append((x+mx, y+my)) +    def bfs(u, v): +        dist = [[INF] * (W + 4) for _ in range(H + 4)]  # indexed from 1 +        # seen = [[0] * (W+4) for _ in range(H+4)] #indexed from 1 +        queue = deque() +        # seen[u][v] = 1 +        dist[u][v] = 0 +        queue.append((u, v)) +        while queue: +            p, q = queue.popleft() +            # if not graph[(p,q)]: +            #     queue.popleft() +            #     continue +            # g,h = graph[(p,q)].popleft() +            # if seen[g][h]: +            #     continue +            # seen[g][h] = 1 +            # dist[g][h] = min(dist[g][h], dist[p][q]) +            for dx, dy in dxdy: +                g = p + dx +                h = q + dy +                if S[g][h] == "." and dist[g][h] > dist[p][q]: +                    dist[g][h] = dist[p][q] +                    queue.appendleft((g, h)) +            for dx, dy in magic: +                g = p + dx +                h = q + dy +                if S[g][h] == "." and dist[g][h] > dist[p][q] + 1: +                    dist[g][h] = dist[p][q] + 1 +                    queue.append((g, h)) +            # dist[g][h] = min(dist[g][h], dist[p][q]+1) +            # queue.append((g,h)) +        return dist -    def dijkstra(sx, sy): -        D = [[INF] * (W) for _ in range(H)]  # 始点からの距離(重み) -        D[sx][sy] = 0 -        PQ = [(0, (sx, sy))] -        heapq.heapify(PQ) -        while PQ:  # PQに候補がある限り -            _, (ux, uy) = heapq.heappop(PQ)  # 最小コストなノードu -            for dx in range(-2, 3): -                for dy in range(-2, 3): -                    xx, yy = ux + dx, uy + dy -                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == ".": -                        is_not_neighbor = int(abs(dx) + abs(dy) != 1) -                        # neighborでなければコストが1増える -                        if abs(dx) + abs(dy) == 1: -                            if D[ux][uy] < D[xx][yy]: -                                D[xx][yy] = D[ux][uy] -                                heapq.heappush(PQ, (D[xx][yy], (xx, yy))) -                        else: -                            if D[ux][uy] + 1 < D[xx][yy]: -                                D[xx][yy] = D[ux][uy] + 1 -                                heapq.heappush(PQ, (D[xx][yy], (xx, yy))) -        return D - -    D = dijkstra(sx, sy) -    if D[dh - 1][dw - 1] >= INF: +    D = bfs(ch, cw) +    ans = D[dh][dw] +    if ans == INF: -        print((D[dh - 1][dw - 1])) +        print(ans) -main() +if __name__ == "__main__": +    main()