Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=input()
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]==-1:
            continue
        else:
            for d0,d1 in dif:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 0])
            for d0,d1 in warp:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source, goal):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        if v==goal:
            break
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[goal]

dist=dijkstra(es,h*w,ch*w+cw,dh*w+dw)
if dist==float('inf'):
    print(-1)
else:
    print(dist)

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=input()
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]==-1:
            continue
        else:
            for d0,d1 in dif:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 0])
            for d0,d1 in warp:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source, goal):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        if v==goal:
            break
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[goal]

dist=dijkstra(es,h*w,ch*w+cw,dh*w+dw)
if dist==float('inf'):
    print(-1)
else:
    print(dist)

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]==-1:
            continue
        else:
            for d in dif:
                newi=i+d[0]
                newj=j+d[1]
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 0])
            for d in warp:
                newi=i+d[0]
                newj=j+d[1]
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

dist=dijkstra(es,h*w,ch*w+cw)
if dist[dh*w+dw]==float('inf'):
    print(-1)
else:
    print(dist[dh*w+dw])

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))
dif=list(dif)
warp=list(warp)

for i in range(h):
    for j in range(w):
        if grid[i][j]!=-1:
            for d in dif:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 0])
            for d in warp:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

dist=dijkstra(es,h*w,ch*w+cw)
if dist[dh*w+dw]==float('inf'):
    print(-1)
else:
    print(dist[dh*w+dw])

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]!=-1:
            for d in dif:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 0])
            for d in warp:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

dist=dijkstra(es,h*w,ch*w+cw)
if dist[dh*w+dw]==float('inf'):
    print(-1)
else:
    print(dist[dh*w+dw])

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
cand=set([])
for i in range(h):
    for j in range(w):
        if grid[i][j]!=0:
            continue
        else:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                    elif 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==-1:
                        cand.add((nowi, nowj))

start=grid[ch][cw]-1
end=grid[dh][dw]-1

if start==end:
    print(0)
    exit()

es=[set([]) for _ in range(col)]
visited=[-1]*col
for i,j in cand:
    now=grid[i][j]
    if now!=-1: 
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x,y) in dif:
                    continue
                if 0<=i+x<h and 0<=j+y<w:
                    nex=grid[i+x][j+y]
                    if nex!=-1 and now!=nex:
                        es[now-1].add(nex-1)
stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    v=visited[now]
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=v+1
            stack.append(e)
#print(grid)
print(visited[end])

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))

es=[set([]) for _ in range(col)]
visited=[-1]*col
for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if (x,y) in dif:
                        continue
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])


Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Buggy python submission (verdict: Time Limit Exceeded):
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
es=[set([]) for _ in range(col)]
visited=[-1]*col
for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Fixed submission:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])