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
from itertools import product

H, W = map(int, input().split())
start = tuple(map(lambda x: int(x) - 1, input().split()))
goal = tuple(map(lambda x: int(x) - 1, input().split()))

maze = []
for _ in range(H):
    maze.append(list(input()))

serve = set()
visited = set()

Q = deque([(0, start)])
while Q:
    data = Q.popleft()
    c = data[0]
    pos = data[1]
    visited.add(pos)
    if pos == goal:
        print(c)
        exit()
    # A
    for move in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    Q.appendleft((c, (nx, ny)))
    # B
    for move in product(range(-2, 3), repeat=2):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in serve | visited:
                    Q.append((c + 1, (nx, ny)))
                    serve.add((nx, ny))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
HW = [list(input()) for _ in range(H)]


def check(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] == ".":
        return True
    else:
        return False


dist = [[float("inf")] * W for _ in range(H)]
# print("dist")
# pl(dist)
dist[ch - 1][cw - 1] = 0

deq = deque()
deq.append([(ch - 1, cw - 1)])  # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
warpy = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
warpx = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
step = 0
found = False
cnt = 0
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    for val in cqueue:
        y, x = val
        # if val == (gy - 1, gx - 1):
        #     found = True
        #     break
        for dy, dx in zip(ddy, ddx):
            chky = set()
            chkx = set()
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if ny != 0:
                    chky.add(ny)
                    chky.add(ny * 2)
                if nx != 0:
                    chkx.add(nx)
                    chkx.add(nx * 2)
                HW[ny][nx] = "#"
                if dist[y][x] < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x]
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x])
                nqueue.append((ny, nx))
        for dy, dx in zip(warpy, warpx):
            if (dy in chky) or (dx in chkx):
                continue
            cnt += 1
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if dist[y][x] + 1 < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x] + 1
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1)
                nqueue.append((ny, nx))
    # if found:
    #     break
    deq.append(nqueue)
    # step += 1
val = dist[dh - 1][dw - 1]
if val == float("inf"):
    print(-1)
else:
    print(val)
# print(dist[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    sr, sc = map(int, readline().split())
    gr, gc = map(int, readline().split())

    grid = [["#"] * (w + 2)]
    for _ in range(h):
        s = ["#"] + list(input()) + ["#"]
        grid.append(s)
    grid.append(["#"] * (w + 2))

    ans = 0
    dist = defaultdict(int)
    que1 = deque()
    que1.append((sr, sc, 0))
    grid[sr][sc] = "!"

    while que1:
        cr, cc, cost = que1.popleft()
        if cr == gr and cc == gc:
            return print(cost)

        if grid[cr + 1][cc] == ".":
            que1.appendleft((cr + 1, cc, cost))
            grid[cr + 1][cc] = "!"
            dist[(cr + 1, cc)] = cost
        if grid[cr - 1][cc] == ".":
            que1.appendleft((cr - 1, cc, cost))
            grid[cr - 1][cc] = "!"
            dist[(cr - 1, cc)] = cost
        if grid[cr][cc + 1] == ".":
            que1.appendleft((cr, cc + 1, cost))
            grid[cr][cc + 1] = "!"
            dist[(cr, cc + 1)] = cost
        if grid[cr][cc - 1] == ".":
            que1.appendleft((cr, cc - 1, cost))
            grid[cr][cc - 1] = "!"
            dist[(cr, cc - 1)] = cost

        for mr in range(-2, 3):
            for mc in range(-2, 3):
                nr = cr + mr
                nc = cc + mc
                if 1 <= nr <= h and 1 <= nc <= w:
                    if grid[nr][nc] == ".":
                        que1.append((nr, nc, cost + 1))
                        dist[(nr, cr)] = cost + 1

    return print(-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(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
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 = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))

    for i in range(h):
        for j in range(w):
            for ii,jj in d2:
                if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                    if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                        v[i+ii][j+jj] = tmp+1
                        q.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1

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

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())
from collections import deque

grid =  ''
grid +=  '#' * (W+4) * 2
for h in range(H):
  S = str(input())
  grid += '#' * 2 + S + '#' * 2
grid +=  '#' * (W+4) * 2

