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:
import sys
def input():
  return sys.stdin.readline()[:-1]

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'*(W+4), 'X'*(W+4)]+['XX'+input()+'XX' for _ in range(H)]+['X'*(W+4), 'X'*(W+4)]
T=[[-2]*(W+4) for _ in range(H+4)]

from collections import deque
q0=deque()
q0.append([Ch, Cw])
T[Ch][Cw]=0
q1=deque()
c=0

while T[Dh][Dw]==-2 and len(q0)>0:  
  while q0:
    a, b=q0.popleft()
    q1.append([a, b])
    if T[a-1][b]==-2 and S[a-1][b]=='.':
      q0.append([a-1, b])
      T[a-1][b]=c
    if T[a+1][b]==-2 and S[a+1][b]=='.':
      q0.append([a+1, b])
      T[a+1][b]=c
    if T[a][b-1]==-2 and S[a][b-1]=='.':
      q0.append([a, b-1])
      T[a][b-1]=c
    if T[a][b+1]==-2 and S[a][b+1]=='.':
      q0.append([a, b+1])
      T[a][b+1]=c
  c+=1
  while q1:
    a, b=q1.popleft()
    if T[a-2][b-2]==-2 and S[a-2][b-2]=='.':
      q0.append([a-2, b-2])
      T[a-2][b-2]=c
    if T[a-2][b-1]==-2 and S[a-2][b-1]=='.':
      q0.append([a-2, b-1])
      T[a-2][b-1]=c
    if T[a-2][b]==-2 and S[a-2][b]=='.':
      q0.append([a-2, b])
      T[a-2][b]=c
    if T[a-2][b+1]==-2 and S[a-2][b+1]=='.':
      q0.append([a-2, b+1])
      T[a-2][b+1]=c
    if T[a-2][b+2]==-2 and S[a-2][b+2]=='.':
      q0.append([a-2, b+2])
      T[a-2][b+2]=c
    if T[a-1][b-2]==-2 and S[a-1][b-2]=='.':
      q0.append([a-1, b-2])
      T[a-1][b-2]=c
    if T[a-1][b-1]==-2 and S[a-1][b-1]=='.':
      q0.append([a-1, b-1])
      T[a-1][b-1]=c
    if T[a-1][b+1]==-2 and S[a-1][b+1]=='.':
      q0.append([a-1, b+1])
      T[a-1][b+1]=c
    if T[a-1][b+2]==-2 and S[a-1][b+2]=='.':
      q0.append([a-1, b+2])
      T[a-1][b+2]=c
    if T[a][b-2]==-2 and S[a][b-2]=='.':
      q0.append([a, b-2])
      T[a][b-2]=c
    if T[a][b+2]==-2 and S[a][b+2]=='.':
      q0.append([a, b+2])
      T[a][b+2]=c
    if T[a+1][b-2]==-2 and S[a+1][b-2]=='.':
      q0.append([a+1, b-2])
      T[a+1][b-2]=c
    if T[a+1][b-1]==-2 and S[a+1][b-1]=='.':
      q0.append([a+1, b-1])
      T[a+1][b-1]=c
    if T[a+1][b+1]==-2 and S[a+1][b+1]=='.':
      q0.append([a+1, b+1])
      T[a+1][b+1]=c
    if T[a+1][b+2]==-2 and S[a+1][b+2]=='.':
      q0.append([a+1, b+2])
      T[a+1][b+2]=c
    if T[a+2][b-2]==-2 and S[a+2][b-2]=='.':
      q0.append([a+2, b-2])
      T[a+2][b-2]=c
    if T[a+2][b-1]==-2 and S[a+2][b-1]=='.':
      q0.append([a+2, b-1])
      T[a+2][b-1]=c
    if T[a+2][b]==-2 and S[a+2][b]=='.':
      q0.append([a+2, b])
      T[a+2][b]=c
    if T[a+2][b+1]==-2 and S[a+2][b+1]=='.':
      q0.append([a+2, b+1])
      T[a+2][b+1]=c
    if T[a+2][b+2]==-2 and S[a+2][b+2]=='.':
      q0.append([a+2, b+2])
      T[a+2][b+2]=c
      
