Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
slist = [input() for i in range(h)]

if ch == dh and dw == cw:
    print(0)
    exit()

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo = [[False for i in range(w)] for j in range(h)]
memo[ch - 1][cw - 1] = True
ans = float("inf")

while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        memo_que.append([sh, sw, count])
        #print(sh, sw, count)
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    print(count)
                    exit()
                if memo[ph + sh][pw + sw]:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[ph + sh][pw + sw] = True
                    memo_que.append([sh + ph, sw + pw, count])

    for sh, sw, count in memo_que:
        #print("w", sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if sh + ph == dh - 1 and sw + pw == dw - 1:
                            print(count + 1)
                            exit()
                        if memo[ph + sh][pw + sw]:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[ph + sh][pw + sw] = True


print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline
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 = [readline().rstrip() for _ in range(H)]

visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])

while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    que = deque()

    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))#ここもスタートの座標に変えること

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

    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]
        no_magic = set()#魔法を使わずに行ける

        for i,j in zip(dx,dy):
            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 lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        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 lin[nx][ny] > lin[x][y]+1 and (i,j) not in [[-1,0],[1,0],[0,-1],[0,1]]:
                    que.appendleft((nx,ny))
                    lin[nx][ny] = lin[x][y]+1# 魔法を使っていける

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny)) 
    return -1
H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
cx-=1;cy-=1;dx-=1;dy-=1
B = []
for _ in range(H):
    B.append(input().strip())

D = [0]*(H*W)
bb = -1
t = 0
t2c = dict()
for i in range(H):
    for j in range(W):
        if B[i][j] == "#":
            D[i*W+j] = bb
            continue
        if D[i*W+j]>0:
            continue
        t += 1
        t2c[t] = set()
        stack = [(i, j)]
        while stack:
            u, v = stack.pop()
            D[W*u+v] = t
            t2c[t].add((u, v))
            for x, y in [(u+1, v), (u-1, v), (u, v-1), (u, v+1)]:
                if x >= H or x<0:
                    continue
                if y >= W or y<0:
                    continue
                if B[x][y] == "#":
                    D[x*W+y] = bb
                    continue
                if D[x*W+y]:
                    continue
                stack.append((x, y))
depth = 0
cs = [D[cx*W+cy]]
tt = D[dx*W+dy]
vs = set([cs[0]])
if tt in vs:
    print(0)
    sys.exit()
while True:
    depth += 1
    nexts = []
    for c in cs:
        for i, j in t2c[c]:
            for ii in range(max(0, i-2), min(i+3, H)):
                for jj in range(max(0, j-2), min(j+3, W)):
                    if B[ii][jj] == "#":
                        continue
                    if D[ii*W+jj] in vs:
                        continue
                    nexts.append(D[ii*W+jj])
                    if D[ii*W+jj] == tt:
                        print(depth)
                        sys.exit()
    cs = nexts
    if not cs:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import sys
import os
from operator import mul
from collections import deque


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    ans = -1
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])
    que2.append((sx, sy))

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    while que: 
        while que:
            p = que.popleft()
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                break

            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動可否判定、d[nx][ny] == INF であれば訪れたことがない
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p までのワープ回数で確定する
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
                # 移動できない場合はワープ候補
                else:
                    que2.append((p[0], p[1]))
        # print('after que: ',d)
        # dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        # dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            # for i in range(20):
            for dxi in range(-2,3):
                for dyi in range(-2,3):
                    nx = p[0] + dxi
                    ny = p[1] + dyi
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                        # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                        que.append((nx, ny))
                        d[nx][ny] = d[p[0]][p[1]]+1  
        # print('after que2: ',d)  
    return ans

