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

read = sys.stdin.read
readline = sys.stdin.readline

def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while len(deq):
    y,x = deq.popleft()
    for dy,dx in move_a:
      ny,nx = y+dy,x+dx
      if 0<=ny<H and 0<=nx<W and S[ny][nx] and dist[ny][nx]>dist[y][x]:
        dist[ny][nx] = dist[y][x]
        deq.appendleft((ny,nx))
    for dy,dx in move_b:
      ny,nx = y+dy,x+dx
      if not (0<=ny<H and 0<=nx<W):
        continue
      if not S[ny][nx]:
        continue
      if dist[ny][nx] <= dist[y][x]+1:
        continue
      flag = False
      for ddy,ddx in move_a:
        nny,nnx = ny+ddy,nx+ddx
        if 0<=nny<H and 0<=nnx<W and S[nny][nnx] and dist[nny][nnx]==dist[y][x]:
          flag = True
          break
      if flag:
        continue
      dist[ny][nx] = dist[y][x] + 1
      deq.append((ny,nx))
    
  ans = dist[D_h][D_w]
  print(ans if ans!=INF else -1)


H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = [[c=='.' for c in readline()] for _ in range(H)]

solve(H,W,C_h,C_w,D_h,D_w,S)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  isinque = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      isinque[h][w] = False
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          if isinque[nh][nw]==False:
            que2.append((nh,nw))
            isinque[nh][nw] = True
    while j<len(que2):
      h,w = que2[j]
      j += 1
      isinque[h][w] = False
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          if isinque[nh][nw]==False:
            que2.append((nh,nw))
            isinque[nh][nw] = True
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([readline() for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from numba import njit, b1, i4, i8, f8
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = [readline() for _ in range(H)]
solve(H,W,C_h,C_w,D_h,D_w,S)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
from numba import njit

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve():
  H,W = map(int,input().split())
  C_h,C_w = map(lambda x:int(x)-1,input().split())
  D_h,D_w = map(lambda x:int(x)-1,input().split())
  S = [readline() for _ in range(H)]

  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

  while len(deq):
    h,w = deq.popleft()
    if seen[h][w]:
      continue
      seen[h][w] = True
    for dh,dw in move_a:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
        dist[nh][nw] = dist[h][w]
        deq.appendleft((nh,nw))
    for dh,dw in move_b:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
        dist[nh][nw] = dist[h][w]+1
        deq.append((nh,nw))

  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

solve()

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

read = sys.stdin.read
readline = sys.stdin.readline

def solve():
  H,W = map(int,input().split())
  C_h,C_w = map(lambda x:int(x)-1,input().split())
  D_h,D_w = map(lambda x:int(x)-1,input().split())
  S = [readline() for _ in range(H)]

  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

  while len(deq):
    h,w = deq.popleft()
    if seen[h][w]:
      continue
      seen[h][w] = True
    for dh,dw in move_a:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
        dist[nh][nw] = dist[h][w]
        deq.appendleft((nh,nw))
    for dh,dw in move_b:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
        dist[nh][nw] = dist[h][w]+1
        deq.append((nh,nw))

  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
solve()

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
seen = [[False]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  if seen[h][w]:
    continue
    seen[h][w] = True
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Runtime Error):
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)


Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Buggy python submission (verdict: Runtime Error):
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if (nh<0 or nw<0 or nh>=H or nw>=W) and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if (nh<0 or nw<0 or nh>=H or nw>=W) and S[nh][nw] == '#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

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

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Fixed submission:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)