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:
class P:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False
        self.checked = False

from collections import deque
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [[None for _ in range(H)] for _ in range(W)]
for y in range(H):
    tmp = input()
    for x in range(W):
        S[x][y] = P(tmp[x])

def neighbors(x, y, d):
    for i in range(max(0, x-1), min(W, x+2)):
        if S[i][y].reached == False and S[i][y].c == '.':
            d.append((i, y))
    for i in range(max(0, y-1), min(H, y+2)):
        if S[x][i].reached == False and S[x][i].c == '.':
            d.append((x, i))

def jump(x, y, d):
    S[x][y].checked = True
    for i in range(max(0, x-2), min(W, x+3)):
        for j in range(max(0, y-2), min(H, y+3)):
            if S[i][j].reached == False and S[i][j].searched == False and S[i][j].c == '.':
                d.append((i, j))
                S[i][j].searched = True


def BFS(x, y):
    if S[x][y].reached:
        return
    d = deque([(x, y)])
    while True:
        x, y = d.popleft()
        S[x][y].reached = True
        neighbors(x, y, d)
        if len(d) == 0:
            break


counter = 0
if Cw == Dw and Ch == Dh:
    print(0)
    exit()
q = deque([(Cw, Ch)])
flag = False
while True:
    while len(q) > 0:
        x, y = q.popleft()
        BFS(x, y)
    if S[Dw][Dh].reached == True:
        break
    counter += 1
    for i in range(W):
        for j in range(H):
            if S[i][j].reached and S[i][j].checked == False:
                jump(i, j, q)
    if len(q) == 0:
        flag = True
        break
if flag:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [[i for i in input()] for _ in range(h)]
c = [[10**6] * w for _ in range(h)]

d = ((1, 0), (-1, 0), (0, 1), (0, -1))
q = deque([(cx, cy)])

c[cx][cy] = 0

while q:
    x, y = q.pop()
    cp = c[x][y]
    if (x, y) == (dx, dy):
        c[x][y] = cp
        break
    for i, j in d:
        nx = x + i
        ny = y + j
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][ny] > cp:
            q.append((nx, ny))
            c[nx][ny] = cp
    cp += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                q.appendleft((nx, ny))
print(-1 * (c[dx][dy] == 10**6) or c[dx][dy])

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,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,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):
        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.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:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

INF = float('inf')

def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input()) for _ in range(H)]

row = []
col = []
cost = []

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                row.append(rc_to_v(y, x))  # head
                col.append(rc_to_v(ny, nx))  # tail
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    cost.append(0)
                else:
                    cost.append(1)


AM = coo_matrix((cost, (row, col)), shape = (H * W, H * W)).tocsr()
cost = dijkstra(AM, directed = False, indices = rc_to_v(sy, sx))

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

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())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for qx, qy in zip(PX, PY):
        px = x + qx
        py = y + qy
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0

pool = deque()
pool.append(tuple(C))
while(pool):
    y, x = pool.pop()
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.appendleft((y+dy, x+dx))
            elif V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((y+dy, x+dx))