print(bfs())

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())
S = [list(input()) for i in range(H)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import heapq

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

def bfs(ch,cw):
    q = []
    S[ch][cw] = 0
    cd = 0
    heapq.heappush(q,(cd,[ch,cw]))
    while q:
        cd,p = heapq.heappop(q)
        if p[0]==dh and p[1]==dw:
            break
            
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > cd:
                S[next_p[0]][next_p[1]] = cd
                heapq.heappush(q,(cd,next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > cd+1:
                    S[next_p[0]][next_p[1]] = cd+1
                    heapq.heappush(q,(cd+1,next_p))
                    
            
    return 
        
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 = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    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]='#'
    # 四方を見る
    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)
    #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])
                s[y+i][x+j]=now+1


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
import math
import copy

def main():
    hh,ww = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    maze=[list(input()) for l in range(hh)]

    # Maze preprocess
    for y in range(hh):
        for x in range(ww):
            if maze[y][x]=='.':
                maze[y][x]=math.inf
            elif maze[y][x] == '#':
                maze[y][x]=int(-1)

    maze[ch-1][cw-1] = 0
    que = deque([[ch-1, cw-1]])
#    print(que)
    while que:
#        print(que, maze)
        current_hh, current_ww = que.popleft()
        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                #print([i,j])
                if i == 0 and j == 0:
                    continue
                next_hh, next_ww = current_hh + i, current_ww + j
                if (next_hh >= 0) & (next_ww >= 0) & (next_hh < hh) & (next_ww < ww):
                    dist = maze[next_hh][next_ww]
                    #print([next_hh,next_ww])
                    if dist != -1:
                        if abs(i) == 2 or abs(j) == 2 or i*j != 0:
                            if (dist > maze[current_hh][current_ww] + 1) :
                                maze[next_hh][next_ww] = maze[current_hh][current_ww] + 1
                                que.append([next_hh, next_ww])
                        else:
                            if (dist > maze[current_hh][current_ww]):
                                maze[next_hh][next_ww] = maze[current_hh][current_ww]
                                que.append([next_hh, next_ww])

    mydist = maze[dh-1][dw-1]
    if mydist == math.inf:
        mydist = -1
    print(mydist)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [list(input()) for i in range(H)]
INF = float("inf")

distance = [[INF]*W for i in range(H)]
Q = deque([[C_h,C_w,0]])
K = deque([])
while Q:
    while Q:
        k = 0
        h,w,d = Q.popleft()
        if d >= distance[h][w]:
            continue
        distance[h][w] = d
        for i_h,i_w in [[h+1,w],[h-1,w],[h,w+1],[h,w-1]]:
            if min(i_h,i_w)<0 or i_h >= H or i_w >= W:
                if k==0:
                    K.append([h,w,d+1])
                    k += 1
                continue
            if S[i_h][i_w] != "#":
                Q.append([i_h,i_w,d])
            if S[i_h][i_w] == "#" and k==0:
                K.append([h,w,d+1])
                k += 1
    while K:
        h,w,d = K.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                i_h,i_w = h+i,w+j
                if min(i_h,i_w)<0 or i_h >= H or i_w >= W:
                    continue
                if S[i_h][i_w] != "#":
                    if distance[i_h][i_w] == INF:
                        distance[i_h][i_w] = d+1
                        Q.append([i_h,i_w,d])

ans = distance[D_h][D_w]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    que = deque()

    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))#ここもスタートの座標に変えること

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

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

        for i,j in zip(dx,dy):
            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 lin[nx][ny] > lin[x][y]:
                    que.appendleft((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        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 lin[nx][ny] > lin[x][y]+1 and (i,j) not in [[-1,0],[1,0],[0,-1],[0,1]]:
                    que.appendleft((nx,ny))
                    lin[nx][ny] = lin[x][y]+1# 魔法を使っていける

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(100000):
        for _ in range(100000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            for next_y in range(-2, 3):
                                for next_x in range(-2, 3):
                                    x, y = now_x + next_x, now_y + next_y
                                    if 0 <= x < w and 0 <= y < h:
                                        if c[y][x] not in "#=!":
                                            c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                            d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))

    d = [[10**15 for _ in range(W)] for _ in range(H)]    
    d[Ch-1][Cw-1] = 0

    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]

    def dfs(ch, cw):   
        stack = deque()
        stack.append((ch, cw))
    
        while stack:
            x, y = stack.popleft()
        
            if(x == Dh-1 and y == Dw-1):
                return d[x][y]
    
            for dx, dy in direction:
                nx = x + dx
                ny = y + dy
        
                if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                    continue
                if(grid[nx][ny] == "#"):
                    continue
                d[nx][ny] = d[x][y]
                stack.append((nx, ny))
        
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                        continue
                    if(grid[x+i][y+j] == "#"):
                        continue
                    if(d[x][y] + 1 >= d[x+i][y+j]):
                        continue
                    d[x+i][y+j] = d[x][y] + 1
                    stack.append((x+i, y+j))
        return -1
    
    print(dfs(Ch-1, Cw-1))
        
main()

Submission status: Time Limit Exceeded

Solution code:
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

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    s_moved = set()
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if not (xx, yy) in s_moved:
              if xx == dh and yy == dw:
                  return m[xx][yy]
              move(xx, yy, dq, dq_next)
              s_moved.add((xx, yy))
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import sys
import os
from operator import mul
from collections import deque


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    ans = -1
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])
    que2.append((sx, sy))

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    while que: 
        while que:
            p = que.popleft()
            que2.append(p)
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                break

            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動可否判定、d[nx][ny] == INF であれば訪れたことがない
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p までのワープ回数で確定する
                    que.append((nx, ny))
                    que2.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
        # print('after que: ',d)
        # dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        # dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            # for i in range(20):
            for dxi in range(-2,3):
                for dyi in range(-2,3):
                    nx = p[0] + dxi
                    ny = p[1] + dyi
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                        # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                        que.append((nx, ny))
                        d[nx][ny] = d[p[0]][p[1]]+1  
        # print('after que2: ',d)  
    return ans

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, -2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, -2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx, ny = u[0] + mX[i], u[1] + mY[i]

            if nx < 0 or H <= nx or ny < 0 or W <= ny or S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for j in range(20):
            wx = u[0] + zX[j]
            wy = u[1] + zY[j]
            if wx < 0 or H <= wx or wy < 0 or W <= wy or S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]] + 1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("#"*(w+4))
l.append("#"*(w+4))
for i in range(h):
    l.append("##"+input()[:-1]+"##")
l.append("#"*(w+4))
l.append("#"*(w+4))
#input

"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.append([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])