Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    d2.append((Th,Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    
    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    
    s = [[0] * W for x in range(H)]
    
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and s[py][px] == 0:
                    s[py][px] == 1
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as Q


bloques = Q()
totreat = Q()

def voisins(x,y):
	lst = []
	for i in range(x-2,x+3):
		for j in range(y-2, y+3):
			if 0<=i<H and 0<=j<W and not vis[i][j]: lst+=[(i,j)]
	return lst

def bfs():
	# ~ print("bfs")
	while not totreat.empty():
		x,y = totreat.get()
		# ~ print(x,y,"en traitement")
		vis[x][y] = True
		bou = False
		for a,b in ((x,y+1),(x,y-1),(x+1,y),(x-1,y)):
			if 0<=a<H and 0<=b<W:
				if g[a][b]=='.':
					if not vis[a][b]:
						bou = True
						vis[a][b] = True
						dist[a][b] = min(dist[a][b],dist[x][y])
						totreat.put((a,b))
				else:
					# ~ print(x,y,"est bloque") 
					if not deja[x][y]:
						bloques.put((x,y))
						deja[x][y] = True

def bfs_magic():
	# ~ print("bfsmagic")
	while not bloques.empty():
		x,y = bloques.get()
		vis[x][y] = True
		for a,b in voisins(x,y):
			if 0<=a<H and 0<=b<W and g[a][b]=='.':
				vis[a][b] = True
				dist[a][b] = min(dist[a][b],dist[x][y]+1)
				totreat.put((a,b))

H,W = [int(i) for i in input().split()]
CH,CW = [int(i)-1 for i in input().split()]
DH,DW= [int(i)-1 for i in input().split()]
g = [input() for i in range(H)]
vis = [[False]*W for i in range(H)]
deja = [[False]*W for i in range(H)]
dist = [[float('inf')]*W for i in range(H)]
dist[CH][CW] = 0
vis[CH][CW] = True
totreat.put((CH,CW))

while not totreat.empty():
	bfs()
	if not bloques.empty():
		bfs_magic()
	if vis[DH][DW]:
		print(dist[DH][DW])
		break
	

if not vis[DH][DW]: print("-1")
# ~ else:print(dist[DH][DW])

# ~ print("dist")
# ~ for d in dist:
	# ~ print(d)
# ~ print("vis")
# ~ for d in vis:
	# ~ print(d)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
# genzai=deque()
# wapu=deque()
genzai=[[c_h-1,c_w-1]]
wapu=[[c_h-1,c_w-1]]
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append([gyou,retu])
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.pop(0)
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.pop(0)
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.' and (not (_p) in d):
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=[[c_h-1,c_w-1]]
wapu=[[c_h-1,c_w-1]]
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append([gyou,retu])
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.pop(0)
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.pop(0)
    
    wapu_kaisuu+=1

print(map[d_h-1][d_w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

Ch += 1
Cw += 1
Dh += 1
Dw += 1

lim = 10**6

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

foo = [[-1 for _ in range(W+4)] for _ in range(H+4)]
rev = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      foo[k][j] = lim
      rev[k][j] = lim



foo[Ch][Cw] = 0
rev[Dh][Dw] = 0
jump = [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]
mv = [(1,0),(-1,0),(0,1),(0,-1)]
now = deque([])
new = deque([(Ch, Cw)])
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == 0:
      print(0)
      exit()
    else:
      if foo[mx][my] == lim:
        foo[mx][my] = 0
        new.append((mx, my))

now_rev = deque([])
new_rev = deque([(Dh,Dw)])
while len(new_rev) > 0:
  item = new_rev.pop()
  now_rev.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == lim:
      rev[mx][my] = 0
      new_rev.append((mx, my))


start = 0
while True:
  if len(now) == 0:
    print(-1)
    exit() 
  start += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if 0 <= rev[jx][jy] < lim:
        print(foo[x][y]+rev[jx][jy]+1)
        exit()
      else:
        if foo[jx][jy] > start:
          foo[jx][jy] = start
          new.append((jx,jy))
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if 0 <= rev[mx][my] < lim:
        print(foo[x][y] + rev[mx][my])
        exit()
      else:
        if foo[mx][my] == lim:
          foo[mx][my] = start
          new.append((mx, my))

  if len(now_rev) == 0:
    print(-1)
    exit() 
  while len(now_rev) > 0:
    item = now_rev.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if 0 <= foo[jx][jy] < lim:
        print(rev[x][y]+foo[jx][jy]+1)
        exit()
      else:
        if rev[jx][jy] > start:
          rev[jx][jy] = start
          new_rev.append((jx,jy))

  while len(new_rev) > 0:
    item = new_rev.pop()
    now_rev.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if 0 <= foo[mx][my] < lim:
        print(rev[x][y] + foo[mx][my])
        exit()
      else:
        if rev[mx][my] == lim:
          rev[mx][my] = start
          new_rev.append((mx, my))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while d != deque():
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        h, w, c = que.popleft()
        for mh, mw in move:  # 移動A: 歩いて移動
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c:
                visited[ch][cw] = c
                que.appendleft((ch, cw, c))
        for wh in range(-2, 3):  # 移動B: ワープ魔法
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c + 1:
                    visited[ch][cw] = c + 1
                    que.append((ch, cw, c + 1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
cost=[[-1 for i in range(W)] for j in range(H)]
queue = [[Ch-1, Cw-1] for j in range(1)]
queue2 = [[] for j in range(0)]
S=[[i,j] for j in range(0)]
cost[Ch-1][Cw-1]=0
costCount = 1
checkCount = 0
for i in range(H):
    S.append(list(input()))
while(cost[Dh-1][Dw-1]<0 and len(queue)>0):
    while(len(queue)>0):
        posX = queue[0][0]
        posY = queue[0][1]
        #print(posX,posY)
        queue2.append(queue.pop(0))
        if posX+1<H:
            if cost[posX+1][posY]<0 and S[posX+1][posY]==".":
                cost[posX+1][posY] = cost[posX][posY]
                queue.append([posX+1,posY])
        if posY+1<W:
            if cost[posX][posY+1]<0 and S[posX][posY+1]==".":
                cost[posX][posY+1] = cost[posX][posY]
                queue.append([posX,posY+1]) 
        if posX-1>=0:
            if cost[posX-1][posY]<0 and S[posX-1][posY]==".":
                cost[posX-1][posY] = cost[posX][posY]
                queue.append([posX-1,posY])
        if posY-1>=0:
            if cost[posX][posY-1]<0 and S[posX][posY-1]==".":
                cost[posX][posY-1] = cost[posX][posY]
                queue.append([posX,posY-1]) 
    #print(cost)
    for a in range(len(queue2)):
            i=queue2[a][0]
            j=queue2[a][1]
            if cost[i][j]>=0:
                for k in range(max(0,i-2), min(H,i+3)):
                    for l in range(max(0,j-2), min(W,j+3)):
                        if cost[k][l]<0 and S[k][l]==".":
                            cost[k][l] = costCount
                            queue.append([k,l])
    costCount+=1
#print(cost)
print(cost[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())#行,列
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [list(input()) for _ in range(h)]

seen = [[0]*w for _ in range(h)]
cost = [[-1]*w for _ in range(h)]
cost[C[0]-1][C[1]-1]=0
cost_base = 0
for i in range(h):
    for j in range(w):
        if S[i][j]=='#':
            cost[i][j]=-2

ok = True

q=deque()
q.append(C)
                
while len(q)>0:
    #移動A
    now = q.popleft()
    if seen[now[0]-1][now[1]-1] == 1:
        continue
    costnow = cost[now[0]-1][now[1]-1]
    seen[now[0]-1][now[1]-1] = 1

    for i in range(-1,2,2):
        if now[0]+i<1 or now[0]+i>h:
            continue
        if cost[now[0]+i-1][now[1]-1]==-1 or cost[now[0]+i-1][now[1]-1]>costnow:
            cost[now[0]+i-1][now[1]-1]=costnow
            q.appendleft([now[0]+i,now[1]])
    for i in range(-1,2,2):
        if now[1]+i<1 or now[1]+i>w:
            continue
        if cost[now[0]-1][now[1]+i-1]==-1 or cost[now[0]-1][now[1]+i-1]>costnow:
            cost[now[0]-1][now[1]+i-1]=costnow
            q.appendleft([now[0],now[1]+i])

    #移動B
    for i in range(-2,3):
        for j in range(-2,3):
            if now[0]+i<1 or now[0]+i>h:
                continue
            if now[1]+j<1 or now[1]+j>w:
                continue

            if cost[now[0]+i-1][now[1]+j-1]==-1:
                cost[now[0]+i-1][now[1]+j-1]=costnow+1
                q.append([now[0]+i,now[1]+j])

print(cost[D[0]-1][D[1]-1])