Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
maze = [list(input()) for _ in range(H)]
 
def BFS(maze,s,g):
  q1 = deque([s])
  checked = []
  cost = [[-1]*W for _ in range(H)]
  m = 0
  while q1:
    h,w,n = q1.popleft()
    if cost[h][w]<0:
      cost[h][w] = n
      if (h,w)==g: return n
      dp = [(x-2,y-2) for x in range(5) for y in range(5) if (x-2)!=0 or (y-2)!=0]
      for dh,dw in dp:
        if 0<=h+dh<H and 0<=w+dw<W and maze[h+dh][w+dw]==".":
          if (dh,dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
            q1.appendleft((h+dh,w+dw,n))
          else:
            q1.append((h+dh,w+dw,n+1))
  return cost[g[0]][g[1]]
print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-1)))

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=[]

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)
while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=start[0][0]+hh
                    nny=start[0][1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
            del(start[0])
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

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

print(grid[dh][dw])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
class P:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False

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

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

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


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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
from collections import deque

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

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

INF = float("inf")

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

def bfs():
    # すべてのマスを INF で初期化
    d = [[INF] * W for i in range(H)]
    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

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

    # ワープ対象
    que2 = deque([])

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

    # ワープのベクトル
    dx2 = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
    dy2 = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]

    while que: 
        while que:
            p = que.popleft()       
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                print(ans)
                exit()
            que2.append((p[0], p[1]))
            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

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

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

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

qu = deque([])
qu.append((cw-1,ch-1))
while qu:
  x,y=qu.popleft()

  for i in range(max(x-2,0),min(x+3,w)):
    for j in range(max(y-2,0),min(y+3,h)):
      if (x==i and y==j):
        continue
      if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
        if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
          qu.appendleft((i,j))
          ans[j][i] = ans[y][x]
        elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
          ans[j][i]=(ans[y][x]+1)
          qu.appendleft((i,j))

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
visit = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = []
Q.append((0,C))
while Q:
  score,z = heappop(Q)
  x = z[0];y=z[1]
  if visit[x][y]:
    continue
  visit[x][y] = True
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      heappush(Q,(score,u))
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      heappush(Q,(score+1,p))
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[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())

#mp[h][w]
mp = [[0]*w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        mp[i][j] = tmp[j]

#for i in range(h):
#    print(mp[i])


#can reach with 0
q = deque()
dx1 = (-1, 0, 1, 0)
dy1 = (0,-1,0,1)
dx2 = (-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2)
dy2 = (-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)
q.append((ch-1,cw-1))

q2 = deque()

mpc = [[0]*w for _ in range(h)]

mpc[ch-1][cw-1] = 1
while q:
    x, y = q.popleft()
    for i in range(4): 
        nx = x+dx1[i]
        ny = y+dy1[i]
        if nx < 0 or nx >= h:
            continue
        if ny < 0 or ny >= w:
            continue
        if mp[nx][ny] == '.' and mpc[nx][ny] != mpc[x][y]:           
            mpc[nx][ny] = mpc[x][y]
            q.appendleft((nx,ny))

    for i in range(len(dx2)):
        nx = x+dx2[i]
        ny = y+dy2[i]
        if nx < 0 or nx >= h:
            continue
        if ny < 0 or ny >= w:
            continue
        if mp[nx][ny] == '.' and mpc[nx][ny] == 0:       
            mpc[nx][ny] = mpc[x][y] + 1
            q.append((nx,ny))
    
#for i in range(h):
#    print(mpc[i])

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
h,w=[int(x) for x in input().split()]
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

l=[]
for i in range(h):
  s=[x for x in input()]
  l.append(s)


done=[[float('inf') for i in range(w)] for j in range(h)]
move=[[-1,0],[1,0],[0,1],[0,-1]]
m1=[]
for i in range(-2,3):
  for j in range(-2,3):
    if i==0 and j==0:
      continue
    else:
      m1.append([i,j])

def bfs(x,y):
  ans=float('inf')
  que=[[x,y,0]]

  while(que):
    nx,ny,cnt = que.pop(0)
    done[ny][nx]=cnt

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)

    for dx,dy in move:
      mx,my = nx+dx,ny+dy
      if 0<=mx<w and 0<=my<h:
        if l[my][mx]=="." and (cnt<done[my][mx]):
          done[my][mx]=cnt
          que.append([mx,my,cnt])

        elif l[my][mx]=="#" and (cnt<done[my][mx]):
          for i,j in m1:
            if 0<=nx+i<w and 0<=ny+j<h and l[ny+j][nx+i]=="." and cnt+1<done[ny+j][nx+i]:
              done[ny+j][nx+i]=cnt+1
              que.append([nx+i,ny+j,cnt+1])
      
  return ans


