Buggy python submission (verdict: Time Limit Exceeded):
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
import sys
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
            #移動先がゴールなら終了
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
                    #移動先がゴールなら終了
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Fixed submission:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
import sys
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
            #移動先がゴールなら終了
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
                    #移動先がゴールなら終了
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Buggy python submission (verdict: Time Limit Exceeded):
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Fixed submission:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
import sys
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
            #移動先がゴールなら終了
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
                    #移動先がゴールなら終了
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Buggy python submission (verdict: Time Limit Exceeded):
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1

Fixed submission:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
import sys
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
            #移動先がゴールなら終了
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
                    #移動先がゴールなら終了
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1