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())
C = list(map(int,input().split()))
D = list(map(int,input().split()))

S = ["##" + input() + "##" for _ in range(H)]
for i in range(2):
    S.insert(0,"#"*(W+4))
    S.append("#"*(W+4))

INF = float("inf")
cost = [[INF for _ in range(W+4)] for _ in range(H+4)]
cost0 = deque()
ans = -1

cost0.append((C[0]+1, C[1]+1, 0))
cost[C[0]+1][C[1]+1] = 0

move = [(1,0), (0,1), (-1,0), (0,-1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

cost1 = deque()

while cost0:
    h,w,c = cost0.popleft()
    cost1.append((h,w,c))

    for i, j in move:
        dh = h+i
        dw = w+j
        if S[dh][dw] == "." and c < cost[dh][dw]:
            cost[dh][dw] = c
            cost0.appendleft((dh, dw, cost[dh][dw]))
    
    if len(cost0) == 0:
        while cost1:
            h, w, c = cost1.popleft()
            for i, j in warp:
                dh = h+i
                dw = w+j
                if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                    cost[dh][dw] = c+1
                    cost0.append((dh,dw, cost[dh][dw]))
    
    if cost[D[0]+1][D[1]+1] != INF:
        ans = cost[D[0]+1][D[1]+1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0<=i+ii and i+ii<h and 0<=j+jj and \
                j+jj<w and s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            if 0<=i+ii and i+ii<h and 0<=j+jj and \
                j+jj<w and s[i+ii][j+jj]=="#":
                if not ((i,j) in wpg):
                    wpg.append((i,j))        
#                print(i,j,g[i][j])
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
#qq=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()
#                for hk,wk in gg[hj][wj]:
#                    if parent[hk][wk] !=-1:
#                        continue
#                    parent[hk][wk]=(hj,wj)
#                    dist[hk][wk]=dist[hj][wj]+10**7
#                    qq.append((hk,wk))
#                    if hk==dh and wk==dw:
#                        print(dist[dh][dw]//(10**7))   
#                        sys.exit()
#        print("q3:",q)
    
#    print("qq:",qq)
    while qq:
        hi,wi = qq.popleft()
#        if parent[hi][wi]!=0 and parent[hi][wi]!=-1:
#            continue
        for hj,wj in gg[hi][wi]:
#       q.append((hi,wi))
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

#    for hj,wj in gg[hi][wi]:
#        if parent[hj][wj] !=-1:
#            continue
#        else:
#            parent[hj][wj]=(hi,wi)
#            dist[hj][wj]=dist[hi][wi]+10**7
#            q.append((hj,wj))
#            if hj==dh and wj==dw:
#                print(dist[dh][dw]//(10**7))   
#                sys.exit()
#    print("q2:",q)
    if len(q)==0:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
DH,DW = DH-1,DW-1
S=[]
for i in range(H):
    S.append(list(map(lambda x:0 if x=='.' else -1, input().strip())))

def walk(h,w,n):
    r = []
    q = deque([(h,w)])
    while q:
        x = q.pop()
        r.append(x)
        h,w = x
        if h == DH and w == DW:
            print(n-1)
            exit()
        if h > 0 and S[h-1][w] == 0:
            S[h-1][w] = n
            q.append((h-1,w))
        if h < H-1 and S[h+1][w] == 0:
            S[h+1][w] = n
            q.append((h+1,w))
        if w > 0 and S[h][w-1] == 0:
            S[h][w-1] = n
            q.append((h,w-1))
        if w < W-1 and S[h][w+1] == 0:
            S[h][w+1] = n
            q.append((h,w+1))
    return r

warp = 1
q = deque([(CH-1,CW-1)])
while len(q) > 0:
    n = []
    while len(q) > 0:
        h,w = q.pop()
        n+=walk(h,w,warp)
    warp += 1
    if len(n) == 0:
        break
    for h,w in n:
        for ah in range(max(0,h-2),min(H,h+3)):
            for aw in range(max(0,w-2),min(W,w+3)):
                if ah == DH and aw == DW:
                    print(warp-1)
                    exit()
                if S[ah][aw] == 0:
                    S[ah][aw] = warp
                    q.append((ah,aw))

print(-1)

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())
m=[input()for _ in[0]*h]
ch-=1;cw-=1;dh-=1;dw-=1;
dist=[[1e9]*w for _ in[0]*h]
dist[ch][cw]=0
from collections import deque
q=deque([(ch,cw)])
e=(-2,-1,0,1,2)
while len(q):
	i,j=q.popleft()
	d=dist[i][j]
	for u,v in zip((-1,0,1,0),(0,-1,0,1)):
		ni,nj=i+u,j+v
		if 0>ni or ni>=h or 0>nj or nj>=w:continue
		if m[ni][nj]=='#':continue
		if dist[ni][nj]<=d:continue
		dist[ni][nj]=d
		q.appendleft((ni,nj))
	for s in e:
		for t in e:
			ni,nj=i+s,j+t
			if 0>ni or ni>=h or 0>nj or nj>=w:continue
			if m[ni][nj]=='#':continue
			if dist[ni][nj]<=d+1:continue
			dist[ni][nj]=d+1
			if q.count((ni,nj))==0:q.append((ni,nj))
r=dist[dh][dw]
print(r if r!=1e9 else-1)

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())
m=[input()for _ in[0]*h]
ch-=1;cw-=1;dh-=1;dw-=1;
dist=[[1e9]*w for _ in[0]*h]
dist[ch][cw]=0
from collections import deque
q=deque([(ch,cw)])
e=(-2,-1,0,1,2)
while len(q):
	i,j=q.popleft()
	d=dist[i][j]
	for u,v in zip((-1,0,1,0),(0,-1,0,1)):
		ni,nj=i+u,j+v
		if 0>ni or ni>=h or 0>nj or nj>=w:continue
		if m[ni][nj]=='#':continue
		if dist[ni][nj]<=d:continue
		dist[ni][nj]=d
		q.appendleft((ni,nj))
	for s in e:
		for t in e:
			ni,nj=i+s,j+t
			if 0>ni or ni>=h or 0>nj or nj>=w:continue
			if m[ni][nj]=='#':continue
			if dist[ni][nj]<=d+1:continue
			dist[ni][nj]=d+1
			q.append((ni,nj))
r=dist[dh][dw]
print(r if r!=1e9 else-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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

maze = [input() for _ in range(H)]

INF = 10 ** 12

score = np.zeros((H, W), dtype=int)
score[:, :] = INF
score[Ch, Cw] = 0

candidates = deque()
candidates.append((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        s = score[h, w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] > s:
            score[y, x] = s
            candidates.appendleft((y, x))
    # warp
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        s = score[h, w]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y, x] > s + 1:
            score[y, x] = s + 1
            candidates.append((y, x))

if score[Dh, Dw] == INF:
    print(-1)
else:
    print (score[Dh, Dw])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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

maze = [input() for _ in range(H)]

INF = 10 ** 12

score = np.zeros((H, W), dtype=int)
score[:, :] = INF
score[Ch, Cw] = 0

#visited = np.zeros((H, W), dtype=bool)

candidates = deque()
candidates.append((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] > score[h, w]:
            score[y, x] = score[h, w]
            candidates.appendleft((y, x))
    # warp
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y, x] > score[h, w] + 1:
            score[y, x] = score[h, w] + 1
            candidates.append((y, x))

if score[Dh, Dw] == INF:
    print(-1)
else:
    print (score[Dh, Dw])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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

maze = []
for i in range(H):
    maze.append(input())

INF = 10 ** 12

score = np.zeros((H, W), dtype=int)
score[:, :] = INF
score[Ch, Cw] = 0

#visited = np.zeros((H, W), dtype=bool)

candidates = deque()
candidates.append((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while candidates:
    h, w = candidates.popleft()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] > score[h, w]:
            score[y, x] = score[h, w]
            candidates.appendleft((y, x))
    # warp
    #if not moved: 
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y, x] > score[h, w] + 1:
            score[y, x] = score[h, w] + 1
            candidates.append((y, x))

if score[Dh, Dw] == INF:
    print(-1)
else:
    print (score[Dh, Dw])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from queue import Queue

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

maze = []
for i in range(H):
    maze.append(input())

INF = 10 ** 12

score = np.zeros((H, W), dtype=int)
score[:, :] = INF

score[Ch, Cw] = 0

#visited = np.zeros((H, W), dtype=bool)

candidates = Queue()
candidates.put((Ch, Cw))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while not candidates.empty():
    h, w = candidates.get()
    # move
    for dh, dw in walk:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] > score[h, w]:
            score[y, x] = score[h, w]
            candidates.put((y, x))
    # warp
    #if not moved: 
    for dh, dw in warp:
        y = h + dh
        x = w + dw
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue
        if maze[y][x] == '.' and score[y, x] > score[h, w] + 1:
            score[y, x] = score[h, w] + 1
            candidates.put((y, x))

if score[Dh, Dw] == INF:
    print(-1)
else:
    print (score[Dh, Dw])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = []
warp_cnts = [[None]*(W) for j in range(H)]
for i in range(H):
  maze.append(input())

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)
        

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  mv_b_tgs=[]
  for tg in mv_a_tgs:
    mv_a(tg[0],tg[1])
  mv_a_tgs = []
  for wp in mv_b_tgs:
    mv_b(wp[0],wp[1])
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
[h, w] = list(map(int, input().split()))
[si, sj] = map(int, input().split())
[ti, tj] = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
mapping = [input() for i in range(h)]

INF = 1e9

map_num = [[INF] * w for i in range(h)]

q = deque([])

map_num[si][sj] = 0
q.append([si, sj])
while q:
    [i, j] = q.popleft()
    d = map_num[i][j]
    if d != map_num[i][j]:
        continue
    for v in range(4):
        ni = i
        nj = j
        if v == 0:
            ni = i - 1
        elif v == 1:
            ni = i + 1
        elif v == 2:
            nj = j - 1
        else:
            nj = j + 1
        if (ni < 0 or ni >= h or nj < 0 or nj >= w):
            continue
        elif mapping[ni][nj] == '#':
            continue
        elif map_num[ni][nj] <= d:
            continue
        map_num[ni][nj] = d
        q.appendleft([ni, nj])
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej
            if (ni < 0 or ni >= h or nj < 0 or nj >= w):
                continue
            elif mapping[ni][nj] == '#':
                continue
            elif map_num[ni][nj] <= d+1:
                continue
            map_num[ni][nj] = d+1
            q.append([ni, nj])

ans = map_num[ti][tj]
if (ans == INF):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
[h, w] = list(map(int, input().split()))
[si, sj] = map(int, input().split())
[ti, tj] = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
mapping = [input() for i in range(h)]

INF = 1e9

map_num = [[INF] * w for i in range(h)]

q = deque([])

map_num[si][sj] = 0
q.append([si, sj])
while q:
    [i, j] = q.popleft()
    d = map_num[i][j]
    if d != map_num[i][j]:
        continue
    for v in range(4):
        ni = i
        nj = j
        if v == 0:
            ni = i - 1
        elif v == 1:
            ni = i + 1
        elif v == 2:
            nj = j - 1
        else:
            nj = j + 1
        if (ni < 0 or ni >= h or nj < 0 or nj >= w):
            continue
        if mapping[ni][nj] == '#':
            continue
        if map_num[ni][nj] <= d:
            continue
        map_num[ni][nj] = d
        q.appendleft([ni, nj])
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej
            if (ni < 0 or ni >= h or nj < 0 or nj >= w):
                continue
            if mapping[ni][nj] == '#':
                continue
            if map_num[ni][nj] <= d+1:
                continue
            map_num[ni][nj] = d+1
            q.append([ni, nj])

ans = map_num[ti][tj]
if (ans == INF):
    ans = -1
print(ans)

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())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w:
          if stage[y][x] == '.' and check[y][x]:
            check[y][x] = 0
            queue.append((y,x))
            searched_temp.append((y,x))
          
  if len(queue) == 0:
    print(-1)
    break

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())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w and stage[y][x] == '.' and check[y][x]:
          check[y][x] = 0
          queue.append((y,x))
          searched_temp.append((y,x))
  if len(queue) == 0:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

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

