Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        while q:
            h, w = q.popleft()
            if done[h][w] == -1 and S[h][w] == ".":
                done[h][w] = num
                for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nh, nw = h+dh, w+dw
                    if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                        continue
                    if done[nh][nw] == -1:
                        q.append((nh, nw))
        num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
def dfs(h, w, num):
    done[h][w] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if done[nh][nw] == -1:
            dfs(nh, nw, num)
num = 0
for i in range(H):
    for j in range(W):
        if done[i][j] == -1 and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
def dfs(h, w, num):
    done[h][w] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if done[nh][nw] == -1:
            dfs(nh, nw, num)
num = 0
for i in range(H):
    for j in range(W):
        if done[i][j] == -1 and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
def dfs(h, w, num):
    dic[(h, w)] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if not (nh, nw) in dic:
            dfs(nh, nw, num)
dic = {}
num = 0
for i in range(H):
    for j in range(W):
        if (not (i, j) in dic) and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = dic[(h, w)]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = dic[(nh, nw)]
                if fr != to and (not done[fr][to]):
                    done[fr][to] = True
                    done[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(dic[(sh, sw)], G)
ans = D[dic[(gh, gw)]]
if ans != INF:
    print(ans)
else:
    print(-1)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)