Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append((start,0))
dist[start] = 0

while dq:
    p,d = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    if d>dist[p]:
        continue
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dist[q] = dist[p]
                        dq.appendleft((q,dist[q]))
                else:
                    if dist[q]>dist[p]+1:
                        dist[q] = dist[p] + 1
                        dq.append((q,dist[q]))

print(-1 if dist[goal]==10**10 else dist[goal])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1


print(-1 if dist[goal]==10**10 else dist[goal])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [[]for i in range(2)]
i = 0
a[i].append(start)
dist[start] = 0

while a[0] or a[1]:
    p = a[i].pop()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if dist[q]<=dist[p]:
                    continue
                if abs(dy)+abs(dx)==1:
                    a[i].append(q)
                    dist[q] = dist[p]
                else:
                    a[i-1].append(q)
                    dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]

print(-1 if dist[goal]==10**10 else dist[goal])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if dist[q]<=dist[p]:
                    continue
                if abs(dy)+abs(dx)==1:
                    dq.appendleft(q)
                    dist[q] = dist[p]
                else:
                    dq.append(q)
                    dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])
    








Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

ys,xs = (x-1 for x in readints())
yg,xg = (x-1 for x in readints())

maze = [readstr() for i in range(h)]

dist = [[10**10]*w for i in range(h)]

dq = deque()
dq.append([ys,xs])
dist[ys][xs] = 0

while dq:
    y,x = dq.popleft()
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.' and dist[y+dy][x+dx]>dist[y][x]:
                if abs(dy)+abs(dx)==1:
                    dq.appendleft((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x]
                else:
                    dq.append((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x] + 1

print(-1 if dist[yg][xg]==10**10 else dist[yg][xg])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

ys,xs = (x-1 for x in readints())
yg,xg = (x-1 for x in readints())

maze = [readstr() for i in range(h)]

dist = [[10**10]*w for i in range(h)]

dq = deque()
dq.append([ys,xs])
dist[ys][xs] = 0

while dq:
    y,x = dq.popleft()
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.' and dist[y+dy][x+dx]>dist[y][x]:
                if abs(dy)+abs(dx)==1:
                    dq.appendleft((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x]
                else:
                    dq.append((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x] + 1

print(-1 if dist[yg][xg]==10**10 else dist[yg][xg])


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])