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:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase
from collections import deque

# %% define phase
global afx
global afy
global ans
ans = 0

def check(s, x, y, o, cnt):
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        if s[x+i][y+j] == '.':
            o.append([x+i, y+j, cnt])
            s[x+i][y+j] = str(cnt)
    return o, s

def wcheck(s, x, y, o, cnt):
    for i in range(5):
        a = i-2
        for j in range(5):
            b = j-2
#            if x+a>=0 and y+b>=0 and \
#            x+a<=h+2 and y+b<=w+2 and\
#            s[x+a][y+j] == '.':
            if s[x+a][y+b] == '.':
                if [x+a, y+b] not in o:
                    o.append([x+a, y+b, cnt+1])    
    return o
    
def bfs(s, x, y, h, w):
    cnt = 0
    s[x][y] = str(cnt)
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, cnt] = wf.popleft()
        f.append([x, y, cnt])
        while f:
            [x, y, cnt] = f.popleft()
            if [x, y] in wf:
                wf.remove([x, y])
            if [x, y] == [h, w]:
                wf.clear()
                return cnt
            f, s = check(s, x, y, f, cnt)
            wf = wcheck(s, x, y, wf, cnt)
    
    return -1

    
    

# %% input phase
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
ch += 1
cw += 1
dh, dw = list(map(int, input().split()))
dh += 1
dw += 1
s = [[] for _ in range(h+4)]
s[0] = list('#'*(w+4))
s[1] = list('#'*(w+4))
for i in range(h):
    si = input()
    s[i+2] = list('##' + si + '##')
s[h+2] = list('#'*(w+4))
s[h+3] = list('#'*(w+4))

# %% process phase
ans = bfs(s, ch, cw, dh, dw)

    

# %%output phase
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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)
    count=0
    flug=True
    while flug==True:
        flug=False
        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 k in range(N):
            
            for j in range(M):
                if seen[k][j]==count:
                    for i in range(20):
                        nx=j+ddx[i]
                        ny=k+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[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                                
                    flug=True
                    
        count+=1

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

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())
inf = 10**10

ch -= 1
cw -= 1
dh -= 1
dw -= 1

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
bomb_count = 0

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]

    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#":
            continue
        else:
            if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                if lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    que.appendleft((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

if lin[dh][dw] == inf:
    print(-1)
else:
    print(lin[dh][dw])

Submission status: Time Limit Exceeded

Solution code:

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

def dist(x1, y1, x2, y2):
    return (x1-x2) ** 2 + (y1-y2) ** 2

import heapq
seen = set()
queue = [(0, dist(CH-1, CW-1, DH-1, DW-1), CH-1, CW-1)]



while queue:
    move, _, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            if (i,j) in [(-1, 0), (1, 0), (0,0), (0, -1), (0, 1)]:
                continue
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))

print(-1)

Submission status: Time Limit Exceeded

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

def solve():
    import sys
    from collections import deque
    import heapq

    H, W = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = Ch-1, Cw-1
    Dh, Dw = list(map(int, sys.stdin.readline().split()))
    Dh, Dw = Dh-1, Dw-1
    S = []
    for _ in range(H):
        s = input()
        S.append(list(s))

    que = []
    heapq.heapify(que)
    heapq.heappush(que, [0, Ch+Cw*(10**4)])  # [ワープ回数, 座標]
    visited = set()
    while len(que) != 0:
        n, yx = heapq.heappop(que)
        y, x = yx%(10**4), yx//(10**4)
        visited.add((y, x))

        # ゴールか？
        if y == Dh and x == Dw:
            print(n)
            return

        # 上下左右移動可能ならばqueに入れる
        for ny, nx in ([y-1, x], [y+1, x], [y, x-1], [y, x+1]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n, ny+nx*(10**4)])
        # ワープ可能位置をqueに入れる
        for ny, nx in ([y-2, x-2], [y-2, x-1], [y-2, x], [y-2, x+1], [y-2, x+2],
                       [y-1, x-2], [y-1, x-1], [y-1, x+1], [y-1, x+2],
                       [y, x-2], [y, x+2],
                       [y+2, x-2], [y+2, x-1], [y+2, x], [y+2, x+1], [y+2, x+2],
                       [y+1, x-2], [y+1, x-1], [y+1, x+1], [y+1, x+2]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n+1, ny+nx*(10**4)])

    # ゴールはたどり着かなかったよ・・・
    print(-1)
    return


