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 i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0
dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0

def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          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.append([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.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

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 -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]

search = [[float('inf')] * W for _ in range(H)]
visit = [[False] * W for _ in range(H)]
dq = deque([])

dq.append((Ch, Cw))
search[Ch][Cw] = 0
visit[Ch][Cw] = True

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    cur_row, cur_col = dq.popleft()
    cur_step = search[cur_row][cur_col]

    dq_in = deque([])
    dq_in.append((cur_row, cur_col))

    warp_can = []
    while dq_in:
        r, c = dq_in.popleft()

        flag = False
        for dir_y, dir_x in direction:
            new_row = r + dir_x
            new_col = c + dir_y

            if new_row < 0 or new_row >= H or new_col < 0 or new_col >= W:
                continue

            if visit[new_row][new_col]:
                continue

            if grid[new_row][new_col] == '#':
                if not flag:
                    warp_can.append((r, c))
                    flag = True
            else:
                search[new_row][new_col] = cur_step
                dq_in.append((new_row, new_col))

        visit[r][c] = True

    next_island = []
    for w_row, w_col in warp_can:
        for r in range(-2, 3):
            x_row = w_row + r
            for c in range(-2, 3):
                if r == 0 and c == 0:
                    continue

                x_col = w_col + c

                if x_row < 0 or x_row >= H or x_col < 0 or x_col >= W:
                    continue

                if grid[x_row][x_col] == '#':
                    continue

                if visit[x_row][x_col]:
                    continue

                next_island.append((x_row, x_col))

    for x, y in next_island:
        dq.append((x, y))
        search[x][y] = min(cur_step + 1, search[x][y])


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

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)

A = 10**18
B = 10**9

stack = deque([(ch-1)*A + (cw-1)*B + 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))

d[(ch-1) * w + (cw-1)] = 0

T = ((-1,0), (1,0), (0,1), (0,-1))

while stack:
    x = stack_popleft()
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    if d[curh * w + curw] < cnt: continue
    d[curh * w + curw] = cnt

    for dh, dw in T:
        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:
            d[nh * w + nw] = cnt
            stack_append(nh*A + nw*B + cnt)
    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:
            d[nh * w + nw] = cnt + 1
            stack_append(nh*A + nw*B + 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
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
Es=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[]
for i in range(-2,3):
    for j in range(-2,3):
        wap.append((i,j))
wap.remove((0,0))
for each in walk:
    wap.remove(each)
cand=[start]
dis[start[0]][start[1]]=0
flag=False
edge=[]
while len(cand)>0:
    #print(dis)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
        elif h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==1 and Es[hh][ww]>cost:
            Es[hh][ww]=cost
            edge.append((hh,ww,cost))
            #print(edge)
    if len(cand)==0:
        for place in edge:
            hh,ww,cost=place
            for each in wap:
                h1,w1=hh+each[0],ww+each[1]
                #print(h1,w1)
                if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                    dis[h1][w1]=cost+1
                    cand.append((h1,w1,cost+1))
        edge=[]
        #print(cand)
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-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())
s = [[-1]*(w+4)]
s.append([-1]*(w+4))
for i in range(h):
  s.append(list(input()))
  for j in range(w):
    if s[i+2][j] == '#':
      s[i+2][j] = -1
    else:
      s[i+2][j] = 10**6
  s[i+2].insert(0,-1)
  s[i+2].insert(0,-1)
  s[i+2].append(-1)
  s[i+2].append(-1)
s.append([-1]*(w+4))
s.append([-1]*(w+4))
s[ch+1][cw+1] = 0

stack = []
stack.append([ch+1,cw+1])
while True:
  if len(stack)==0:
    break
  st = stack.pop()
  sh = st[0]
  sw = st[1]
  if s[sh-1][sw]>s[sh][sw]:
    s[sh-1][sw] = s[sh][sw]
    stack.append([sh-1,sw])
  if s[sh][sw-1]>s[sh][sw]:
    s[sh][sw-1] = s[sh][sw]
    stack.append([sh,sw-1])
  if s[sh+1][sw]>s[sh][sw]:
    s[sh+1][sw] = s[sh][sw]
    stack.append([sh+1,sw])
  if s[sh][sw+1]>s[sh][sw]:
    s[sh][sw+1] = s[sh][sw]
    stack.append([sh,sw+1])
  shh = sh-2
  sww = sw-2
  for i in range(5):
    for j in range(5):
      if shh+i>1 and sww+j>1 and s[shh+i][sww+j]>s[sh][sw]+1 and (s[shh-1][sww]==-1 or s[shh+1][sww]==-1 or s[shh][sww-1]==-1 or s[shh][sww+1]==-1):
        s[shh+i][sww+j] = s[sh][sw]+1
        stack.append([shh+i,sww+j])
      
if s[dh+1][dw+1]==10**6:
  print(-1)