if T[Dh][Dw]>-1:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=[[c_h-1,c_w-1]]
tugi=[]
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]>kaisuu or map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
    for i in (-1,1):
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]>kaisuu or map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
    
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]>kaisuu+1 or map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    tugi.append([gyou+i,retu+j])
 
wapu=0
 
import copy
 
while True:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu)
        genzai.pop(0)
    
    if len(genzai)==0:
        if len(tugi)!=0:
            genzai=copy.deepcopy(tugi)
            tugi=[]
            wapu+=1
        else:
            print(map[d_h-1][d_w-1])
            exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
mp = [None]+[[None]+[c for c in input()] for _ in range(h)]

mp[ch][cw]=0

from numba import jit

@jit
def mass11(_h, _w):
    l = []
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        side_h, side_w = _h+i, _w+j
        if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
            l.append((side_h, side_w))
    return l 

@jit
def mass55(_h, _w):
    l = []
    for i in range(5):
        for j in range(5):
            side_h, side_w = _h+i-2, _w+j-2
            if side_h>0 and side_h<=h and side_w>0 and side_w<=w:
                l.append((side_h, side_w))
    return l 

@jit
def main():
    d = [(ch,cw)]
    while not len(d) == 0:
        _h, _w = d[0]
        d = d[1:]
        center_point = mp[_h][_w]
        # print(_h, _w)
        for side_h, side_w in mass11(_h, _w):
            side = mp[side_h][side_w]
            # print('side',side_h, side_w,side)
            if not side == '#' and not side == mp[_h][_w]:
                mp[side_h][side_w]=center_point
                d = [(side_h, side_w)] + d
        for side_h, side_w in mass55(_h, _w):
            if mp[side_h][side_w] == '.':
                mp[side_h][side_w]=center_point+1
                d.append((side_h, side_w))

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


main()

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())
Ch+=1
Cw+=1
Dh+=1
Dw+=1
S=['X'*(W+4), 'X'*(W+4)]+['XX'+input()+'XX' for _ in range(H)]+['X'*(W+4), 'X'*(W+4)]
T=[[-2]*(W+4) for _ in range(H+4)]

from collections import deque
q0=deque()
q0.append([Ch, Cw])
T[Ch][Cw]=0
q1=deque()
c=0

