Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    import heapq
    from sys import stdin
    h,w = map(int,input().split())
    si,sj = map(int,input().split())
    gi,gj = map(int,input().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    readline = stdin.readline
    for _ in [0]*h:
        grid.append(readline())
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    dist[si][sj] = 0
    heap = [(0,si,sj)]
    while heap:
        mindist,i,j = heapq.heappop(heap)
        if (i,j) == (gi,gj):
            return mindist
        if mindist > dist[i][j]: continue
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    heapq.heappush(heap,(dist[ni][nj],ni,nj))
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in range(j-2,j+3):
                if not (0 <= nj and nj < w): continue
                if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                    if dist[ni][nj] > dist[i][j] + 1:
                        dist[ni][nj] = dist[i][j] + 1
                        heapq.heappush(heap,(dist[ni][nj],ni,nj))
    return -1
print(solve())

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from sys import stdin
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in [0]*h:
    grid.append(stdin.readline())
INF = float("inf")
dist = [[INF]*w for _ in range(h)]
dist[si][sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i][j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni][nj] > dist[i][j]:
                dist[ni][nj] = dist[i][j]
                heapq.heappush(heap,(dist[ni][nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    heapq.heappush(heap,(dist[ni][nj],ni,nj))
 
else:
    print(-1)

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from sys import stdin
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(stdin.readline()[:-1])
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))
 
else:
    print(-1)

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(input())
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))
 
else:
    print(-1)

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                    if dist[ni][nj] > dist[i][j] + 1:
                        dist[ni][nj] = dist[i][j] + 1
                        q.append((ni,nj))

    return -1

print(solve())

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in range(h):
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = {(i,j):INF for i in range(h) for j in range(w)}
    q = collections.deque([(si,sj)])
    dist[si,sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i,j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j]:
                    dist[ni,nj] = dist[i,j]
                    q.appendleft((ni,nj))
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in range(j-2,j+3):
                if not (0 <= nj and nj < w): continue
                if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                    if dist[ni,nj] > dist[i,j] + 1:
                        dist[ni,nj] = dist[i,j] + 1
                        q.append((ni,nj))

    return -1

print(solve())

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
import collections
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(input())
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
q = collections.deque([(si,sj)])
dist[si,sj] = 0
while q:
    i,j = q.popleft()
    if (i,j) == (gi,gj):
        print(dist[i,j])
        break
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                q.appendleft((ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    q.append((ni,nj))

else:
    print(-1)


Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(input())
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))

else:
    print(-1)

Fixed submission:
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())