else:
  print(s[dh+1][dw+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 in range(5):
        a = i-2
        for j in range(5):
            b = j-2
#            if x+a>=0 and y+b>=0 and \
#            x+a<=h+2 and y+b<=w+2 and\
#            s[x+a][y+j] == '.':
            if s[x+a][y+b] == '.':
                if [x+a, y+b] not in o:
                    o.append([x+a, y+b, cnt+1])    
    return o
    
def bfs(s, x, y, h, w):
    cnt = 0
    s[x][y] = str(cnt)
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, cnt] = wf.popleft()
        f.append([x, y, cnt])
        while f:
            [x, y, cnt] = f.popleft()
            if [x, y] in wf:
                wf.remove([x, y, cnt+1])
            if [x, y] == [h, w]:
                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
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [[None] *M for _ in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1] *M for _ in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    flug=True
    while flug==True:
        flug=False
        while len(todox) !=0:
            x=todox.popleft()
            y=todoy.popleft()
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx>=0 and nx<M and ny>=0 and ny<N :
    
    
                            
                    if S[ny][nx]==".":
                        
                        
                        
                        if seen[ny][nx] ==-1:
                            #print("mohu",nx,ny)
                            seen[ny][nx] =seen[y][x]
                            todox.append(nx)
                            todoy.append(ny)
                        elif seen[ny][nx] >seen[y][x]:
                            seen[ny][nx] =seen[y][x]
                            todox.append(nx)
                            todoy.append(ny)
        for k in range(N):
            for j in range(M):
                if seen[k][j]==count:
                    for i in range(20):
                        nx=j+ddx[i]
                        ny=k+ddy[i]
                        if nx>=0 and nx<M and ny>=0 and ny<N :
                            if S[ny][nx]==".":
                                if seen[ny][nx] ==-1:
                                    #print("mohu",nx,ny)
                                    seen[ny][nx] =seen[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                                
                    flug=True
                    
        count+=1

        
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

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=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)

def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
l=[[Ch-1,Cw-1]]
l=deque(l)
maze[Ch-1][Cw-1]=0
while l:
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]

  target=l[0]
  h,w=target
  l.popleft()
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      l.appendleft([h+vector[0],w+vector[1]])
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      maze[h+i//5-2][w+i%5-2]=maze[h][w]+1
      l.append([h+i//5-2,w+i%5-2])
print(maze[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
smat=[]
smat.append([False]*(W+4))
smat.append([False]*(W+4))
for _ in range(H):
  line=[False,False]+[x=="." for x in input()]+[False,False]
  smat.append(line)
smat.append([False]*(W+4))
smat.append([False]*(W+4))
#print(smat)

graph=defaultdict(list)
#graph[i]: iから出る道の[重み,行先]の辞書
for i in range(2,H+2):
  for j in range(2,W+2):
    if not smat[i][j]:
      continue
    
    if smat[i-1][j]:
      graph[(i,j)].append([(i-1,j),0])
    if smat[i+1][j]:
      graph[(i,j)].append([(i+1,j),0])
    if smat[i][j-1]:
      graph[(i,j)].append([(i,j-1),0])
    if smat[i][j+1]:
      graph[(i,j)].append([(i,j+1),0])
    
    if smat[i-1][j-1]:
      graph[(i,j)].append([(i-1,j-1),1])
    if smat[i-1][j+1]:
      graph[(i,j)].append([(i-1,j+1),1])
    if smat[i+1][j-1]:
      graph[(i,j)].append([(i+1,j-1),1])
    if smat[i+1][j+1]:
      graph[(i,j)].append([(i+1,j+1),1])

    for k in range(-2,3):
      if smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2):
      if smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if smat[i+k][j+2]:
        graph[(i,j)].append([(i+k,j+2),1])

#print(dist)
#print(prev)

dist_mat=[[-1]*(W+4) for _ in range(H+4)]
queue=[(Ch+1,Cw+1)]
d=0
while queue:
  new_queue=set()

  while queue:
    ux,uy=queue.pop()
    if ux==Dh+1 and uy==Dw+1:
      print(d)
      sys.exit(0)
    dist_mat[ux][uy]=d
    
    for v,w in graph[(ux,uy)]:
      vx,vy=v
      if dist_mat[vx][vy]!=-1:
        continue
      if w==0:
        queue.append(v)
      else:
        new_queue.add(v)

  queue=list(new_queue)
  d+=1
#print(dist)

print(-1)

Submission status: Time Limit Exceeded

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

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

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False
    local_area = deque([])

    while q:
        p = q.popleft()
        local_area.append((p[0],p[1]))
        if p[0] == gx and p[1] == gy:
            goal = True
            break

        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]]
        if len(q) == 0 and goal == False:
            while local_area:
                p = local_area.popleft()
                for i in range(-2,3):
                    for j in range(-2,3):
                        nx = p[0]+i 
                        ny = p[1]+j
                        if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                            q.append((nx,ny))
                            d[ny][nx] = d[p[1]][p[0]] + 1                        

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

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

ch -= 1
cw -= 1
dh -= 1
dw -= 1

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
bomb_count = 0

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    se = set()#被りがないかの確認

    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#":
            continue
        else:
            if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                if lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    se.add((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    if (nx,ny) not in se:
                        que.appendleft((nx,ny))
                        lin[nx][ny] = lin[x][y]+1# 魔法の力で行く

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

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)

A = 10**18
B = 10**9

stack = deque([(ch-1)*A + (cw-1)*B + 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))

d[(ch-1) * w + (cw-1)] = 0

while stack:
    x = stack_popleft()
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    if d[curh * w + curw] < cnt: continue
    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 and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            stack_append(nh*A + nw*B + cnt)
    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:
            d[nh * w + nw] = cnt + 1
            stack_append(nh*A + nw*B + 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:
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]
count=0
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
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]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          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.append([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.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[200000]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    H, W = map( int, input().split())
    Ch, Cw = map( lambda x: int(x)-1, input().split())
    Dh, Dw = map( lambda x: int(x)-1, input().split())
    S = [ input() for _ in range(H)]
    k = 10**7
    R = [ [k]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                R[i][j] = -1
    R[Ch][Cw] = 0
    T = [ [False]*W for _ in range(H)]
    d = deque([(Ch, Cw)])
    MW = [(-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 d:
        # print(d)
        # print(R)
        x, y = d.popleft()
        if T[x][y]:
            continue
        else:
            T[x][y] = True
        magic = R[x][y]
        if x == Dh and y == Dw:
            break
        if x > 0:
            if R[x-1][y] > magic:
                R[x-1][y] = magic
                d.appendleft((x-1,y))
        if x < H-1:
            if R[x+1][y] > magic:
                R[x+1][y] = magic
                d.appendleft((x+1,y))
        if y > 0:
            if R[x][y-1] > magic:
                R[x][y-1] = magic
                d.appendleft((x,y-1))
        if y < W-1:
            if R[x][y+1] > magic:
                R[x][y+1] = magic
                d.appendleft((x,y+1))
        for a, b in MW:
            tx, ty = x+a, y+b
            if tx < 0 or tx > H-1:
                continue
            if ty < 0 or ty > W-1:
                continue
            if R[tx][ty] > magic:
                R[tx][ty] = magic+1
                d.append((tx,ty))

    if R[Dh][Dw] == k:
        print(-1)
    else:
        print(R[Dh][Dw])
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


def bfs():
    for y in range(h):
        for x in range(w):
            if s[y][x]=='.':
                s[y][x]=math.inf


    s[c[0]-1][c[1]-1]=0
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1),(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<=y+i<h and 0<=x+j<w:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if dist!='#':
                    if i*i+j*j==1:
                        if dist>s[y][x]:
                            s[nexty][nextx]=s[y][x]
                            que.append([nexty,nextx])
                    elif dist>s[y][x]+1:
                        s[nexty][nextx]=s[y][x]+1
                        que.append([nexty,nextx])

    if s[d[0]-1][d[1]-1]==math.inf:
        print(-1)
    else:
        print(s[d[0]-1][d[1]-1])

bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [list(input()) for i in range(H)]
INF = float("inf")

distance = [[INF]*W for i in range(H)]
Q = deque([[C_h,C_w,0]])
while Q:
    h,w,d = Q.popleft()
    if d >= distance[h][w]:
        continue
    distance[h][w] = d
    for i_h,i_w in [[h+1,w],[h-1,w],[h,w+1],[h,w-1]]:
        if min(i_h,i_w) < 0 or i_h >= H or i_w >= W:
            continue
        if S[i_h][i_w] != "#":
            Q.append([i_h,i_w,d])
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j)<=1:
                continue
            i_h,i_w = h+i,w+j
            if min(i_h,i_w) < 0 or i_h >= H or i_w >= W:
                continue
            if S[i_h][i_w] != "#":
                Q.append([i_h,i_w,d+1])
ans = distance[D_h][D_w]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
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())
slist = [input() for i in range(h)]

if ch == dh and dw == cw:
    print(0)
    exit()

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo_que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        #print(sh, sw, count)
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    print(count)
                    exit()
                if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[(sh + ph, sw + pw)] = count
                    memo_que.append([sh + ph, sw + pw, count])
    templist = []
    for sh, sw, count in list(memo_que):
        #print(sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if sh + ph == dh - 1 and sw + pw == dw - 1:
                            print(count + 1)
                            exit()
                        if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[(sh + ph, sw + pw)] = count + 1
                            templist.append([sh + ph, sw + pw, count + 1])
    memo_que = deque(templist)

print(-1)