while T[Dh][Dw]==-2 and len(q0)>0:  
  while q0:
    a, b=q0.popleft()
    q1.append([a, b])
    if T[a-1][b]==-2 and S[a-1][b]=='.':
      q0.append([a-1, b])
      T[a-1][b]=c
    if T[a+1][b]==-2 and S[a+1][b]=='.':
      q0.append([a+1, b])
      T[a+1][b]=c
    if T[a][b-1]==-2 and S[a][b-1]=='.':
      q0.append([a, b-1])
      T[a][b-1]=c
    if T[a][b+1]==-2 and S[a][b+1]=='.':
      q0.append([a, b+1])
      T[a][b+1]=c
  c+=1
  while q1:
    a, b=q1.popleft()
    if T[a-2][b-2]==-2 and S[a-2][b-2]=='.':
      q0.append([a-2, b-2])
      T[a-2][b-2]=c
    if T[a-2][b-1]==-2 and S[a-2][b-1]=='.':
      q0.append([a-2, b-1])
      T[a-2][b-1]=c
    if T[a-2][b]==-2 and S[a-2][b]=='.':
      q0.append([a-2, b])
      T[a-2][b]=c
    if T[a-2][b+1]==-2 and S[a-2][b+1]=='.':
      q0.append([a-2, b+1])
      T[a-2][b+1]=c
    if T[a-2][b+2]==-2 and S[a-2][b+2]=='.':
      q0.append([a-2, b+2])
      T[a-2][b+2]=c
    if T[a-1][b-2]==-2 and S[a-1][b-2]=='.':
      q0.append([a-1, b-2])
      T[a-1][b-2]=c
    if T[a-1][b-1]==-2 and S[a-1][b-1]=='.':
      q0.append([a-1, b-1])
      T[a-1][b-1]=c
    if T[a-1][b+1]==-2 and S[a-1][b+1]=='.':
      q0.append([a-1, b+1])
      T[a-1][b+1]=c
    if T[a-1][b+2]==-2 and S[a-1][b+2]=='.':
      q0.append([a-1, b+2])
      T[a-1][b+2]=c
    if T[a][b-2]==-2 and S[a][b-2]=='.':
      q0.append([a, b-2])
      T[a][b-2]=c
    if T[a][b+2]==-2 and S[a][b+2]=='.':
      q0.append([a, b+2])
      T[a][b+2]=c
    if T[a+1][b-2]==-2 and S[a+1][b-2]=='.':
      q0.append([a+1, b-2])
      T[a+1][b-2]=c
    if T[a+1][b-1]==-2 and S[a+1][b-1]=='.':
      q0.append([a+1, b-1])
      T[a+1][b-1]=c
    if T[a+1][b+1]==-2 and S[a+1][b+1]=='.':
      q0.append([a+1, b+1])
      T[a+1][b+1]=c
    if T[a+1][b+2]==-2 and S[a+1][b+2]=='.':
      q0.append([a+1, b+2])
      T[a+1][b+2]=c
    if T[a+2][b-2]==-2 and S[a+2][b-2]=='.':
      q0.append([a+2, b-2])
      T[a+2][b-2]=c
    if T[a+2][b-1]==-2 and S[a+2][b-1]=='.':
      q0.append([a+2, b-1])
      T[a+2][b-1]=c
    if T[a+2][b]==-2 and S[a+2][b]=='.':
      q0.append([a+2, b])
      T[a+2][b]=c
    if T[a+2][b+1]==-2 and S[a+2][b+1]=='.':
      q0.append([a+2, b+1])
      T[a+2][b+1]=c
    if T[a+2][b+2]==-2 and S[a+2][b+2]=='.':
      q0.append([a+2, b+2])
      T[a+2][b+2]=c
      
if T[Dh][Dw]>-1:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    elif len(wq)==0 or ( len(wq)>0 and wq[-1]!=[a,b]  ):
        wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    elif len(wq)==0 or ( len(wq)>0 and wq[-1]!=[a,b]  ):
        wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    elif len(wq)==0 or ( len(wq)>0 and wq[-1]!=[a,b]  ):
        wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    elif len(wq)==0 or ( len(wq)>0 and wq[-1]!=[a,b]  ):
        wq.append([a,b])

    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

heap = [(0, ch - 1, cw - 1)]
inf = 1000000000
dist = [[inf for i in range(w)] for _ in range(h)]

