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 *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
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 h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while P:
  x,y = P.popleft()
  Q.append([x,y])
  for dx,dy in move:
    if ans[x+dx][y+dy]==-1:
      ans[x+dx][y+dy] = ans[x][y]
      P.append([x+dx,y+dy])
  
  if len(P)==0:
    while Q:
      x,y = Q.popleft()
      for dx,dy in magic:
        if ans[x+dx][y+dy]==-1:
          ans[x+dx][y+dy] = ans[x][y]+1
          P.append([x+dx,y+dy])

print(ans[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],[0,-2],[0,-1],[0,0],[0,1],[0,2],[1,-2],[1,-1],[1,0],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]

for h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while P:
  x,y = P.popleft()
  Q.append([x,y])
  for dx,dy in move:
    if ans[x+dx][y+dy]==-1:
      ans[x+dx][y+dy] = ans[x][y]
      P.append([x+dx,y+dy])
  
  if len(P)==0:
    while Q:
      x,y = Q.popleft()
      for dx,dy in magic:
        if ans[x+dx][y+dy]==-1:
          ans[x+dx][y+dy] = ans[x][y]+1
          P.append([x+dx,y+dy])

print(ans[dh+1][dw+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())
s = [['#']*(w+2)]
for _ in range(h):
    s.append([x for x in '#'+input()+'#'])
s.append(['#']*(w+2))
visiable = [[True if s[i][j] == '.' else False for j in range(w+2)] for i in range(h+2)]

cur_cell = []
next_cell = [[ch,cw]]
cnt = 0
while len(next_cell) > 0:
    cur_cell = []
    for x in next_cell:
        d = deque()
        d.append([x[0],x[1],cnt])
        while d:
            cell = d.popleft()
            s[cell[0]][cell[1]] = cell[2]
            visiable[cell[0]][cell[1]] = False
            cur_cell.append([cell[0], cell[1]])
            if visiable[cell[0]][cell[1]+1]:
                d.append([cell[0], cell[1]+1, cnt])
            if visiable[cell[0]+1][cell[1]]:
                d.append([cell[0]+1, cell[1], cnt])
            if visiable[cell[0]][cell[1]-1]:
                d.append([cell[0], cell[1]-1, cnt])
            if visiable[cell[0]-1][cell[1]]:
                d.append([cell[0]-1, cell[1], cnt])
    next_cell = []
    for x in cur_cell:
        start = [max(0, x[0]-2), max(0, x[1]-2)]
        end = [min(h+1, x[0]+2), min(w+1, x[1]+2)]
        for i in range(start[0], end[0]+1):
            for j in range(start[1], end[1]+1):
                if s[i][j] == '.':
                    next_cell.append([i, j])
                    s[i][j] = cnt
    cnt += 1

print(-1 if s[dh][dw] == '.' else s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [['#']*(w+2)]
for _ in range(h):
    s.append([x for x in '#'+input()+'#'])
s.append(['#']*(w+2))
visiable = [[True if s[i][j] == '.' else False for j in range(w+2)] for i in range(h+2)]

cur_cell = []
next_cell = [[ch,cw]]
cnt = 0
while len(next_cell) > 0:
    cur_cell = []
    for x in next_cell:
        d = deque()
        d.append([x[0],x[1],cnt])
        while d:
            cell = d.popleft()
            if not visiable[cell[0]][cell[1]]:
                continue
            s[cell[0]][cell[1]] = cell[2]
            visiable[cell[0]][cell[1]] = False
            cur_cell.append([cell[0], cell[1]])
            d.append([cell[0], cell[1]+1, cnt])
            d.append([cell[0]+1, cell[1], cnt])
            d.append([cell[0], cell[1]-1, cnt])
            d.append([cell[0]-1, cell[1], cnt])
    next_cell = []
    for x in cur_cell:
        start = [max(0, x[0]-2), max(0, x[1]-2)]
        end = [min(h+1, x[0]+2), min(w+1, x[1]+2)]
        for i in range(start[0], end[0]+1):
            for j in range(start[1], end[1]+1):
                if s[i][j] == '.':
                    next_cell.append([i, j])
                    s[i][j] = cnt
    cnt += 1

print(-1 if s[dh][dw] == '.' else s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [['#']*(w+2)]
for _ in range(h):
    s.append([x for x in '#'+input()+'#'])
s.append(['#']*(w+2))
visiable = [[True for _ in range(w+2)] for _ in range(h+2)]

cur_cell = []
next_cell = [[ch,cw]]
cnt = 0
while len(next_cell) > 0:
    cur_cell = []
    for x in next_cell:
        d = deque()
        d.append([x[0],x[1],cnt])
        while d:
            cell = d.popleft()
            if not visiable[cell[0]][cell[1]]:
                continue
            s[cell[0]][cell[1]] = cell[2]
            visiable[cell[0]][cell[1]] = False
            cur_cell.append([cell[0], cell[1]])
            if s[cell[0]][cell[1]+1] != '#':
                d.append([cell[0], cell[1]+1, cnt])
            if s[cell[0]+1][cell[1]] != '#':
                d.append([cell[0]+1, cell[1], cnt])
            if s[cell[0]][cell[1]-1] != '#':
                d.append([cell[0], cell[1]-1, cnt])
            if s[cell[0]-1][cell[1]] != '#':
                d.append([cell[0]-1, cell[1], cnt])

    next_cell = []
    for x in cur_cell:
        start = [max(0, x[0]-2), max(0, x[1]-2)]
        end = [min(h+1, x[0]+2), min(w+1, x[1]+2)]
        for i in range(start[0], end[0]+1):
            for j in range(start[1], end[1]+1):
                if s[i][j] == '.':
                    next_cell.append([i, j])
                    s[i][j] = cnt
    cnt += 1

print(-1 if s[dh][dw] == '.' else s[dh][dw])

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())

ch,cw,dh,dw = ch-1,cw-1,dh-1,dw-1
S = [[""]*w for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        S[i][j] = s[j]
        
visited = [[-1]*w for _ in range(h)]

visited[ch][cw] = 0

INF = 10**9
dist = [[INF]*w for _ in range(h)]
Q = deque([])
Q.append([ch,cw])
dist[ch][cw] = 0

while Q:
    y,x = Q.popleft()
    d = dist[y][x]
    
    for i, j in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
      nx = x + i
      ny = y + j
      if (nx < 0 or nx >= w or ny < 0 or ny >= h): 
          continue
      if S[ny][nx] == "#":
          continue
      if dist[ny][nx] <= d:
          continue
      dist[ny][nx] = d
      Q.appendleft([ny,nx])
      
    
    for ey in range(-2,3):
        for ex in range(-2,3):
            nx = x + ex
            ny = y + ey
            if (nx < 0 or nx >= w or ny < 0 or ny >= h): 
              continue
            if S[ny][nx] == "#":
              continue
            if dist[ny][nx] <= d+1:     
              continue
            dist[ny][nx] = d+1
            Q.append([ny,nx])
      
ans = dist[dh][dw]

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import product
from collections import deque

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
S = {}
roads = set()
for i in range(h):
    s = input()
    for j in range(w):
        S[i, j] = s[j]
        if s[j] == '.':
            roads.add((i, j))

index = 0
section = {}
reached = {k: False for k in roads}

for p in roads:
    if reached[p]:
        continue
    else:
        reached[p] = True
        stack = [p]
        section[p] = index
        while stack:
            v = stack.pop()
            i, j = v
            adj = []
            if i > 0 and S[i - 1, j] == '.':
                adj.append((i-1, j))
            if j > 0 and S[i, j - 1] == '.':
                adj.append((i, j - 1))
            if i < h-1 and S[i + 1, j] == '.':
                adj.append((i+1, j))
            if j < w-1 and S[i, j+1] == '.':
                adj.append((i, j+1))
            for u in adj:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    section[u] = index
        index += 1

# print(roads)
# print(section)
if section[c] == section[d]:
    print(0)
    exit(0)

vertex = range(index)
edges = {i: set() for i in vertex}
for i, j in roads:
    head = section[i, j]
    square = product(range(max(i-2, 0), min(i+3, h)),
                     range(max(j-2, 0), min(j+3, w)))
    for m in square:
        if S[m] == '.':
            tail = section[m]
            if tail != head and S[m] == '.':
                edges[tail].add(head)
                edges[head].add(tail)

source = section[c]
target = section[d]
distance = {v: math.inf for v in vertex}
distance[source] = 0
reached_ = {k: False for k in vertex}
reached_[source] = True
queue = deque([source])
while queue:
    u = queue.popleft()
    for v in edges[u]:
        if not reached_[v]:
            reached_[v] = True
            distance[v] = distance[u] + 1
            queue.append(v)

if distance[target] != math.inf:
    print(distance[target])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w = nm()
    Ch, Cw = nm()
    Dh, Dw = nm()
    S = [list(ns()) for _ in range(h)]
    pos = deque([(Ch, Cw)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[Ch - 1][Cw - 1] = 0


    warp = deque([(Ch, Cw)])
    while pos:
        while pos:
            c_i, c_j = pos.pop()
            for i, j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
                if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                        and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] \
                        and S[c_i + i - 1][c_j + j - 1] == '.':
                    cost[c_i + i - 1][c_j + j - 1] = cost[c_i - 1][c_j - 1]
                    pos.append((c_i + i, c_j + j))
                    warp.append((c_i + i, c_j + j))

        warp_sub = []
        while warp:
            c_i, c_j = warp.pop()
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                            and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] + 1 \
                            and S[c_i + i - 1][c_j + j - 1] == '.':
                        cost[c_i + i - 1][c_j + j -
                                          1] = cost[c_i - 1][c_j - 1] + 1
                        pos.append((c_i + i, c_j + j))
                        warp_sub.append((c_i + i, c_j + j))

        warp.extend(warp_sub)

    print(cost[Dh - 1][Dw - 1] if cost[Dh - 1][Dw - 1] != float('Inf') else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h , w = map(int,input().split())
ch , cw = map(lambda x:int(x)-1,input().split())
dh , dw = map(lambda x:int(x)-1,input().split())
ma = [list(input()) for i in range(h)]
visit = [[-1 for i in range(w)] for j in range(h)]
cou = -1
p = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if visit[i][j] != -1 or ma[i][j] == "#":
            continue
        cou += 1
        visit[i][j] = cou
        d = deque()
        d.append((i,j))
        while d:
            now = d.popleft()
            for x , y in p:
                if 0 <= now[0]+x < h and 0 <= now[1]+y < w:
                    if ma[now[0]+x][now[1]+y] == "." and visit[now[0]+x][now[1]+y] == -1:
                        visit[now[0]+x][now[1]+y] = cou
                        d.append(((now[0]+x,now[1]+y)))

st = visit[ch][cw]
go = visit[dh][dw]
route = [set() for i in range(cou+1)]

for i in range(h):
    for j in range(w):
        if visit[i][j] == -1:
            continue
        for s in range(-2,3,1):
            for t in range(-2,3,1):
                if 0<=i+s<h and 0<=j+t<w:
                    if visit[i+s][j+t] != -1 and visit[i+s][j+t] != visit[i][j]:
                        route[visit[i][j]].add(visit[i+s][j+t])

kyori = [-1 for i in range(cou+1)]
kyori[st] = 0
d = deque()
d.append(st)

while d:
    now = d.popleft()
    for i in route[now]:
        if kyori[i] == -1:
            kyori[i] = kyori[now] + 1
            d.append(i)

print(kyori[go])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    Ch, Cw = NMI()
    Dh, Dw = NMI()
    S_ = []
    for i in range(H):
        s = SI()
        S_.append(s)

    # i行目j列目のマスに(i - 1) * W + j　- 1の数字を割り振る
    star = (Ch - 1) * W + Cw - 1
    goal = (Dh - 1) * W + Dw - 1
    g = [[] for _ in range(H * W)]
    for i in range(H * W):
        h, w = divmod(i, W)
        if S_[h][w] == '#':
            continue
        else:
            if w != 0 and S_[h][w - 1] == '.':
                g[i].append(i - 1)
            if w != W - 1 and S_[h][w + 1] == '.':
                g[i].append(i + 1)
            if h != 0 and S_[h - 1][w] == '.':
                g[i].append(i - W)
            if h != (H - 1) and S_[h + 1][w] == '.':
                g[i].append(i + W)


    from collections import deque

    def bfs(u, n):
        queue = deque([u])
        d = [None] * n # uからの距離の初期化
        d[u] = 0 # 自分との距離は0
        dif_list = [u]
        while queue:
            v = queue.popleft()
            for i in g[v]:
                if d[i] is None:
                    d[i] = 0
                    queue.append(i)
                    dif_list.append(i)
        return dif_list

    def warp(A, B):
        dif_A = []
        dif_A_total = [0] * (H * W)
        bfs_list = []
        for a in A:
            h, w = divmod(a, W)
            left = min(w, 2)
            right = min(W - 1 - w, 2)

            for i in range(-left, right + 1):
                for j in range(-2, 3):
                    a_ = a + i + (j * W)
                    h_, w_ = divmod(a_, W)
                    if 0 <= a_ <= H * W - 1 and B[a_] == 0 and dif_A_total[a_] == 0 and S_[h_][w_] == '.':
                        dif_A_total[a_] = 1
                        B[a_] = 1
                        dif_A.append(a_)
        for b in dif_A:
            if b not in bfs_list:
                b_ = bfs(b, H * W)
                for c in b_:
                    if c not in dif_A:
                        bfs_list.append(c)
                        dif_A.append(c)
                        B[c] = 1
        return dif_A

    dif_0 = bfs(star, H * W)
    dif_total = [0] * (H * W)
    for _ in dif_0:
        dif_total[_] = 1
    ans = 0
    if dif_total[goal] != 0:
        print(0)
        exit()
    else:
        while dif_0 != []:
            dif_0 = warp(dif_0, dif_total)
            ans += 1
            if dif_total[goal] != 0:
                print(ans)
                exit()
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w = nm()
    Ch, Cw = nm()
    Dh, Dw = nm()
    S = [list(ns()) for _ in range(h)]
    pos = deque([(Ch, Cw)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[Ch - 1][Cw - 1] = 0

    while pos:
        c_i, c_j = pos.pop()
        for i, j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
            if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                    and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] \
                    and S[c_i + i - 1][c_j + j - 1] == '.':
                cost[c_i + i - 1][c_j + j - 1] = cost[c_i - 1][c_j - 1]
                pos.append((c_i + i, c_j + j))

        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                        and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] + 1 \
                        and S[c_i + i - 1][c_j + j - 1] == '.':
                    cost[c_i + i - 1][c_j + j - 1] = cost[c_i - 1][c_j - 1] + 1
                    pos.append((c_i + i, c_j + j))

    print(cost[Dh - 1][Dw - 1] if cost[Dh - 1][Dw - 1] != float('Inf') else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

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())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = deque()
pos.append([ch,cw,0])
while len(pos)>0:
  x, y, hop = pos.popleft()
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
    
  maze[x][y] = 2
  
  flag = 0
  if maze[x-1][y] <2:
    pos.append([x-1,y,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        pos.append([x-2,y,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        pos.append([x-2,y+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        pos.append([x-2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        pos.append([x-2,y-1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        pos.append([x-2,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        pos.append([x+2,y,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        pos.append([x+2,y-1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        pos.append([x+2,y-2,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        pos.append([x+2,y+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        pos.append([x+2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        pos.append([x,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        pos.append([x+1,y-2,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        pos.append([x-1,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        pos.append([x,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        pos.append([x+1,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        pos.append([x-1,y+2,hop+1])
    except:
      pass
    if maze[x-1][y-1] <2:
      pos.append([x-1,y-1,hop+1])
    if maze[x-1][y+1] <2:
      flag=1
      pos.append([x-1,y+1,hop+1])
    if maze[x+1][y-1] <2:
      flag=1
      pos.append([x+1,y-1,hop+1])
    if maze[x+1][y+1] <2:
      flag=1
      pos.append([x+1,y+1,hop+1])
    
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

# D - Wizard in Maze
def conv_index(s):
	return int(s) - 1


def search(h, w, reached, magic):
  global Dh
  global Dw
  global can_goal
  global ans

  is_reached = copy.deepcopy(reached)

  if h == Dh and w == Dw:
    is_reached[Dh][Dw] = True
    can_goal = True
    ans.append(magic)
  elif not can_reach(h, w, is_reached):
    return
  else:
    is_reached[h][w] = True

    if need_to_use_magic(h, w, is_reached):
      m = magic + 1

      for i in range(-2, 3):
        search(h - 2, w + i, is_reached, m)
        search(h + 2, w + i, is_reached, m)

      for i in range(-2, 3):
        if i != 0:
          search(h - 1, w + i, is_reached, m)
          search(h + 1, w + i, is_reached, m)

      search(h, w - 2, is_reached, m)
      search(h, w + 2, is_reached, m)
    else:
      search(h - 1, w, is_reached, magic)
      search(h + 1, w, is_reached, magic)
      search(h, w - 1, is_reached, magic)
      search(h, w + 1, is_reached, magic)


def can_reach(h, w, is_reached):
	global H
	global W
	global maze

	if h < 0 or h > H - 1 or w < 0 or w > W - 1:
		return False
	elif is_reached[h][w]:
		return False
	elif maze[h][w] == '#':
		return False
	else:
		return True


def need_to_use_magic(h, w, is_reached):
	any_can_reach = False

	if can_reach(h - 1, w, is_reached):
		any_can_reach = True

	if can_reach(h + 1, w, is_reached):
		any_can_reach = True

	if can_reach(h, w - 1, is_reached):
		any_can_reach = True

	if can_reach(h, w + 1, is_reached):
		any_can_reach = True

	if not any_can_reach:
		return True


import copy
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
Ch, Cw = map(conv_index, input().split())
Dh, Dw = map(conv_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

can_goal = False
ans = []

search(Ch, Cw, is_reached, 0)

if not can_goal:
	print(-1)
elif len(ans) == 0:
	print(0)
else:
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

# D - Wizard in Maze
def conv_index(s):
	return int(s) - 1


def search(h, w, reached, magic, route):
  global Dh
  global Dw
  global can_goal
  global ans

  is_reached = copy.deepcopy(reached)

  if h == Dh and w == Dw:
    is_reached[Dh][Dw] = True
    can_goal = True
    ans.append(magic)
		
    #print(magic)
    #print(route + '\n' + str(Dh + 1) + ' ' + str(Dw + 1))
    #print('----------')
  elif not can_reach(h, w, is_reached):
    return
  else:
    is_reached[h][w] = True
    r = copy.copy(route)
    r += '\n' + str(h + 1) + ' ' + str(w + 1)

    if need_to_use_magic(h, w, is_reached):
      m = magic + 1

      for i in range(-2, 3):
        search(h - 2, w + i, is_reached, m, r)
        search(h + 2, w + i, is_reached, m, r)

      for i in range(-2, 3):
        if i != 0:
          search(h - 1, w + i, is_reached, m, r)
          search(h + 1, w + i, is_reached, m, r)

      search(h, w - 2, is_reached, m, r)
      search(h, w + 2, is_reached, m, r)
    else:
      search(h - 1, w, is_reached, magic, r)
      search(h + 1, w, is_reached, magic, r)
      search(h, w - 1, is_reached, magic, r)
      search(h, w + 1, is_reached, magic, r)


def can_reach(h, w, is_reached):
	global H
	global W
	global maze

	if h < 0 or h > H - 1 or w < 0 or w > W - 1:
		return False
	elif is_reached[h][w]:
		return False
	elif maze[h][w] == '#':
		return False
	else:
		return True


def need_to_use_magic(h, w, is_reached):
	any_can_reach = False

	if can_reach(h - 1, w, is_reached):
		any_can_reach = True

	if can_reach(h + 1, w, is_reached):
		any_can_reach = True

	if can_reach(h, w - 1, is_reached):
		any_can_reach = True

	if can_reach(h, w + 1, is_reached):
		any_can_reach = True

	if not any_can_reach:
		return True


import copy
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
Ch, Cw = map(conv_index, input().split())
Dh, Dw = map(conv_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

can_goal = False
ans = []

#search(Ch, Cw, 0)
import copy
search(Ch, Cw, is_reached, 0, '')

if not can_goal:
	print(-1)
elif len(ans) == 0:
	print(0)
else:
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x+1, y+1)

    y, x = map(int, input().split())
    goal = (x+1, y+1)

    dist_table = [[-2] * (W+4)]
    dist_table.append([-2] * (W+4))
    for _ in range(H):
        row = '##' + input() + '##'
        row = [-1 if c == '.' else -2 for c in row]
        dist_table.append(row)
    dist_table.append([-2] * (W+4))
    dist_table.append([-2] * (W+4))

    sx, sy = start
    
    move1 = ((-1, 0), (1, 0), (0, 1), (0, -1))
    move2 = ((-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))

    queue = deque()
    queue.append((start, 0))
    while queue:
        now_pos, dist = queue.popleft()
        now_x, now_y = now_pos
        if dist_table[now_y][now_x] != -1:
            continue
        dist_table[now_y][now_x] = dist
        if now_pos == goal:
            break

        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if dist_table[ty][tx] == -1:
                queue.appendleft(((tx, ty), dist))
        
        for dx, dy in move2:
            tx, ty = now_x + dx, now_y + dy
            if dist_table[ty][tx] == -1:
                queue.append(((tx, ty), dist + 1))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
 
def solve(h, w, ch, cw, dh, dw, s_list):
 
    s_arr = [[False] * (w + 4) for _ in range(h + 4)]
    for i, s in enumerate(s_list):
        for j in range(w):
            if s[j] == ".":
                s_arr[i + 2][j + 2] = True
 
    done_arr = [[False] * (w + 4) for _ in range(h + 4)]
 
    # heap
    queue = deque()
    res = -1
    # start
    queue.append((0, ch + 1, cw + 1))
    # main
    while len(queue):
        d, i, j = queue.popleft()
        if done_arr[i][j]:
            continue
        done_arr[i][j] = True
        # print(d, i, j)
        if i == dh + 1 and j == dw + 1:
            res = d
            # print("done")
            break
        for i_ in range(i - 2, i + 3):
            for j_ in range(j - 2, j + 3):
                if not done_arr[i_][j_] and s_arr[i_][j_]:
                    diff = abs(i_ - i) + abs(j_ - j)
                    if diff > 1:
                        queue.append((d + 1, i_, j_))
                    else:
                        queue.appendleft((d, i_, j_))
    # print(res)
    return res
 
 
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    s_list = []
    for i in range(h):
        s = input()
        s_list.append(s)
    res = solve(h, w, ch, cw, dh, dw, s_list)
    print(res)
 
 
def test():
    assert solve(4, 4, 1, 1, 4, 4, ["..#.", "..#.", ".#..", ".#.."]) == 1
    assert solve(4, 4, 1, 4, 4, 1, [".##.", "####", "####", ".##."]) == -1
    assert solve(4, 4, 2, 2, 3, 3, ["....", "....", "....", "...."]) == 0
    assert solve(4, 5, 1, 2, 2, 5, ["#.###", "####.", "#..##", "#..##"]) == 2
 
 
def test_large():
    assert solve(1000, 1000, 1, 1, 1000, 1000, ["." * 1000 for _ in range(1000)]) == 0
 
 
if __name__ == "__main__":
    main()