def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	rows, cols = rli()
	r0, c0 = rli(); r0 -= 1; c0 -= 1;
	r1, c1 = rli(); r1 -= 1; c1 -= 1;
	G = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "#": 
				row.append(1)
			else:
				row.append(0)
		G.append(row)

	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols	
	seen = defaultdict(lambda: False)
	Q = [] #(num magics, r, c)
	heappush(Q, (0, r0, c0))
	ans = INF
	while Q:
		magics, r, c = heappop(Q)
		if seen[(r, c)]: continue
		seen[(r, c)] = True
		if r == r1 and c == c1:
			ans = magics
			break
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr, nc = r + dr, c + dc 
				if not inside(nr, nc) or G[nr][nc] == 1 or seen[(nr, nc)]: continue
				n_magics = magics 
				if abs(dr) + abs(dc) > 1:
					n_magics += 1
				heappush(Q, (n_magics, nr, nc))
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()

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())
s = [list(input()) for _ in range(h)]

stack = deque()
stack.append([ch-1,cw-1])
INF=10**12
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0] + dxdy]:
            warp += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

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

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

s = []
for i in range(h): s.append(list(input()))

inf = int(1e9)
dist = [[inf for j in range(w)] for i in range(h)]
dist[ch][cw] = 0

q = deque()
q.append([ch,cw])

