Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


#hhww=[]
#for i in hh:
#    for j in ww:
#        if s[i][j]==".":
#            hhww.append((i,j))
hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        if s[i][j]==".":
#            g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww if s[i][j]=="."] for i in hh]
#g=[[[(i+ii,j+jj) for ii,jj in ij if (s[i][j]=="." and 0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

hhww=[]
for i in hh:
    for j in ww:
        if s[i][j]==".":
            hhww.append((i,j))
            
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        if s[i][j]==".":
#            g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww if s[i][j]=="."] for i in hh]
#g=[[[(i+ii,j+jj) for ii,jj in ij if (s[i][j]=="." and 0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


#for j in ww:
#    for i in hh[0:-1]:
#        if s[i+1][j]==".": g[i][j].append((i+1,j))        
#        if s[i][j]==".": g[i+1][j].append((i,j))        
#for i in hh:
#    for j in ww[0:-1]:
#        if s[i][j+1]==".": g[i][j].append((i,j+1))        
#        if s[i][j]==".": g[i][j+1].append((i,j))        

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (s[i][j]=="." and 0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
#        if s[i][j]==".":
#            g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww if s[i][j]=="."] for i in hh]
#g=[[[(i+ii,j+jj) for ii,jj in ij if (s[i][j]=="." and 0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1




#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


#for j in ww:
#    for i in hh[0:-1]:
#        if s[i+1][j]==".": g[i][j].append((i+1,j))        
#        if s[i][j]==".": g[i+1][j].append((i,j))        
#for i in hh:
#    for j in ww[0:-1]:
#        if s[i][j+1]==".": g[i][j].append((i,j+1))        
#        if s[i][j]==".": g[i][j+1].append((i,j))        

#for i in hh:
#    for j in ww:
#        if s[i][j]==".":
#            g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww if s[i][j]=="."] for i in hh]
g=[[[(i+ii,j+jj) for ii,jj in ij if (s[i][j]=="." and 0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1




#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for i in hh:
    for j in ww:
        if s[i][j]==".":
            g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    g[i]=[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
        if s[i+1][j]==".": g[i][j].append((i+1,j))        
        if s[i][j]==".": g[i+1][j].append((i,j))        
for i in hh:
    for j in ww[0:-1]:
        if s[i][j+1]==".": g[i][j].append((i,j+1))        
        if s[i][j]==".": g[i][j+1].append((i,j))        


#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
        if s[i+1][j]==".": g[i][j].append((i+1,j))        
        if s[i][j]==".": g[i+1][j].append((i,j))        
for i in hh:
    for j in ww[0:-1]:
        if s[i][j+1]==".": g[i][j].append((i,j+1))        
        if s[i][j]==".": g[i][j+1].append((i,j))        print(-2)

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
#    if i+1<h:
        if s[i+1][j]==".":
            g[i][j].append((i+1,j))        
    for i in hh[1:]:
#    if 0<=i-1:
#    for j in ww:
        if s[i-1][j]==".":
            g[i][j].append((i-1,j))        
for i in hh:
    for j in ww[0:-1]:
#        if j+1<w:
        if s[i][j+1]==".":
            g[i][j].append((i,j+1))        
#for i in hh:
    for j in ww[1:]:
#        if 0<=j-1:
        if s[i][j-1]==".":
            g[i][j].append((i,j-1))        


#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#for i in hh:
#    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#for i in hh:
#    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#for i in hh:
#    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]

for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
#        if i+1<h:
#            if s[i+1][j]==".":
#                g[i][j].append((i+1,j))        
#            else:
#                wpg2[i][j]=1
#        if 0<=i-1:
#            if s[i-1][j]==".":
#                g[i][j].append((i-1,j))        
#            else:
#                wpg2[i][j]=1
#        if j+1<w:
#            if s[i][j+1]==".":
#                g[i][j].append((i,j+1))        
#            else:
#                wpg2[i][j]=1
#        if 0<=j-1:
#            if s[i][j-1]==".":
#                g[i][j].append((i,j-1))        
#            else:
#                wpg2[i][j]=1

        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
#        if 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
#        if j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
#        if 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

#for i in hh:
#    for j in ww:
#        if i+1<h:
#            if s[i+1][j]==".":
#                g[i][j].append((i+1,j))        
#            else:
#                wpg2[i][j]=1
#        if 0<=i-1:
#            if s[i-1][j]==".":
#                g[i][j].append((i-1,j))        
#            else:
#                wpg2[i][j]=1
#        if j+1<w:
#            if s[i][j+1]==".":
#                g[i][j].append((i,j+1))        
#            else:
#                wpg2[i][j]=1
#        if 0<=j-1:
#            if s[i][j-1]==".":
#                g[i][j].append((i,j-1))        
#            else:
#                wpg2[i][j]=1

#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
#        if 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
#        if j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
#        if 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]
wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
#        if i+1<h:
#            if s[i+1][j]==".":
#                g[i][j].append((i+1,j))        
#            else:
#                wpg2[i][j]=1
#        if 0<=i-1:
#            if s[i-1][j]==".":
#                g[i][j].append((i-1,j))        
#            else:
#                wpg2[i][j]=1
#        if j+1<w:
#            if s[i][j+1]==".":
#                g[i][j].append((i,j+1))        
#            else:
#                wpg2[i][j]=1
#        if 0<=j-1:
#            if s[i][j-1]==".":
#                g[i][j].append((i,j-1))        
#            else:
#                wpg2[i][j]=1

        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
#        if 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
#        if j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
#        if 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1

for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=sum([ 1 for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]+[0])

for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=max([ 1 for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]+[0])

for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=max([0]+[ 1 for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")])

for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        wpg2[i][j]=max([ 1 for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")])

for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
        if (i+1<h and s[i+1][j]=="#") or \
           (0<=i-1 and s[i-1][j]=="#") or \
           (j+1<w and s[i][j+1]=="#") or \
           (0<=j-1 and s[i][j-1]=="#"): 
            wpg2[i][j]=1

for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        if i+1<h:
            if s[i+1][j]==".":
                g[i][j].append((i+1,j))        
            else:
                wpg2[i][j]=1
        if 0<=i-1:
            if s[i-1][j]==".":
                g[i][j].append((i-1,j))        
            else:
                wpg2[i][j]=1
        if j+1<w:
            if s[i][j+1]==".":
                g[i][j].append((i,j+1))        
            else:
                wpg2[i][j]=1
        if 0<=j-1:
            if s[i][j-1]==".":
                g[i][j].append((i,j-1))        
            else:
                wpg2[i][j]=1
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
#        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
#                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
#        g[i][j]=ggg        
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in hh:
    for j in ww:
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
#for i in range(h):
#    for j in range(w):
for i in hh:
    for j in ww:
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0<=i+ii<h and 0<=j+jj<w:
                if s[i+ii][j+jj]==".":
                    g[i][j].append((i+ii,j+jj))        
                else:
#                wpg.append((i,j))
                    wpg2[i][j]=1

for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1

for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1

  for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import deque

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Runtime Error):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
                wpg.append((i,j))
#                wpg2[i][j]=1
                
#for i in range(h):
#    for j in range(w):
#        if wpg2[i][j]==1:
#            wpg.append((i,j))
                
wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

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

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Buggy python submission (verdict: Runtime Error):

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[[0] for i in range(w)] for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        ww=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=h:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)   


Fixed submission:

import sys
from collections import deque
import itertools

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
    elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
    elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
    elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)