Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
checked=[[False]*(w+1) for _ in range(h+1)]
checked[sy][sx]=True
q=collections.deque()
q.append((sy,sx))
ans=0
while 1:
  cur_pos=[]
  while len(q)!=0:
    y,x=q.popleft()
    cur_pos.append((y,x))
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
        checked[y+dy][x+dx]=True
        q.append((y+dy,x+dx))
  if checked[gy][gx]==True:
    print(ans)
    exit()
  if len(cur_pos)==0:
    print(-1)
    exit()
  ans+=1
  for y,x in cur_pos:
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
          checked[y+dy][x+dx]=True
          q.append((y+dy,x+dx))


Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

def calc():
  h,w=map(int,input().split())
  sy,sx=map(int,input().split())
  gy,gx=map(int,input().split())
  board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
  costs=[[10**18]*(w+1) for _ in range(h+1)]
  costs[sy][sx]=0
  q=[]
  heapq.heappush(q,(0,sy,sx))
  while len(q)!=0:
    cost,y,x=heapq.heappop(q)
    if y==gy and x==gx:
      print(cost)
      exit()
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
        costs[y+dy][x+dx]=costs[y][x]
        heapq.heappush(q,(cost,y+dy,x+dx))
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
          costs[y+dy][x+dx]=costs[y][x]+1
          heapq.heappush(q,(cost+1,y+dy,x+dx))
  print(-1)
calc()

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1
board=''
for _ in range(h):
  board+=input()
costs=[10**18]*(w*h)
costs[sy*w+sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  cur_pos=y*w+x
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    next_pos=cur_pos+dy*w+dx
    if 0<=y+dy<h and 0<=x+dx<w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]:
      costs[next_pos]=costs[cur_pos]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      next_pos=cur_pos+dy*w+dx
      if 0<=y+dy<h and 0<=x+dx<w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]+1:
        costs[next_pos]=costs[cur_pos]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy*w+gx]==10**18:
  print(-1)
else:
  print(costs[gy*w+gx])

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1
board=''
for _ in range(h):
  board+=input()
costs=[10**18]*(w*h)
costs[sy*w+sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  cur_pos=y*w+x
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    next_pos=cur_pos+dy*w+dx
    if 1<=y+dy<=h and 1<=x+dx<=w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]:
      costs[next_pos]=costs[cur_pos]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      next_pos=cur_pos+dy*w+dx
      if 1<=y+dy<=h and 1<=x+dx<=w and board[next_pos]=='.' and costs[next_pos]>costs[cur_pos]+1:
        costs[next_pos]=costs[cur_pos]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy*w+gx]==10**18:
  print(-1)
else:
  print(costs[gy*w+gx])

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
costs=[[10**18]*(w+1) for _ in range(h+1)]
costs[sy][sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
      costs[y+dy][x+dx]=costs[y][x]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
        costs[y+dy][x+dx]=costs[y][x]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy][gx]==10**18:
  print(-1)
else:
  print(costs[gy][gx])

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
costs=[[10**18]*(w+1) for _ in range(h+1)]
costs[sy][sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  if y==gy and x==gx:
    print(cost)
    exit()
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
      costs[y+dy][x+dx]=costs[y][x]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
        costs[y+dy][x+dx]=costs[y][x]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
print(-1)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx,0))
count=0
while len(q)!=0:
  y,x,score=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score:
      scores[y+dy][x+dx]=score
      q.append((y+dy,x+dx,score))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score+1:
        scores[y+dy][x+dx]=score+1
        q.appendleft((y+dy,x+dx,score+1))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append(r2)
                    checked.add((r1,r2))
q=collections.deque()
q.append(((uf.FindRoot((sy-1)*w+(sx-1))),0))
checked=[False]*(h*w+1)
ans=10**18
goal=uf.FindRoot((gy-1)*w+(gx-1))
while len(q)!=0:
    v,times=q.popleft()
    if v==goal:
        ans=min(ans,times)
        break
    checked[v]=True
    for u in edges[v]:
        if checked[u]==False:
            q.append((u,times+1))
if ans==10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append(r2)
                    checked.add((r1,r2))
q=collections.deque()
q.append(((uf.FindRoot((sy-1)*w+(sx-1))),0))
checked=[False]*(h*w+1)
ans=10**18
goal=uf.FindRoot((gy-1)*w+(gx-1))
while len(q)!=0:
    v,times=q.popleft()
    if v==goal:
        ans=min(ans,times)
    checked[v]=True
    for u in edges[v]:
        if checked[u]==False:
            q.append((u,times+1))
if ans==10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

import heapq

#edgeには[weight,v]を追加していく
def dijkstra(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append([1,r2])
                    checked.add((r1,r2))
dist=dijkstra(uf.FindRoot((sy-1)*w+(sx-1)),edges,h*w)
ans=dist[uf.FindRoot((gy-1)*w+(gx-1))]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

import heapq

#edgeには[weight,v]を追加していく
def dijkstra(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y-1>=0 and board[v-w]=='.':
            uf.Unite(v,v-w)
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x-1>=0 and board[v-1]=='.':
            uf.Unite(v,v-1)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append([1,r2])
                    checked.add((r1,r2))
dist=dijkstra(uf.FindRoot((sy-1)*w+(sx-1)),edges,h*w)
ans=dist[uf.FindRoot((gy-1)*w+(gx-1))]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

import heapq

#edgeには[weight,v]を追加していく
def dijkstra(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        if board[y][x]=='#':
            continue
        if y-1>=0 and board[y-1][x]=='.':
            uf.Unite(y*w+x,(y-1)*w+x)
        if y+1<h and board[y+1][x]=='.':
            uf.Unite(y*w+x,(y+1)*w+x)
        if x-1>=0 and board[y][x-1]=='.':
            uf.Unite(y*w+x,y*w+x-1)
        if x+1<w and board[y][x+1]=='.':
            uf.Unite(y*w+x,y*w+x+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y][x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[y+dy][x+dx]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append([1,r2])
                    checked.add((r1,r2))
dist=dijkstra(uf.FindRoot((sy-1)*w+(sx-1)),edges,h*w)
ans=dist[uf.FindRoot((gy-1)*w+(gx-1))]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])