while len(heap):
    if dist[dh - 1][dw - 1] != inf:
        break

    d, x, y = heapq.heappop(heap)

    if dist[x][y] != inf:
        continue
    if dist[x][y] < d:
        continue

    dist[x][y] = d

    for dx, dy in [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) != (0, 0)]:
        nx, ny = x + dx, y + dy

        # 近傍なら移動A, そうでなければ移動B
        typa = abs(dx) + abs(dy) == 1
        nd = d + (0 if typa else 1)

        if check_range(nx, ny) and dist[nx][ny] == inf and s[nx][ny] == '.':
            item = (nd, nx, ny)
            heapq.heappush(heap, item)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S

    def pos(h,w):
        return h * W + w

    mx = H*W
    cost = [[INF] * mx for _ in range(mx)]
    edge = [[] for _ in range(mx)]
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#": continue

            x = pos(h,w)
            for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_h,new_w = h+dh,w+dw
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[new_h][new_w] == "#": continue

                y = pos(new_h,new_w)
                cost[x][y] = 0
                cost[y][x] = 0
                edge[x].append(y)
                edge[y].append(x)
                    
 
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if dh == 0 and dw == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    y = pos(new_h,new_w)
                    cost[x][y] = min(cost[x][y],1)
                    cost[y][x] = min(cost[y][x],1)
                    edge[x].append(y)
                    edge[y].append(x)
    

    
    s = pos(Ch,Cw)
    t = pos(Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)

    dist = [INF] * mx # sからxでの最短距離
    dist[s] = 0

    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e in edge[x]:
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                hq.append((dist[e],e))
        
    # print(dist)
    if dist[t] == INF: 
        dist[t] = -1
        
    print(dist[t])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def dijkstra(s, n, edge):
    res = [float("inf")] * n
    res[s] = 0
    hq = []
    heapq.heappush(hq, [0, s])
    while hq:
        ci, i = heapq.heappop(hq)
        if res[i] < ci:
            continue
        for cj, j in edge[i]:
            if res[j] > (res[i] + cj):
                res[j] = res[i] + cj
                heapq.heappush(hq, [res[j], j])
    return res


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

    edge = [[] for j in range(H * W)]
    for i in range(H):
        for j in range(W):
            for k in range(-2, 3):
                for l in range(-2, 3):
                    ni = i + k
                    nj = j + l
                    if k == 0 and l == 0:
                        continue
                    if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                        if abs(k) + abs(l) >= 2:
                            edge[i * W + j].append([1, ni * W + nj])
                        else:
                            edge[i * W + j].append([0, ni * W + nj])
    ans = dijkstra(CH * W + CW, H * W, edge)
    if ans[DH * W + DW] == float("inf"):
        print(-1)
    else:
        print(ans[DH * W + DW])


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())
S = [None]*(H+4)
S[0] = S[1] = S[H+2] = S[H+3] = ["#"]*(W+4)
for i in range(2, H+2):
    S[i] = ["#"] + ["#"] + list(input()) + ["#"] + ["#"]

cost = [[-1 for _ in range(W+3)] for _ in range(H+3)]

Ch += 1
Cw += 1
Dh += 1
Dw += 1

# bfs

warp_times = 0

def warp(i, j, cost, warp_times, q):
    change = 0
    for h in range(i-2, i+3):
        for w in range(j-2, j+3):
            # print(h, w, i, j)
            # print(S[h][w])
            if S[h][w] == "." and cost[h][w] == -1:
                q.append([h, w])
                cost[h][w] = warp_times + 1
                change = 1
    
    return change

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

while True:
    

    same_cost = list()
    no_change = 1

    while len(q):
        # print(q)
        now = q.popleft()
        i = now[0]
        j = now[1]

        cost[i][j] = warp_times
        same_cost.append([i, j])

        if S[i][j-1] == "." and cost[i][j-1] == -1:
            q.append([i, j-1])
            cost[i][j-1] = warp_times
        if S[i][j+1] == "." and cost[i][j+1] == -1:
            q.append([i, j+1])
            cost[i][j+1] = warp_times
        if S[i-1][j] == "." and cost[i-1][j] == -1:
            q.append([i-1, j])
            cost[i-1][j] = warp_times
        if S[i+1][j] == "." and cost[i+1][j] == -1:
            q.append([i+1, j])
            cost[i-1][j] = warp_times
    

    for point in same_cost:
        change = warp(point[0], point[1], cost, warp_times, q)
        if change :
            no_change = 0
    
    warp_times += 1
    
    if no_change:
        break