def solve2():
    """TLE"""
    import sys
    from collections import deque
    import heapq

    H, W = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = Ch-1, Cw-1
    Dh, Dw = list(map(int, sys.stdin.readline().split()))
    Dh, Dw = Dh-1, Dw-1
    S = []
    for _ in range(H):
        s = input()
        S.append(list(s))

    que = []
    heapq.heapify(que)
    heapq.heappush(que, [0, Ch, Cw])  # [ワープ回数, h座標, w座標]
    visited = set()
    while len(que) != 0:
        n, y, x = heapq.heappop(que)
        visited.add((y, x))

        # ゴールか？
        if y == Dh and x == Dw:
            print(n)
            return

        # 上下左右移動可能ならばqueに入れる
        for ny, nx in ([y-1, x], [y+1, x], [y, x-1], [y, x+1]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n, ny, nx])
        # ワープ可能位置をqueに入れる
        for ny, nx in ([y-2, x-2], [y-2, x-1], [y-2, x], [y-2, x+1], [y-2, x+2],
                       [y-1, x-2], [y-1, x-1], [y-1, x+1], [y-1, x+2],
                       [y, x-2], [y, x+2],
                       [y+2, x-2], [y+2, x-1], [y+2, x], [y+2, x+1], [y+2, x+2],
                       [y+1, x-2], [y+1, x-1], [y+1, x+1], [y+1, x+2]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n+1, ny, nx])

    # ゴールはたどり着かなかったよ・・・
    print(-1)
    return


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

move = [[0,1], [0,-1], [1,0], [-1,0]]

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch+1, cw+1, dh+1, dw+1

s =[[-1 for j in range(w+4)] for i in range(h+4)]

for i in range(h):
  a = input()
  for j in range(2, w+2):
    s[i+2][j] = w*h+1 if a[j-2]=='.' else -1

    
#for i in s:
#  print(i)
q1 = deque([[ch,cw]])
s[ch][cw] = 0
while(s[dh][dw] == w*h+1 and q1):
  q2 = q1.copy()
  while q1:
    now = q1.popleft()
    nows = s[now[0]][now[1]]
    
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] == w*h+1):
        s[nh][nw] = nows
        q1.append([nh, nw])
        q2.append([nh, nw])
 
  if(s[dh][dw] != w*h+1):
    break
    
  while q2:
    now = q2.popleft()
    nows = s[now[0]][now[1]]
    
    for i in range(-2,3):
      for j in range(-2,3):
        nh, nw = now[0]+i, now[1]+j
        if(s[nh][nw] == w*h+1):
          s[nh][nw] = nows+1
          q1.append([nh, nw])

if(s[dh][dw] == w*h+1):
  print(-1)