while len(q) != 0:
    i, j = map(int, q.popleft())
    d = dist[i][j]
    
    for v in range(4):
        ni = i + dx[v]
        nj = j + dy[v]

        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        
        if s[ni][nj] == "#":
            continue

        if dist[ni][nj] <= d:
            continue
        
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej

            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
        
            if s[ni][nj] == "#":
                continue

            if dist[ni][nj] <= d+1:
                continue

            dist[ni][nj] = d+1
            q.append([ni, nj])

ans = dist[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) + 1, input().split()))
    G = list(map(lambda x: int(x) + 1, input().split()))
    A = ['#' * (w + 4)] * 2 + ['##' + input() + '##' for _ in range(h)] + ['#' * (w + 4)] * 2
    INF = 1000000
    score = [[INF] * (w + 2) for _ in range(h + 2)]
    score[S[0]][S[1]] = 0
    stack = deque([S])
    walk = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warp = tuple((i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in (walk + ((0, 0), )))
    visited = set()
    while stack:
        y, x = stack.popleft()
        if (y, x) in visited:
            continue
        else:
            visited.add((y, x))
        for dx, dy in walk:
            X = x + dx
            Y = y + dy
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x]):
                stack.appendleft([Y, X])
                score[Y][X] = s
        for i, j in warp:
            X = x + j
            Y = y + i
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x] + 1):
                stack.append([Y, X])
                score[Y][X] = s
    print(ans if (ans := score[G[0]][G[1]]) != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) + 1, input().split()))
    G = list(map(lambda x: int(x) + 1, input().split()))
    A = [['#'] * (w + 4)] * 2 + [['#', '#'] + list(input()) + ['#', '#'] for _ in range(h)] + [['#'] * (w + 4)] * 2
    INF = 100000000
    score = [[INF] * (w + 2) for _ in range(h + 2)]
    score[S[0]][S[1]] = 0
    stack = deque([S])
    dxy = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while stack:
        y, x = stack.popleft()
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x]):
                stack.appendleft([Y, X])
                score[Y][X] = s
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + j
                Y = y + i
                if A[Y][X] == '#': continue
                if score[Y][X] > (s := score[y][x]) + 1:
                    stack.append([Y, X])
                    score[Y][X] = s + 1
    print(ans if (ans := score[G[0]][G[1]]) != INF else -1)

if __name__ == '__main__':
    main()

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())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [(ch,cw)]
searched_temp = [(ch,cw)]
count = 0

while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()

    if stage[v[0]-1][v[1]] == '.' and (v[0]-1,v[1]) not in check:
      queue.append((v[0]-1,v[1]))
      check.append((v[0]-1,v[1]))
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and (v[0]+1,v[1]) not in check:
      queue.append((v[0]+1,v[1]))
      check.append((v[0]+1,v[1]))
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and (v[0],v[1]-1) not in check:
      queue.append((v[0],v[1]-1))
      check.append((v[0],v[1]-1))
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and (v[0],v[1]+1) not in check:
      queue.append((v[0],v[1]+1))
      check.append((v[0],v[1]+1))
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w and stage[y][x] == '.' and (y,x) not in check:
          check.append((y,x))
          queue.append((y,x))
          searched_temp.append((y,x))
  if len(queue) == 0:
    print(-1)
    break

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = []
for i in range(H):
    S.append(input())

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.appendleft((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)