print(cost[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
def myfunc(h, w):
    if T[h][w] == '.' or T[h][w] == 'True':
        T[h][w] = c
        for i in [(0,1), (0,-1), (1,0), (-1,0)]:
            myfunc(h+i[0], w+i[1])

H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,'#'*(W+2))
S.append('#'*(W+2))
T = [[0] * (W+2) for _ in range(H+2)]
for i in range(H+2):
    for j in range(W+2):
        T[i][j] = S[i][j]
c = 0
myfunc(CH, CW)
warp = True
while T[DH][DW] == '.' and warp == True:
    warp = False
    for i in range(H+2):
        for j in range(W+2):
            if T[i][j] == c:
                 for k in range(-2, 3):
                     for l in range(-2, 3):
                         if 0<=i+k and i+k<H+2 and 0<=j+l and j+l<W+2 and T[i+k][j+l] == '.':
                             warp = True
                             T[i+k][j+l] = 'True'
    c += 1
    for i in range(H+2):
        for j in range(W+2):
            if T[i][j] == 'True':
                myfunc(i, j)
if T[DH][DW] == '#' or T[DH][DW] == '.':
    print(-1)
else:
    print(T[DH][DW])

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
S = [0] * H
for i in range(H):
    S[i] = input()

q = deque([])
dist = [[-1] * W for _ in range(H)]
q.append((ch, cw, 0))
dist[ch][cw] = 0
while len(q) > 0:
    cur = []
    while len(q) > 0:
        cy, cx, d = q.popleft()
        cur.append((cy, cx, d))
        for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            y = cy + dy
            x = cx + dx
            if y < 0 or y >= H or x < 0 or x >= W:
                continue
            if S[y][x] == '#':
                continue
            if dist[y][x] != -1:
                continue
            dist[y][x] = dist[cy][cx]
            q.appendleft((y, x, d))
    for cy, cx, d in cur:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                y = cy + dy
                x = cx + dx
                if y < 0 or y >= H or x < 0 or x >= W:
                    continue
                if S[y][x] == '#':
                    continue
                if dist[y][x] != -1:
                    continue
                dist[y][x] = d + 1
                q.appendleft((y, x, d + 1))
print(dist[dh][dw])

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], 0]) # [dist, x, y, neighbour_only]
    # neighbour_only: 0 -> T, 1-4 -> L, R, D, U, 5-> All
    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 = -1 # L, R, D, U
        N_Flag = 0
        if(dist_pos[3] == 0):
            for dx, dy, i in ( (-1, 0, 1), (1, 0, 2), (0, -1, 3), (0, 1, 4) ):
                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 = i
                    N_Flag += 1
                    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], 0])
            if(N_Flag >1):
                heapq.heappush(deque, [ dists[y][x], x, y, 5 ])
            elif(N_Flag > 0):
                heapq.heappush(deque, [ dists[y][x], x, y, Flag ])
        elif(dist_pos[3] == 5):
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])

        else:
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(dist_pos[3] == 4):
                dy_min = 1
            elif(dist_pos[3] == 3):
                dy_max = 0
            elif(dist_pos[3] == 2):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1], 0])




    #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:
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].c == '.' and S[i][y].reached == False:
            d.append((i, y))
    for i in range(max(0, y-1), min(H, y+2)):
        if S[x][i].c == '.' and S[x][i].reached == False:
            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].c == '.' and S[i][j].searched == False and S[i][j].reached == False:
                d.append((i, j))
            S[i][j].searched = True


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


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import collections
    def bfs(sy, sx, gy, gx):
        q = collections.deque()
        q.append((sy, sx))
        dist = [[-1] * W for _ in range(H)]
        dist[sy][sx] = 0
        dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
        while len(q) != 0:
            h, w = q.popleft()
            d = dist[h][w]
            for x, y in dx:
                h2 = h + y
                w2 = w + x
                if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                    if grid[h2][w2] == ".":
                        if dist[h2][w2] == -1:
                            dist[h2][w2] = d
                            q.append((h2, w2))
                        elif d < dist[h2][w2]:
                            dist[h2][w2] = d
                            q.append((h2, w2))
            for x, y in dx2:
                h2 = h + y
                w2 = w + x
                if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                    if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                        dist[h2][w2] = d + 1
                        q.append((h2, w2))
        return dist[gy][gx]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    grid = [input() for _ in range(H)]
    print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))