Dire = [W+4, -W-4, 1, -1]
WAAP_ = [
  -2*(W+4)-2,-2*(W+4)-1,-2*(W+4), -2*(W+4)+1, -2*(W+4)+2, 
  -1*(W+4)-2,-1*(W+4)-1,-1*(W+4), -1*(W+4)+1, -1*(W+4)+2, 
  -2, -1, 1, 2,
  1*(W+4)-2,1*(W+4)-1,1*(W+4), 1*(W+4)+1, 1*(W+4)+2, 
  2*(W+4)-2,2*(W+4)-1,2*(W+4), 2*(W+4)+1, 2*(W+4)+2, 
]
start = 2 * (W+4) + (Ch - 1) * (W+4) + 2 + (Cw - 1)
end = 2 * (W+4) + (Dh - 1) * (W+4) + 2 + (Dw - 1)


def WAAP(lst):
  res =  []
  for l in lst:
    for waap_ in  WAAP_:
      l_ = l+ waap_
      if grid[l_] == '.' :
        res.append(l_)
  return list(set(res))
        
        
    

def dfs(wwww, stack):
  fin =  []
  
  while True:
    #print(stack)
    if len(stack) == 0:
      for f in fin:
        grid[f] == '#'
      waap = WAAP(fin)
      return False, waap
      break
    q = stack.pop()
    fin.append(q)
    if q == end:
      return True, wwww
    else:
      for d in Dire:
        new_q = q + d
        if grid[new_q] == '.' and  new_q not in fin and new_q not in stack:
          stack.append(new_q)
          
          
          
          
def main():
  stack_ = deque([start])
  ans = 0
  while True:
    is_fin, res = dfs(ans, stack_)
    if is_fin:
      print(ans)
      break
    else:
      if len(res) == 0:
        print(-1)
        break
      stack_ = deque(res)
      ans += 1
      
main()

Submission status: Time Limit Exceeded

Solution code:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    H, W = read_ints()
    wiz = read_int_list()
    goal = read_int_list()
    grid = [read_str() for _ in range(H)]
    visit = [[False] * W for _ in range(H)]
    
    visit[wiz[0] - 1][wiz[1] - 1] = True
    cnt = [[-1] * W for _ in range(H)] 
    que = deque([[wiz[0] - 1, wiz[1] - 1]])
    cnt[wiz[0] - 1][wiz[1] - 1] = 0

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dx8 = [0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1]
    dy8 = [2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]

    while que:
        y, x = que.popleft()
        if y == goal[0] - 1 and x == goal[1] - 1:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != '#' and (visit[ny][nx] == False or cnt[ny][nx] > -1):
                que.append([ny, nx])
                visit[ny][nx] = True
                cnt[ny][nx] = cnt[y][x]
            
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] == '#':
                for i in range(16):
                    nx = x + dx8[i]
                    ny = y + dy8[i]
                    if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != '#' and visit[ny][nx] == False:
                        que.append([ny, nx])
                        visit[ny][nx] = True
                        cnt[ny][nx] = cnt[y][x] + 1

    print(cnt[goal[0] - 1][goal[1] - 1])


if __name__ ==  '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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 = [input().strip() for _ in range(H)]

    warp = ((-2, -2), (-2, -2), (-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))

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Dijkstra
def Dijkstra(D,From,To,with_path=False):
    """Dijksta法を用いて,FromからToまでの距離を求める.

    D:辺の重みが全て非負の有向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

    (出力の結果)
    with_path=True->(距離,最短経路の辿る際の前の頂点)
    with_path=False->距離
    """
    from copy import copy
    from heapq import heappush,heappop

    T={v:float("inf") for v in D.vertex}
    T[From]=0

    if with_path:
        Prev={v:None for v in D.vertex}

    Q=[(0,From)]

    Flag=False
    while Q:
        c,u=heappop(Q)

        if u==To:
            Flag=True
            break

        if T[u]<c:
            continue

        for v in D.adjacent_out[u]:
            if T[v]>T[u]+D.adjacent_out[u][v]:
                T[v]=T[u]+D.adjacent_out[u][v]
                heappush(Q,(T[v],v))

                if with_path:
                    Prev[v]=u

    if not Flag:
        if with_path:
            return (float("inf"),None)
        else:
            return float("inf")

    if with_path:
        path=[To]
        u=To
        while (Prev[u]!=None):
            u=Prev[u]
            path.append(u)
        return (T[To],path[::-1])
    else:
        return T[To]
