Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
        elif (0<=ny<h and 0<=nx<w) and G[ny][nx] != '#':
            if abs(dy)+abs(dx)<=1:
                G[ny][nx] = '#'
                D[ny][nx] = D[y][x]
                Q.append((ny, nx))
            elif D[ny][nx] == 10**6:
                D[ny][nx] = D[y][x]+1
                Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])


Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])


Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Runtime Error):
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
G[sy][sx] = '#'
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    d = D[y][x]
    for dy, dx in product(range(-2, 3), repeat=2):
        if dx+dy==0:
            G[y][x] = '#'
        ny, nx = y+dy, x+dx
        elif any((ny<0, h<=ny, nx<0, w<=nx)):
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1 and D[ny][nx] > d:
            G[ny][nx] = '#'
            D[ny][nx] = d
            Q.append((ny, nx))
        elif D[ny][nx] > d+1:
            D[ny][nx] = d+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Runtime Error):
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = []
for _ in range(h):
    G.append(list(input()))
D = [[10**6]*w for i in range(h)]
D[sy][sx] = 0
Q = deque()
Q.append((sy, sx))

while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx+dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dx)+abs(dy)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] > D[y][x]+1:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "#"
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])


Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10**6, space=4)
    D[y, x] = 0
    while Q:
        x, y = Q.pop()
        for dx, dy in product(range(-2, 3), repeat=2):
            nx, ny = x+dx, y+dy
            if dx==dy==0:
                G[y, x] = '!'
                continue
            elif not G.is_valid_xy(nx, ny) or G[ny, nx] in '#!':
                continue
            elif abs(dx)+abs(dy)<=1:
                G[y, x] = '!'
                Q.append((nx, ny))
                D[ny, nx] = D[y, x]
            elif D[ny, nx] > D[y, x]+1:
                Q.appendleft((nx, ny))
                D[ny, nx] = D[y, x]+1       
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10**6, space=4)
    D[y, x] = 0
    
    walk = list(zip([1, 0, -1, 0], [0, 1, 0, -1]))
    warp = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2)
            if abs(dx)+abs(dy) >= 2]
    while Q:
        x, y = Q.pop()
        if G[y, x] == '!':
            continue
        d = D[y, x]
        G[y, x] = '!'
        
        for dx, dy in walk:
            nx, ny = x+dx, y+dy
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d:
                D[ny, nx] = d
                Q.append((nx, ny))
        for dx, dy in warp:
            nx, ny = x+dx, y+dy                
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d+1:
                D[ny, nx] = d+1
                Q.appendleft((nx, ny))
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(grid, start, goal):
    dequeue = deque([start])
    x, y = start
    dist = Grid(grid.grid, function=lambda x:-9 if x=='#' else 10**6, space=3)
    dist[y, x] = 0
    i = 0
    while dequeue:
        x, y = dequeue.pop()
        d = dist[y, x]
        i += 1
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.' and dist[ny, nx] > d:
                dist[ny, nx] = d
                dequeue.append((nx, ny))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.' and dist[ny, nx] > d+1:
                dist[ny, nx] = d+1
                dequeue.appendleft((nx, ny))
    x, y = goal
    return dist[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=3)
grid[sy, sx] = 's'
grid[gy, gx] = 'g'

ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(grid, root):
    dequeue = deque([root])
    x, y = root
    dist = Grid(grid.grid, function=lambda x:-9 if x=='#' else -1, space=3)
    dist[y, x] = 0
    while dequeue:
        x, y = dequeue.pop()
        if grid[y, x] == 'g':
            return dist[y, x]
        grid[y, x] = '!'
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.':
                if grid[ny, nx] == 'g':
                    return dist[y, x]
                dist[ny, nx] = dist[y, x]
                grid[ny, nx] = '!'
                dequeue.append((nx, ny))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.':
                dist[ny, nx] = dist[y, x] + 1
                dequeue.appendleft((nx, ny))
    return -1

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=3)
grid[sy, sx] = 's'
grid[gy, gx] = 'g'

print(bfs_01(grid, (sx, sy)))

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def bfs(root):
    def search(queue):
        delta = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2) if abs(dx) + abs(dy) >= 2]
        
        while queue:
            x, y = queue.pop()
            d = dp[y, x]
            for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                nx, ny = x+dx, y+dy
                if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.append((nx, ny))
        for x, y in product(range(w), range(h)):
            if dp[y, x] == d:
                 for dx, dy in delta:
                    nx, ny = x+dx, y+dy
                    if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                        dp[ny, nx] = d+1
                        queue.append((nx, ny))
        if queue:
            search(queue)
    
    x, y = root
    dp[y, x] = 0
    queue = deque([root])
    search(queue)
    
bfs((cw-1, ch-1))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def bfs(root):
    x, y = root
    dp[y, x] = 0
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        d = dp[y, x]
        for dx, dy in product(range(-2, 3), repeat=2):
            if dx == dy == 0:
                continue
            nx, ny = x+dx, y+dy
            if abs(dx) + abs(dy) == 1:
                if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.appendleft((nx, ny))          
            elif dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                queue.append((nx, ny))
bfs((cw-1, ch-1))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def bfs(root):
    x, y, d = root
    dp[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.appendleft((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    queue.append((nx, ny, d+1))
bfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    
    dfs([(x, y, d) for x, y, d in stack2 if dp[ny, nx] > d])

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Runtime Error):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Runtime Error):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
        dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid(list(X), function=lambda x: 10**6 if x == '.' else -1)

def bfs(root):
    x, y, d = root
    dp[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    queue.append((nx, ny, d+1))
bfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Fixed submission:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])