ans1=bfs(cw-1,ch-1)

if ans1==float('inf'):
  print(-1)
else:
  print(ans1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10000000)

H, W = map(int, input().split())
si, sj = map(lambda x: int(x) - 1, input().split())
gi, gj = map(lambda x: int(x) - 1, input().split())

maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

direction = [(-1, 0), (0, -1), (0, 1), (1, 0)]
reached_que = deque([[si, sj]])


def bfs(si, sj):
    que = deque([[si, sj]])
    if reached[si][sj] != -1:
        return
    while que:
        h, w = que.popleft()
        for a, b in direction:
            next_h = h + a
            next_w = w + b
            if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
                continue
            if maze[next_h][next_w] == '#':
                continue
            if reached[next_h][next_w] != -1:
                continue
            que.append([next_h, next_w])
            reached[next_h][next_w] = reached[h][w] + 1
            reached_que.append([next_h, next_w])


hankei_5 = [
    [-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, 1],
    [0, 2],
    [1, -2],
    [1, -1],
    [1, 0],
    [1, 1],
    [1, 2],
    [2, -2],
    [2, -1],
    [2, 0],
    [2, 1],
    [2, 2]
]

ans = -1


def bfs2(si, sj):
    kouho = []
    for i, j in hankei_5:
        next_h = si + i
        next_w = sj + j
        if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
            continue
        if maze[next_h][next_w] == '.' and reached[next_h][next_w] == -1:
            kouho.append([next_h, next_w])
    return kouho


def check(si, sj, ans):
    bfs(si, sj)
    if reached[gi][gj] == -1:
        kouho = []
        for r in reached_que:
            a = bfs2(r[0], r[1])
            kouho = a + kouho
        if len(kouho) == 0:
            print(ans)
            exit(0)
        else:
            for k in kouho:
                check(k[0], k[1], ans + 1)
    else:
        ans += 1
        print(ans)
        exit(0)


check(si, sj, -1)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



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 = []
    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

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

        x, y = [dist_pos[1], dist_pos[2] ]
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1 or Maps[y+dy][x+dx]=="#"):
                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] ])

        for dy in range( max(-y, -2), min(H-y, 3) ):
            for dx in range( max(-x, -2), min(W-x, 3) ):
                next = [x+ dx, y+ dy]
                if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                    dists[next[1] ][next[0] ] = dists[y][x]+1
                    heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase
from collections import deque

# %% define phase
global afx
global afy
global ans
ans = 0

def check(s, x, y, o, cnt):
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        if s[x+i][y+j] == '.':
            o.append([x+i, y+j, cnt])
            s[x+i][y+j] = str(cnt)
    return o, s

def wcheck(s, x, y, o, cnt):
    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]:
        if s[x+i][y+j] == '.':
            if [x+i, y+j] not in o:
                o.append([x+i, y+j, cnt+1])    
    return o
    
def bfs(s, x, y, h, w):
    cnt = 0
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, ncnt] = wf.popleft()
        if s[x][y] == '.':
            cnt = ncnt
            s[x][y] = str(cnt)
            f.append([x, y, cnt])
#            print('--------')
#            for si in s:
#                print(si)
#            print('--------')
            while f:
                [x, y, cnt] = f.popleft()
    #            if [x, y, cnt+1] in wf:
    #                wf.remove([x, y, cnt+1])
                if [x, y] == [h, w]:
#                    print('--------')
#                    for si in s:
#                        print(si)
#                    print('--------')
                    wf.clear()
                    return cnt
                f, s = check(s, x, y, f, cnt)
                wf = wcheck(s, x, y, wf, cnt)
    return -1

    
    

# %% input phase
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
ch += 1
cw += 1
dh, dw = list(map(int, input().split()))
dh += 1
dw += 1
s = [[] for _ in range(h+4)]
s[0] = list('#'*(w+4))
s[1] = list('#'*(w+4))
for i in range(h):
    si = input()
    s[i+2] = list('##' + si + '##')
s[h+2] = list('#'*(w+4))
s[h+3] = list('#'*(w+4))

# %% process phase
ans = bfs(s, ch, cw, dh, dw)

    

# %%output phase
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    f = 0
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w:
            if s[nh][nw] == '.':
                stack_append([nh, nw, cnt])
            else:
                f = 1
    if f:
        for dh, dw in nex:
            nh = curh + dh
            nw = curw + dw
            if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
                stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
visit = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = []
Q.append([0,C])
while Q:
  score,z = heappop(Q)
  x = z[0];y=z[1]
  if visit[x][y]:
    continue
  visit[x][y] = True
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      heappush(Q,[score,u])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      heappush(Q,[score+1,p])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])