#=====================================
def No_to_Pos(N):
    return (N//W+1,N%W+1)

def Pos_to_No(x,y):
    return (x-1)*W+(y-1)

def dist(P,Q):
    return max(abs(P[0]-Q[0]),abs(P[1]-Q[1]))
#=====================================
H,W=map(int,input().split())
C=tuple(map(int,input().split()))
D=tuple(map(int,input().split()))

S=["*"*(W+4)]*(H+4)

for x in range(H):
    S[x+2]="**"+input()+"**"

V=[]
for x in range(1,H+1):
    V+=[(x,y) for y in range(1,W+1)]

J=Digraph(V)
B=[(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 x in range(1,H+1):
    for y in range(1,W+1):
        if S[x+1][y+1]!=".":
            continue
        for (p,q) in B:
            if S[x+p+1][y+q+1]==".":
                if p==q-1==0 or p-1==q==0:
                    J.add_edge((x,y),(x+p,y+q),0)
                    J.add_edge((x+p,y+q),(x,y),0)
                else:
                    J.add_edge((x,y),(x+p,y+q),1)
                    J.add_edge((x+p,y+q),(x,y),1)

T=Dijkstra(J,C,D)
if T==float("inf"):
    print(-1)
else:
    print(T)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().strip().split())
Ch, Cw = map(int, input().strip().split())
Dh, Dw = map(int, input().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

moves=[]
for i in range(H):
    moves.append([1000000]*W)

for i in range(H):
    s = input().strip()
    for j in range(W):
        if s[j] == '#':
            moves[i][j] = -1

moves[Ch][Cw]=0
sources_0 = [[-1,0],[1,0],[0,-1],[0,1]]
sources_1 = [[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2]]
sources_1 += [[-2,-1],[-1,-1],[0,-1],[1,-1],[2,-1]]
sources_1 += [[-2,0],[-1,0],[1,0],[2,0]]
sources_1 += [[-2,1],[-1,1],[0,1],[1,1],[2,1]]
sources_1 += [[-2,2],[-1,2],[0,2],[1,2],[2,2]]

def not_concluded():
    for i in range(H):
        for j in range(W):
            if moves[i][j] == 1000000:
                return True
    return False

n = 0
while (n <= H*W):
    n += 1
    for i in range(H):
        for j in range(W):
            if moves[i][j] <= 0:
                continue
            for src in sources_0:
                if i+src[0] >= 0 and i+src[0] < H and j+src[1] >= 0 and j+src[1] < W:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move < moves[i][j]:
                        moves[i][j] = src_move
            for src in sources_1:
                if i+src[0] >= 0 and i+src[0] < H and j+src[1] >= 0 and j+src[1] < W:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move + 1 < moves[i][j]:
                        moves[i][j] = src_move + 1

if moves[Dh][Dw] == 1000000:
    print(-1)
else:
    print(moves[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def main():
    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s = [input() for _ in range(h)]
    N = h * w

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

    for hi in range(h):
        for wi in range(w):
            if s[hi][wi] == "#":
                continue

            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh = hi + dh
                    nw = wi + dw
                    if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                        row.append(f(hi, wi))
                        col.append(f(nh, nw))
                        if abs(dh) + abs(dw) == 1:
                            weight = 0
                        else:
                            weight = 1
                        cost.append(weight)

    g = csr_matrix((cost, (row, col)), shape=(N, N))
    dist = dijkstra(g, indices=f(sh-1, sw-1)).astype(int)
    ans = dist[f(gh-1, gw-1)]
    ans = max(ans, -1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as Q


bloques = Q()
totreat = Q()

def voisins(x,y):
	lst = []
	for i in range(x-2,x+3):
		for j in range(y-2, y+3):
			if (i,j)!=(x,y): lst+=[(i,j)]
	return lst

def bfs():
	# ~ print("bfs")
	while not totreat.empty():
		x,y = totreat.get()
		# ~ print(x,y,"en traitement")
		vis[x][y] = True
		bou = False
		for a,b in ((x,y+1),(x,y-1),(x+1,y),(x-1,y)):
			if 0<=a<H and 0<=b<W:
				if g[a][b]=='.':
					if not vis[a][b]:
						bou = True
						vis[a][b] = True
						dist[a][b] = min(dist[a][b],dist[x][y])
						totreat.put((a,b))
				else:
					# ~ print(x,y,"est bloque") 
					bloques.put((x,y))

def bfs_magic():
	# ~ print("bfsmagic")
	while not bloques.empty():
		x,y = bloques.get()
		vis[x][y] = True
		for a,b in voisins(x,y):
			if 0<=a<H and 0<=b<W and g[a][b]=='.':
				vis[a][b] = True
				dist[a][b] = min(dist[a][b],dist[x][y]+1)
				totreat.put((a,b))

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()]
g = [input() for i in range(H)]
vis = [[False]*W for i in range(H)]
dist = [[float('inf')]*W for i in range(H)]
dist[CH][CW] = 0
vis[CH][CW] = True
totreat.put((CH,CW))

cnt = 100
while not totreat.empty() and cnt>0:
	bfs()
	cnt-=1
	if not bloques.empty():
		bfs_magic()
	if vis[DH][DW]:
		print(dist[DH][DW])
		break
	

if not vis[DH][DW]: print("-1")
# ~ else:print(dist[DH][DW])

# ~ print("dist")
# ~ for d in dist:
	# ~ print(d)
# ~ print("vis")
# ~ for d in vis:
	# ~ print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
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

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

cnt = 0

def bfs():
    global cnt
    reached = [[False for _ in range(W)] for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    #reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
        if d:
            cnt += 1

bfs()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from collections import deque
def LI():return list(map(int,input().split()))
INF=float("inf")

h,w=LI()
ch,cw=LI()
dh,dw=LI()
maze=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]

visited=[[False]*(w+2) for _ in range(h+2)]

q=deque()
q.append((ch,cw))
p=deque()
while q:
    x,y=q.popleft()
    visited[x][y]=True
    for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
        xn,yn=x+i,y+j
        if visited[xn][yn]:
          continue
        if maze[xn][yn]==".":
            visited[xn][yn]=True
            q.append((xn,yn))
    for i,j in ([-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]):
      xm,ym=x+i,y+j
      try:
        if visited[xm][ym]:
          continue
        if maze[xm][ym]=="#":
          continue
        p.append((xm,ym))
      except:pass
if visited[dh][dw]:
    print(0)
    exit()

for (px,py) in p:
    if visited[px][py]==False:
        q.append((px,py))
if len(q)==0:
    print(-1)
    exit()
for ttt in range(1,100000):
    while q:
        x,y=q.popleft()
        visited[x][y]=True
        if visited[dh][dw]:
            print(ttt)
            exit()
        for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
            xn,yn=x+i,y+j
            if visited[xn][yn]:
              continue
            if maze[xn][yn]==".":
                visited[xn][yn]=True
                q.append((xn,yn))
        for i,j in ([-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]):
          xm,ym=x+i,y+j
          try:
            if visited[xm][ym]:
              continue
            if maze[xm][ym]=="#":
              continue
            p.append((xm,ym))
          except:pass
    
    if visited[dh][dw]==True:
        print(ttt)
        exit()
        
    for (px,py) in p:
        if visited[px][py]==False:
            q.append((px,py))
    if len(q)==0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
import numpy as np
input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
s = np.array(s)
num = np.array([[float("inf") for i in range(w)] for i in range(h)])
flag = np.array([[False for i in range(w)] for i in range(h)])
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = np.array([[-1, 0], [1, 0], [0, -1], [0, 1]])
d2 = np.array([[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]])
d3 = np.array([[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]])
d4 = np.array([[-2, -2], [-2, 2], [2, -2], [2, 2]])
while queue:
    test = queue.popleft()
    x = test[0]
    y = test[1]
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = temp
            queue.append([x2, y2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(int(num[dh - 1][dw - 1]))

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = ["" for _ in range(h)]
p = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
q = queue.Queue()
q.put((ch,cw))
p[ch][cw] = 0
l = [(ch,cw)]
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[j][k] = i
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            l.append((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi in [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]:
      if  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[j+hi][k+wi] = i+1
  if q.empty():
    print(-1)
    exit()
  l = nl
  i += 1