print(V[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__main__":
    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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    walk = [(1, 0), (0, 1), (-1, 0), (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)
    ]
    walk_que = deque()
    warp_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        mc[y][x] = w
        if y == dh and x == dw:
            break
        exit_wall = False
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF:
                if maze[ny][nx] == ".":
                    walk_que.append((ny, nx, w))
                else:
                    exit_wall = True
        if exit_wall:
            warp_que.append((y, x, w))
        if not walk_que:
            while warp_que:
                y, x, w = warp_que.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF and maze[ny][nx] == ".":
                        walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

if __name__ == "__main__":
    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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    walk = [(1, 0), (0, 1), (-1, 0), (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)
    ]
    walk_que = deque()
    warp_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        mc[y][x] = w
        if y == dh and x == dw:
            break
        exit_wall = False
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF:
                if maze[ny][nx] == ".":
                    walk_que.append((ny, nx, w))
                else:
                    exit_wall = True
        if exit_wall:
            warp_que.append((y, x, w))
        if not walk_que:
            while warp_que:
                y, x, w = warp_que.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF and maze[ny][nx] == ".":
                        walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

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 = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=[],[]
rs.append(sr-1)
cs.append(sc-1)
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.pop(0),cs.pop(0)
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.insert(0,nr)
            cs.insert(0,nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)

Submission status: Time Limit Exceeded

Solution code:
import collections

def bfs(v, goal, D, next_v, seen, rank):
    for x in D[v]:
        if x in seen:
            continue
        if x == goal:
            return True
        else:
            next_v.append((x,rank))
            seen.append(x)    


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 = [[x for x in input()] for _ in range(h)]
A = [i for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            A[w*i+j] = -1
        if i < h-1:
            if S[i][j] == '.' and S[i+1][j] == '.':
                A[w*i+j] = A[w*(i+1)+j] = min(A[w*i+j], A[w*(i+1)+j]) 
        if j < w-1:
            if S[i][j] == '.' and S[i][j+1] == '.':
                A[w*i+j] = A[w*i+(j+1)] = min(A[w*i+j], A[w*i+(j+1)])
#移動Aによる連結成分をノードとして移動Bで連結グラフを作成
B = collections.defaultdict(lambda:set())
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue
        for k in range(5):
            for l in range(3):
                if i+k-2 >= 0 and i+k-2 < h and j+l-2 >= 0:
                    if S[i][j] == '.' and S[i+k-2][j+l-2] == '.': #連結可能条件
                        if A[w*i+j] != A[w*(i+k-2)+(j+l-2)]:
                            B[A[w*i+j]].add(A[w*(i+k-2)+(j+l-2)])
                            B[A[w*(i+k-2)+(j+l-2)]].add(A[w*i+j])
                

if A[ch*w+cw] == A[dh*w+dw]: #Aで連結している
    ans = 0
else:
    next_v = [(A[ch*w+cw],0)]
    goal = A[dh*w+dw]
    seen = [A[ch*w+cw]]
    ans = 1
    while (True):
        if len(next_v) == 0: #Bで連結してない
            ans = -1
            break
        v = next_v[0][0]
        rank = next_v[0][1] + 1
        next_v.pop(0)
        if bfs(v, goal, B, next_v, seen, rank): #Bで連結しているなら
            ans = rank
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

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

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

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [(1,0),(0,1),(-1,0),(0,-1)]
    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))
    magic = ((-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 j, i in magic:
            if 0 <= x+i < w and 0 <= y+j < h:
                if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                    S[y+j][x+i] = S[y][x] + 1
                    queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for h in range(H):
        Sh =  list(input())
        S.append(Sh)

    que = {(Ch-1,Cw-1)}
    jump_que = set()
    goal = (Dh-1, Dw-1)
    # searched=set()
    searched = [[False for i in range(W)] for i in range(H)]
    jump =0

    while(True):
        while(len(que)):
            tmp = que.pop()
            if tmp ==goal:
                print(jump)

                return
            if searched[tmp[0]][tmp[1]] == True:
                continue
            searched[tmp[0]][tmp[1]] = True
            nxts=get_around(S,H,W,tmp[0],tmp[1], searched)
            # print(f'nxts: {nxts}')
            que=que|nxts
            jump_nxts = get_jump_around(S, H, W, tmp[0], tmp[1], searched)
            # print(f'jump_nxts: {jump_nxts}')
            jump_que = jump_que | jump_nxts
            # print(f'jump_que: {jump_que}')

        jump=jump+1
        que=jump_que
        jump_que = set()
        if len(que)==0:
            print('-1')
            return


def get_around(S,H,W, h,w, searched):
    hm = h-1
    hp =h+1
    wm = w-1
    wp= w+1
    nxt=set()
    if hm>=0 and S[hm][w]=='.' and not searched[hm][w]:
        nxt.add((hm,w))

    if hp<H and S[hp][w]=='.'and not searched[hp][w]:

        nxt.add((hp,w))
    if wm>=0 and S[h][wm]=='.'and not searched[h][wm]:
        nxt.add((h,wm))

    if wp<W and S[h][wp]=='.'and not searched[h][wp]:
        nxt.add((h,wp))
    return nxt

def get_jump_around(S,H,W, h,w, searched):
    hm = max(h-2,0)
    hp =min(h+2,H-1)
    wm = max(w-2,0)
    wp= min(w+2,W-1)
    nxt=set()
    # print(hm,hp,wm,wp)
    for h in range(hm,hp+1):
        for w in range(wm, wp + 1):
            if S[h][w]=='.' and not searched[h][w]:
                nxt.add((h, w))

    return nxt


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output,out)

    def test_入力例_1(self):
        input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = deque([(cx, cy)])

    c[cx][cy] = 0

    while q:
        x, y = q.popleft()
        cp = c[x][y]
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i, j in d:
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                q.appendleft((nx, ny))
                c[nx][ny] = cp
        cp += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                        ny] > cp:
                    c[nx][ny] = cp
                    q.append((nx, ny))

    return -1 * (c[dx][dy] == 10**6) or c[dx][dy]


print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


if __name__ == "__main__":
    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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    walk = [(1, 0), (0, 1), (-1, 0), (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)
    ]
    walk_que = deque()
    warp_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        mc[y][x] = w
        exit_wall = False
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF:
                if maze[ny][nx] == ".":
                    walk_que.append((ny, nx, w))
                else:
                    exit_wall = True
        if exit_wall:
            warp_que.append((y, x, w))
        if not walk_que:
            while warp_que:
                y, x, w = warp_que.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] == INF and maze[ny][nx] == ".":
                        walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().rstrip()

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())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import heapq
xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

h,w=map(int,input().split())
c1,c2=map(int,input().split())
d1,d2=map(int,input().split())
d=[list(input()) for i in range(h)]
d[c1-1][c2-1]=0
p=[]
heapq.heappush(p,(0,c1-1,c2-1))
while len(p):
    a,b,c=heapq.heappop(p)
    for x,y in xy:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a:
                d[x][y]=a
                heapq.heappush(p,(a,x,y))
    for x,y in wp:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a+1:
                d[x][y]=a+1
                heapq.heappush(p,(a+1,x,y))
#    print(p)
#    if d[d1-1][d2-1]==a:
#        print(a)
#        exit()
#    print(p)
#    print(d)

print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = False
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = True
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(Flag):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
        
    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[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())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = deque([(0, Si-1, Sj-1)])
visited = set()

while que:
    count, r, c = que.popleft()
    if not(0 <= r < H and 0 <= c < W):
        continue
    if (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        que.appendleft((count, r+td, c+lr))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            que.append((count+1, r+ud, c+lr))
print('-1')

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=[],[]
rs.append(sr-1)
cs.append(sc-1)
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.pop(0),cs.pop(0)
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.append(nr)
            cs.append(nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)