else:
  print(s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(x, y):
    q = queue.Queue()
    q.put([x,y])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        if nowx ==  D1 - 1 and nowy == D2 -1:
            return True
        if 0 < nowy and m[nowx][nowy -1] == '.' and M[nowx][nowy -1] == -1:
            M[nowx][nowy -1] = c
            q.put([nowx,nowy-1])
        if W-1 > nowy and m[nowx][nowy +1] == '.' and M[nowx][nowy +1] == -1:
            M[nowx][nowy +1] = c
            q.put([nowx,nowy+1])
        if 0 < nowx and m[nowx - 1][nowy] == '.'and M[nowx - 1][nowy] == -1:
            M[nowx - 1][nowy] = c
            q.put([nowx - 1,nowy])
        if H - 1 > nowx and m[nowx + 1][nowy] == '.'and M[nowx + 1][nowy] == -1:
            M[nowx + 1][nowy] = c
            q.put([nowx + 1,nowy])
    return False



def jump():
    for i in range (H):
        for j in range (W):
            if M[i][j] == c:
                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 M[k][l] == -1 and m[k][l] == '.':
                            Q.put([k,l])
                            M[k][l] = c+1




H,W = map(int,input().split())
C1,C2 =map(int,input().split())
D1,D2 = map(int,input().split())

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



M = [[-1 for i in range (W)] for j in range (H)]
c = 0
Q = queue.Queue()

Q.put([C1-1,C2-1])
M[C1-1][C2-1] = c
flag = False
f2 = False
while True:
    if Q.empty():
        print(-1)
        f2 = True
        break
    while not Q.empty():
        x,y = Q.get()
        if bfs(x,y) == True:
            flag = True
            break
    if flag == True:
        break
    else:
        jump()
        c += 1

if not f2:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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)
    count=0
    flug=True
    while flug==True:
        flug=False
        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 k in range(N):
            
            for j in range(M):
                if seen[k][j]==count:
                    for i in range(20):
                        nx=j+ddx[i]
                        ny=k+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[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                                elif seen[ny][nx] >seen[k][j]+1:
                                    seen[ny][nx] =seen[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                    flug=True
                    
        count+=1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10 ** 9

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())
S = [list(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


"""h = []
heapq.heappush(h, (0, Ch, Cw))"""

q = deque()
q.append((0, Ch, Cw))
S[Ch][Cw] = 0

while len(q) != 0:
    d, nh, nw = q.popleft()
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            flag = False
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
                flag = True
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        if flag:
                            q.appendleft((newd, newh, neww))
                        else:
                            q.append((newd, newh, neww))   
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen = set()
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                return now_count
            # cost 0 でたどり着けるマス
            maze[now_y][now_x] == '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if maze[ny][nx] == '#':
                    continue
                maze[ny][nx] = '#'
                dq.appendleft((ny, nx, now_count))
            # cost 1 でたどり着けるマス
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    if dx == dy == 0: continue
                    nx = now_x + dx
                    ny = now_y + dy
                    if maze[ny][nx] == '#':
                        continue
                    dq.append((ny, nx, now_count+1))
        return None

    res = bfs(maze, ch+1, cw+1)
    if res is not None:
        print(res)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-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()
    
    if s[y][x]=='#':
        return
    
    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 or 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)


while nxt:
    i=nxt.pop(0)
    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:

from collections import deque


H, W = [int(x) for x in input().split()]
Ch, Cw = [int(x) - 1 for x in input().split()]
Dh, Dw = [int(x) - 1 for x in input().split()]

warp_list = [(-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)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([-1] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = -1
while queue:
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] == -1:
            return True
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.popleft()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer == -1:
            answer = use_magic
        elif answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        do_warp = False

    if do_warp:
        for y, x in warp_list:
            warp_h = now_h + y
            warp_w = now_w + x

            if maze_check(warp_h, warp_w, use_magic+1):
                queue.appendleft((warp_h, warp_w, use_magic+1))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

# ワープを最低で何回使うか
# 上下左右2つ向こうまでの範囲内でワープできる
# 隣接する'.'が領域

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

pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 歩いて移動
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            # 0-1 bfs
            # 先頭に置く
            pos.appendleft([ny, nx])
            dp[ny][nx] = dp[y][x]
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            # 歩いて移動不可能でないと使わない
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]

  DD =  [(-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) ]

  while que:
    y,x = que.popleft()
    flag = 0
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "#"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]
          que.append([y+j,x+i])
        elif(dist>G[y][x]):
          G[y+j][x+i] = G[y][x]
          que.append([y+j,x+i])
      else:
        flag = 1
      if(flag == 1):
          flag = 0
          for k,l in DD:
              if(x+k<0 or y+l<0 or x+k>W-1 or y+l>H-1):
                  continue
              dist = G[y+l][x+k]
              #print(G[y][x])
              if(G[y+l][x+k] != "#"):
                  if(type(G[y+l][x+k]) is str):
                      G[y+l][x+k] = G[y][x]+1
                      que.appendleft([y+l,x+k])
                  elif(dist>G[y][x]+1):
                      G[y+l][x+k] = G[y][x]+1
                      que.appendleft([y+l,x+k])

sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H, W = map(int, input().split())
magicY, magicX = map(int, input().split())
goalY, goalX = map(int, input().split())
G = [list(input()) for i in range(H)]
G[magicY-1][magicX-1] = 0
ans = 0

#print(G[magicX-1][magicY-1])

bfs(magicX-1, magicY-1)

if(G[goalY-1][goalX-1]=="."):
    print(-1)
else:
    print(G[goalY-1][goalX-1])

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
sx, sy = map(int,input().split())
gx, gy = map(int,input().split())
S = [input() for i in range(h)]

sx-=1
sy-=1
gx-=1
gy-=1

A = [(-1,0),(1,0),(0,-1),(0,1)]
B = []
for i in range(-2,3):
    for j in range(-2,3):
        if i!= 0 or j!=0:
            B.append((i,j))
# print(B)

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

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

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            for a in A:
                ai = i+a[0]
                aj = j+a[1]
                if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                    M[i*w+j].append((ai*w+aj, 0))
            for b in B:
                bi = i+b[0]
                bj = j+b[1]
                if 0 <= bi < h and 0 <= bj < w and S[bi][bj] == ".":
                    M[i*w+j].append((bi*w+bj,1))


# for i in range(len(C)):

#     M[C[i][0]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

n = h*w

import heapq

big = 10**9
D = [big] * n  # 頂点0からの距離
P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
D[sx*w+sy] = 0
V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
Q = []  # 優先度付きキュー
for v in range(n):
    heapq.heappush(Q, (D[v], v))

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            # print(v)
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, (alt, v))
# print(D)
ans = D[gx*w+gy]
if ans > 10**7:
    ans = -1
print(ans)