import queue
 
H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]
 
c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]
 
q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]
 
while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break
 
                
print(res)
import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        for i in pre:
            q.put(i)
        pre=[]
    else:
        break

                
print(res)
提出情報

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
sy,sx=[int(i)-1 for i in input().split()]
gy,gx=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='#':
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)