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
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :


                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if S[ny][nx]==".":
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]+1:
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)


            
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-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)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] != "#":
            if S[h+dh][w+dw] > S[h][w]:
                S[h+dh][w+dw] = S[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if S[h+wh][w+ww] > S[h][w] + 1:
                S[h+wh][w+ww] = S[h][w] + 1
                q.append((h+wh, w+ww))
 
if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    mxxx = 10**10
    score=[[mxxx]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(0,Sx,Sy))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        cs,x,y = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:

            score[y-1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y-1))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:


            score[y+1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y+1))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:

            score[y][x-1]=score[y][x]
            heapq.heappush(q,(cs,x-1,y))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:

            score[y][x+1]=score[y][x]
            heapq.heappush(q,(cs,x+1,y))


        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(cs+1,j,i))

    if score[Gy][Gx]==mxxx:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = sh-1,sw-1
gh,gw = map(int, sys.stdin.readline().rstrip("\n").split())
gh,gw = gh-1,gw-1
labyrinth = [ line.rstrip("\n") for line in sys.stdin ]
done = [[False]*w for _ in range(h)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
warp = [(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(2,1),(2,2),(1,2),(0,2),(-2,2),(-1,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(2,-1)]

d = deque()
d.append((sh,sw,0))
done[sh][sw] = True
warpmin = -1
while d:
    ph,pw,pwarp = d.popleft()
    if not done[ph][pw] :
        done[ph][pw] = True
    if ph == gh and pw == gw:
        warpmin = pwarp
        break
    for m in move:
        nh,nw = ph+m[0],pw+m[1]
        if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and (not done[nh][nw]):
            d.appendleft((nh,nw,pwarp))
    for m in warp:
        nh,nw = ph+m[0],pw+m[1]
        if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and (not done[nh][nw]):
            d.append((nh,nw,pwarp+1))
print(warpmin)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque
def bfs(x, y):
    ans = 0
    d = [[float('inf')]*w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                u = x + i
                v = y + j

                if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] > d[x][y]:
                    if abs(i) + abs(j) <= 1:
                        d[u][v] = min(d[x][y], d[u][v])
                    else:
                        d[u][v] = min(d[u][v], d[x][y] + 1)
                    queue.append((u, v))
    return d

d = bfs(ch, cw)
if d[dh][dw] == float('inf'):
    print(-1)
else:
    print(d[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w=[int(x) for x in input().split()]
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

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


done=[[float('inf') for i in range(w)] for j in range(h)]
move=[[-1,0],[1,0],[0,1],[0,-1]]
m1=[]
for i in range(-2,3):
  for j in range(-2,3):
    if i==0 and j==0:
      continue
    else:
      m1.append([i,j])

def bfs(x,y):
  ans=float('inf')
  que=[[x,y,0]]

  while(que):
    nx,ny,cnt = que.pop(0)
    done[ny][nx]=cnt

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)

    for dx,dy in move:
      mx,my = nx+dx,ny+dy
      if 0<=mx<w and 0<=my<h:
        if l[my][mx]=="." and (cnt<done[my][mx]):
          done[my][mx]=cnt
          que.append([mx,my,cnt])

        elif l[my][mx]=="#" and (cnt<done[my][mx]):
          for i,j in m1:
            if 0<=nx+i<w and 0<=ny+j<h and l[ny+j][nx+i]=="." and cnt+1<done[ny+j][nx+i]:
              done[ny+j][nx+i]=cnt+1
              que.append([nx+i,ny+j,cnt+1])
      
  return ans


ans1=bfs(cw-1,ch-1)

if ans1==float('inf'):
  print(-1)
else:
  print(ans1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
inf=10**4
H,W=map(int,input().split())
S=list(map(int,input().split()))
G=list(map(int,input().split()))
arr=[list(map(str,input())) for i in range(H)]
A=[(0,-1,0),(0,1,0),(-1,0,0),(1,0,0)]
B=[(0,-2,1),(0,2,1),(-2,0,1),(2,0,1),(-1,1,1),(-1,2,1),(-2,1,1),(-2,2,1),(-1,-1,1),(-1,-2,1),(-2,-1,1),(-2,-2,1),(1,1,1),(1,2,1),(2,1,1),(2,2,1),(1,-1,1),(1,-2,1),(2,-1,1),(2,-2,1)]
C=A+B
vist=[[0]*W for i in range(H)]
ans=[[inf]*W for i in range(H)]

d=[(0,S[0]-1,S[1]-1)]
ans[S[0]-1][S[1]-1]=0


while d:
    cost,x,y=heapq.heappop(d)
    
    if vist[x][y]==1:
        continue
    
    vist[x][y]=1
    
    for dx,dy,c in C:
        if H>x+dx>=0 and W>y+dy>=0:
           if vist[x+dx][y+dy]==0 and arr[x+dx][y+dy]==".":
            
                ans[x+dx][y+dy]=min(cost+c,ans[x+dx][y+dy])
                heapq.heappush(d,(ans[x+dx][y+dy],x+dx,y+dy))



if ans[G[0]-1][G[1]-1]==inf:
    print(-1)
else:
    print(ans[G[0]-1][G[1]-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [input() for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))

    while q:
        cnt = 0
        cost, px, py = heappop(q)
        if dp[px][py] < cost:
            continue
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e7

# class PriorityQueue:
#     """
#     優先度付きキューの
#     """
#     def __init__(self, heap):
#         self.heap = heap
#         heapify(self.heap)
    
#     def push(self, item):
#         heappush(self.heap, item)
    
#     def pop(self):
#         return heappop(self.heap)
    
#     def pushpop(self, item):
#         return heappushpop(self.heap, item)
    
#     def __call__(self):
#         return self.heap
    
#     def __len__(self):
#         return len(self.heap)
    
    

def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [["#"]*(W+2) for _ in range(H+2)]
    for i in range(1,1+H):
        tmp=list(input())
        for j in range(1,1+W):
            S[i][j]=tmp[j-1]

    idxs = []

    for row in range(1, H+1):
        for col in range(1, W+1):
            if S[row][col] == ".":
                idxs.append((row, col))

    dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    graph = {idx: deque() for idx in idxs}
    for x in range(1, H+1):
        for y in range(1, W+1):
            if S[x][y] == "#":
                continue
            idxs.append((x, y))
            for dx, dy in dxdy:
                if S[x+dx][y+dy] == ".":
                    graph[(x, y)].append((x+dx, y+dy, 0))
                    

    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if x+dx<1 or x+dx>H or y+dy<1 or y+dy>W:
                    continue
                if S[x+dx][y+dy] == ".":
                    graph[idx].append((x+dx, y+dy, 1))

    def dijkstra(adj, sx, sy):
        Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り

            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu

            Color[ux][uy] = 1 # uをVisitedに。

            if D[ux][uy] < min_cost:
                # 更新の必要なし.
                continue

            for adj_x, adj_y, adj_w in adj[(ux, uy)]:
                if not Color[adj_x][adj_y]: #訪問済みでないなら
                    if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                        D[adj_x][adj_y] = D[ux][uy] + adj_w
                        # P[adj_idx] = u
                        # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                        heappush(PQ, (D[adj_x][adj_y], adj_x, adj_y))
                        # PQ.push((D[adj_x][adj_y], adj_x, adj_y))
        return D
    D = dijkstra(graph, ch, cw)
    if D[dh][dw] == INF:
        print(-1)
    else:
        print(D[dh][dw])

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())

tobool = lambda s: s == "#"

S = [
  list(map(tobool, input())) for _ in range(H)
]
visited_m = [[False for w in range(W) ] for h in range(H)]
cost_m = [[math.inf for w in range(W) ] for h in range(H)]

def enum_moveA(Ch, Cw):
  return [(Ch-1, Cw), (Ch+1, Cw), (Ch, Cw-1), (Ch, Cw+1)]

def enum_moveB(Ch, Cw):
  return [
    (Ch-2, Cw-2), (Ch-2, Cw-1), (Ch-2, Cw), (Ch-2, Cw+1), (Ch-2, Cw+2),
    (Ch-1, Cw-2), (Ch-1, Cw-1), (Ch-1, Cw+1), (Ch-1, Cw+2),
    (Ch, Cw-2), (Ch, Cw+2),
    (Ch+1, Cw-2), (Ch+1, Cw-1), (Ch+1, Cw+1), (Ch+1, Cw+2),
    (Ch+2, Cw-2), (Ch+2, Cw-1), (Ch+2, Cw), (Ch+2, Cw+1), (Ch+2, Cw+2),
  ]

heap = []
heapq.heappush(heap, (0, Ch, Cw))
while True:
  if len(heap) == 0:
    break
  visited_m[Ch][Cw] = True
  c_cost, Ch, Cw = heapq.heappop(heap)
  if Ch == Dh and Cw == Dw:
    break
  for h, w in enum_moveA(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 0 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 0
        heapq.heappush(heap, (c_cost + 0, h, w))
        
  for h, w in enum_moveB(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 1 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 1
        heapq.heappush(heap, (c_cost + 1, h, w))
    
total_cost = cost_m[Dh][Dw]
if total_cost < math.inf:
  print(total_cost)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

S = [list(input()) for i in range(H)]

maze_visited = [[math.inf] * W for i in range(H)]

queue = deque([[C[0]-1, C[1]-1]])
maze_visited[C[0]-1][C[1]-1] = 0
while queue:
    y, x = queue.popleft()
    mv_cur = maze_visited[y][x]
    for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
        n_x, n_y = x + i, y + j
        if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
            mv_n = maze_visited[n_y][n_x]
            if mv_n > mv_cur:
                if S[n_y][n_x] == '.':
                    maze_visited[n_y][n_x] = mv_cur
                    queue.append([n_y, n_x])
    for i in range(-2, 3):
        for j in range(-2, 3):
            if abs(i) + abs(j) <= 1:
                continue
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur + 1:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur + 1
                        queue.append([n_y, n_x])

if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().rstrip().split(" "))
C = list(map(int,input().rstrip().split(" ")))
D = list(map(int,input().rstrip().split(" ")))
A = []
for i in range(H):
    A.append(list(input()))
warp = [[10 ** 9 for i in range(W)] for i in range(H)]

que = deque([[C[0] - 1,C[1] - 1]])
warp[C[0] - 1][C[1] - 1] = 0

while len(que) != 0:
    p = warp[que[0][0]][que[0][1]]
    for i in range(-2,3):
        for j in range(-2,3):
            if(0 <= que[0][0] + i < H and  0 <= que[0][1] + j < W):
                if(A[que[0][0] + i][que[0][1] + j] == "."):
                    if abs(i) + abs(j) <= 1:
                        if warp[que[0][0] + i][que[0][1] + j] > p:
                            warp[que[0][0] + i][que[0][1] + j] = p
                            que.append([que[0][0] + i,que[0][1] + j])
                    else:
                        if warp[que[0][0] + i][que[0][1] + j] > p + 1:
                            warp[que[0][0] + i][que[0][1] + j] = p + 1
                            que.append([que[0][0] + i,que[0][1] + j])
    que.popleft()
if warp[D[0] - 1][D[1] - 1] == 10 ** 9:warp[D[0] - 1][D[1] - 1] = -1
print(warp[D[0] - 1][D[1] - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

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

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
        
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i:
                continue
            if x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)

for _ in range(250):
    for i in nxt:
        if i[0]==dh and i[1]==dw:
            print(i[2])
            exit()
        rcl(i[0],i[1],i[2])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  return h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1

warp = 0
BFS_now = set()
BFS_now.add((Ch-1, Cw-1))
BFS_search = set()
BFS_search.add((Ch-1, Cw-1))
ij = [(-1,0),(0,-1),(0,1),(1,0)]

while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = set()
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.add((h+i,w+j))
          BFS_now.add((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_search = BFS_search_tmp.copy()
  BFS_now_tmp = set()
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.add((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp.copy()
  BFS_search = BFS_now_tmp.copy()
  warp += 1

print(A[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
Ch, Cw = [int(i) - 1 for i in input().split()]
Dh, Dw = [int(i) - 1 for i in input().split()]
S = np.array([list(input()) for _ in range(H)])
S = S == '.'
S

def update(h, w, value, table):
    if h < 0 or h >= table.shape[0]:
        return None
    if w < 0 or w >= table.shape[1]:
        return None
    return np.nanmin([value, table[h, w]])

cost = np.full_like(S, np.nan, dtype=float)
finish = np.full_like(S, False, dtype=bool)

cost[Dh, Dw] = 0
h, w = Dh, Dw

while(True):
    finish[h, w] = True
    for d_h in range(-2, 3):
        for d_w in range(-2, 3):
            _h, _w = h + d_h, w + d_w
            value = update(_h, _w, cost[h, w] + 1, cost)
            if value is not None and S[_h, _w]:
                cost[_h, _w] = value

    for d_h, d_w in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        _h, _w = h + d_h, w + d_w
        value = update(_h, _w, cost[h, w], cost)
        if value is not None and S[_h, _w]:
            cost[_h, _w] = value

    available_cost = np.where(~finish * ~np.isnan(cost) * S, 1, np.nan) * cost
    if np.isnan(available_cost).all():
        break
    idx = np.nanargmin(available_cost)
    h = idx // W
    w = idx - (W * h)


if np.isnan(cost[Ch, Cw]):
    print(-1)
else:
    print(int(cost[Ch, Cw]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append([nh, nw, cnt])
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy -= 1
sx -= 1
gy,gx = map(int,input().split())
grid = [0]*H
for i in range(H):
    grid[i] = input()
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done = [[0]*W for _ in range(H)]
done[sy][sx] = 1
walk_q = deque()
walk_q.append([sy,sx])
magic_q = deque()
magic_q.append([sy,sx])
def walk(y,x):
    for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= new_y < H and 0 <= new_x < W and grid[new_y][new_x] == '.':
            if cost[new_y][new_x] > cost[y][x]:
                cost[new_y][new_x] = cost[y][x]
                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])
                done[new_y][new_x] = 1
def magic(y,x):
    for y_add in [i for i in range(-2,3)]:
        for x_add in [i for i in range(-2,3)]:
            if 0 <= y+y_add < H and 0 <= x+x_add < W and grid[y+y_add][x+x_add] == '.':
                if cost[y+y_add][x+x_add] > cost[y][x]+1:
                    cost[y+y_add][x+x_add] = min(cost[y+y_add][x+x_add],cost[y][x]+1)
                    walk_q.append([y+y_add,x+x_add])
                    magic_q.append([y+y_add,x+x_add])
                    done[y+y_add][x+x_add] = 1

while walk_q or magic_q:
    while walk_q:
        y,x = walk_q.popleft()
        walk(y,x)
    while magic_q:
        y,x = magic_q.popleft()
        magic(y,x)
if not done[gy-1][gx-1]:
    print(-1)
else:
    print(cost[gy-1][gx-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h += 1
C_w += 1
D_h, D_w = map(int, input().split())
D_h += 1
D_w += 1
S_list = []

S_list.append('#' * (W + 4))
S_list.append('#' * (W + 4))
for h in range(H):
    S_tmp = '##'+input()+'##'
    S_list.append(S_tmp)
S_list.append('#' * (W + 4))
S_list.append('#' * (W + 4))

zahyo_h = C_h
zahyo_w = C_w
teni = 0

sabun_h = D_h - zahyo_h
sabun_w = D_w - zahyo_w
teni_max = abs(sabun_h) + abs(sabun_w)
finish_flg = False
while(teni <= teni_max):
    flg_w = False
    flg_h = False

    ## W
    if(sabun_w > 0):
        for w in range(sabun_w):
            if(S_list[zahyo_h][zahyo_w + 1] == '.'):
                zahyo_w += 1
                flg_w = True
            else:
                break
    elif(sabun_w < 0):
        for w in range(-(sabun_w)):
            if(S_list[zahyo_h][zahyo_w - 1] == '.'):
                zahyo_w -= 1
                flg_w = True
            else:
                break
    ## H
    if(sabun_h > 0):
        for h in range(sabun_h):
            if(S_list[zahyo_h + 1][zahyo_w] == '.'):
                zahyo_h += 1
                flg_h = True
            else:
                break
    elif(sabun_h < 0):
        for h in range(-(sabun_h)):
            if(S_list[zahyo_h - 1][zahyo_w] == '.'):
                zahyo_h -= 1
                flg_h = True
            else:
                break
    
    sabun_h = D_h - zahyo_h
    sabun_w = D_w - zahyo_w
    if((sabun_h == 0) and (sabun_w == 0)):
        finish_flg = True
        break

    ## teni
    teni_flg = False
    if(not(flg_w or flg_h)):
        for w in range(3):
            for h in range(3):
                if((w != 0) or (h != 0)):
                    if(sabun_h > 0) and (sabun_w > 0):
                        if(S_list[zahyo_h + h][zahyo_w + w] == '.'):
                            zahyo_h = zahyo_h + h
                            zahyo_w = zahyo_w + w
                            teni += 1
                            teni_flg = True
                    elif(sabun_h > 0) and (sabun_w < 0):
                        if(S_list[zahyo_h + h][zahyo_w - w] == '.'):
                            zahyo_h = zahyo_h + h
                            zahyo_w = zahyo_w - w
                            teni += 1
                            teni_flg = True
                    elif(sabun_h < 0) and (sabun_w > 0):
                        if(S_list[zahyo_h - h][zahyo_w + w] == '.'):
                            zahyo_h = zahyo_h - h
                            zahyo_w = zahyo_w + w
                            teni += 1
                            teni_flg = True
                    elif(sabun_h < 0) and (sabun_w < 0):
                        if(S_list[zahyo_h - h][zahyo_w - w] == '.'):
                            zahyo_h = zahyo_h - h
                            zahyo_w = zahyo_w - w
                            teni += 1
                            teni_flg = True
                        
                    if(teni_flg):
                        break
            if(teni_flg):
                break         

if(finish_flg):
    print(teni)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([c])
passed = set()
queued = set()
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()
        if (h,w) in passed:
            continue
        passed.add((h,w))
        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in queued and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))
                queued.add((nh,nw))

        for dh,dw in [
            [-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], 
        ]: 
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in nque and (nh,nw) not in queued and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)