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: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(5000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
              break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
            break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = 5000
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != 5000:
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(100000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
              break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
            break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] > dist[x]:
                    q.append(x+d)
                    dist[x+d] = dist[xs
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Runtime Error

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,0,0,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[i]=1
    if count<3 or (count==[1,0,0,1] or count==[1,1,0,0] or count==[0,1,1,0] or count==[0,0,1,1]):
      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: Runtime Error

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch = ch - 1
cw = cw - 1
dh = dh - 1
dw = dw - 1

S = []
nextIndex = 0
requiredWarps=[]
indexes = [[-1 for j in range(W)] for i in range(H)]
warpjudgeindexes=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    S.append(input())

def DFS(i,j):
    for a in range(4):
        if a == 0:
            if i+1<H and indexes[i+1][j] == -1 and S[i+1][j]==".":
                indexes[i + 1][j] = indexes[i][j]
                DFS(i+1,j)
        elif a == 1:
            if i>0 and indexes[i-1][j] == -1 and S[i-1][j]==".":
                indexes[i -1][j] = indexes[i][j]
                DFS(i-1,j)
                
        elif a == 2:
            if j+1<W and indexes[i][j+1] == -1 and S[i][j+1]==".":
                indexes[i][j+1] = indexes[i][j]
                DFS(i,j+1)
            
        elif a == 3:
            if j>0 and indexes[i][j-1] == -1 and S[i][j-1]==".":
                indexes[i][j-1] = indexes[i][j]
                DFS(i, j - 1)

def WarpDFS(i, j):
    warp(i,j)
    for a in range(4):
        if a == 0:
            if i+1<H and warpjudgeindexes[i+1][j] == -1 and S[i+1][j]==".":
                warpjudgeindexes[i + 1][j] = warpjudgeindexes[i][j]
                WarpDFS(i+1,j)
        elif a == 1:
            if i>0 and warpjudgeindexes[i-1][j] == -1 and S[i-1][j]==".":
                warpjudgeindexes[i -1][j] = warpjudgeindexes[i][j]
                WarpDFS(i-1,j)
                
        elif a == 2:
            if j+1<W and warpjudgeindexes[i][j+1] == -1 and S[i][j+1]==".":
                warpjudgeindexes[i][j+1] = warpjudgeindexes[i][j]
                WarpDFS(i,j+1)
            
        elif a == 3:
            if j>0 and warpjudgeindexes[i][j-1] == -1 and S[i][j-1]==".":
                warpjudgeindexes[i][j-1] = warpjudgeindexes[i][j]
                WarpDFS(i, j - 1)


def warp(a,b):
    for i in range(5):
        for j in range(5):
            u = a + i - 2
            v = b + j - 2
            if u < 0 or u >= H or v < 0 or v >= W:
                continue
            if indexes[u][v] == -1 and S[u][v] == ".":
                global nextIndex
                indexes[u][v] = nextIndex
                warpjudgeindexes[u][v]=nextIndex
                requiredWarps.append(requiredWarps[indexes[a][b]] + 1)                
                nextIndex+=1
                oneareaSearch(u,v)
                
def oneareaSearch(i, j):
    DFS(i, j)
    WarpDFS(i,j)

requiredWarps.append(0)
nextIndex += 1
indexes[ch][cw] = 0
warpjudgeindexes[ch][cw]=0
oneareaSearch(ch, cw)

if indexes[dh][dw] == -1:
    print("-1")
else:   
    print(requiredWarps[indexes[dh][dw]])

Submission status: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(5000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
              break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.popleft()
    if visited[xx][yy] != False and visited[xx][yy] <= kaisuu:
        continue
    qq.append((xx, yy))
    ls = deque()
    while qq:
        x, y = qq.popleft()
        visited[x][y] = min(kaisuu, visited[x][y])
        ls.append((x, y))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y))
            visited[x+1][y] = min(kaisuu, visited[x+1][y])
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y))
            visited[x-1][y] = min(kaisuu, visited[x-1][y])
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1))
            visited[x][y+1] = min(kaisuu, visited[x][y+1])
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1))
            visited[x][y-1] = min(kaisuu, visited[x][y-1])
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, e+1))
print(-1)

Submission status: Runtime Error

Solution code:
import sys
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 = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            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:
                                #h*W+w,(h+i-2)*W+w+j-2
                                fr,go = h*W+w,(h+i-2)*W+w+j-2
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])

Submission status: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(5000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
            break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                #if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                 #   continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] == -1:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x]:
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(10000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
            break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 遅すぎる！
import math
import sys


h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

x = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if z[i][j]== '.':
            x[i][j] = 0
        else:
            x[i][j] = -1
#print(x)
x[ch-1][cw-1]=1

def tansaku():
    nu = 0
    while 1:
        nutta=0 # 塗ったマス
        for i in range(h):
            for j in range(w):
                if x[i][j] == 1:
                    if i>0:
                        if x[i-1][j]==0:
                            nutta += 1
                            x[i-1][j]=1
                    if j>0:
                        if x[i][j-1]==0:
                            nutta += 1
                            x[i][j-1]=1
                    if i<h-1:
                        if x[i+1][j]==0:
                            nutta += 1
                            x[i+1][j]=1
                    if j<w-1:
                        if x[i][j+1]==0:
                            nutta += 1
                            x[i][j+1]=1
        if nutta==0:
            return nu
        else:
            nu += nutta

def warp():
    y = [[0 for j in range(w)] for i in range(h)]
    nu = 0
    for i in range(h):
        for j in range(w):
            if x[i][j] == 1:
                for p in range(max(i-2,0),min(i+3,h)):
                    for q in range(max(j-2,0),min(j+3,w)):
                        if x[p][q] == 0:
                            y[p][q]=1
                            #print("a",p,q)
                            nu += 1
    for i in range(h):
        for j in range(w):
            if y[i][j]==1:
                x[i][j]=1
                #print("b")
    return nu # これは塗った数よりは多いがnuが1なら0ではない


answer = 0
while(1):
    #print(x,ch,cw,dh,dw)
    nurioe = tansaku()
    #print(x,nurioe)
    if x[dh-1][dw-1]==1:
        print(answer)
        break
    nurioe = warp()
    answer += 1
    #print(x,nurioe)
    if nurioe == 0:
        print(-1)
        break

Submission status: Runtime Error

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = [[(p, t)]]
        broken_set = [[]]
        while next_set:
            while next_set:
                p, t = next_set.pop()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.pop()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(h+2) for _ in range(w+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.popleft()

    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

Submission status: Runtime Error

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(5000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
            break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)