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:
from collections import deque
def walk(x,y,h,w):
    near = []
    if x > 0:
        near.append((x-1,y))
    if y > 0:
        near.append((x,y-1))
    if x < h-1:
        near.append((x+1,y))
    if y < w-1:
        near.append((x,y+1))
    return(near)
def warp(x,y,h,w):
    near = []
    flag1 = False
    flag2 = False
    flag3 = False
    flag4 = False
    if x > 1: flag1 = True
    if y > 1: flag2 = True
    if x < h-2: flag3 = True
    if y < w-2: flag4 = True
    if flag1:
        near.append((x-2,y))
        if flag2:
            near.append((x,y-2))
            near.append((x-2,y-2))
            near.append((x-1,y-2))
            near.append((x-2,y-1))
            near.append((x-1,y-1))
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+2,y-2))
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            elif x < h-1:
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            else:
                if flag4:
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
        elif y > 0:
            near.append((x-2,y-1))
            near.append((x-1,y-1))
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+1,y-1))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            elif x < h -1:
                near.append((x+1,y-1))
                if flag4:
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            else:
                if flag4:
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
        else:
            if flag3:
                near.append((x+2,y))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            elif x < h -1:
                if flag4:
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
            else:
                if flag4:
                    near.append((x-1,y+2))
                    near.append((x-2,y+2))
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
                    near.append((x-2,y+1))
    elif x > 0:
        if flag2:
            near.append((x,y-2))
            near.append((x-1,y-2))
            near.append((x-1,y-1))
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+2,y-2))
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
            elif x < h -1:
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
        elif y > 0:
            near.append((x-1,y-1))
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+1,y-1))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
            elif x < h-1:
                near.append((x+1,y-1))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
        else:
            if flag3:
                near.append((x+2,y))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
            elif x < h-1:
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x-1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
                    near.append((x-1,y+2))
                    near.append((x-1,y+1))
                elif y < w-1:
                    near.append((x-1,y+1))
    else:
        if flag2:
            near.append((x,y-2))
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+2,y-2))
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                    near.append((x-1,y+1))
            elif x < h -1:
                near.append((x+1,y-1))
                near.append((x+1,y-2))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
        elif y > 0:
            if flag3:
                near.append((x+2,y))
                near.append((x+2,y-1))
                near.append((x+1,y-1))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
            elif x < h-1:
                near.append((x+1,y-1))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
        else:
            if flag3:
                near.append((x+2,y))
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+2,y+2))
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
                    near.append((x+2,y+1))
            elif x < h-1:
                if flag4:
                    near.append((x,y+2))
                    near.append((x+1,y+2))
                    near.append((x+1,y+1))
                elif y < w-1:
                    near.append((x+1,y+1))
            else:
                if flag4:
                    near.append((x,y+2))
    return near

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

#キュー
queue = deque([(0,walk(ch-1,cw-1,h,w)),(1,warp(ch-1,cw-1,h,w))]) #(ワープした回数, 隣接している頂点)
#訪問済みの頂点を記録する
visited = {(ch-1,cw-1):0}
while queue != deque([]):
    label = queue.popleft()
    for i in label[1]:
        if s[i[0]][i[1]] == "#":
            continue
        if not i in visited:
            visited[(i[0],i[1])] = label[0]
            if (i[0],i[1]) == (dh-1,dw-1):
                continue
            queue.append((label[0],walk(i[0],i[1],h,w)))
            queue.append((label[0]+1,warp(i[0],i[1],h,w)))
        else:
            if label[0] < visited[i]:
                visited[i] = label[0]
                if (i[0],i[1]) == (dh-1,dw-1):
                    continue
                queue.append((label[0],walk(i[0],i[1],h,w)))
                queue.append((label[0]+1,warp(i[0],i[1],h,w)))
if not (dh-1,dw-1) in visited:
    print(-1)
else:
    print(visited[(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())
S = []
for h in range(H):
    S.append(list(input()))
H -= 1;W -= 1;CH -= 1;CW -= 1;DH -= 1;DW -= 1
from collections import deque
Q = deque([[CH,CW,0]])
ans = 9999999999999999999999
able = False
while Q:
    q = Q.popleft()
    for w in range(-2,3):
        for h in range(-2,3):
            # 動かないのは処理しない
            if w == 0 and h == 0:
                pass
            else:
                # 場外判定
                # from IPython.core.debugger import Pdb; Pdb().set_trace()
                if q[0] + h >= 0 and q[0] + h <= H and q[1] + w >= 0 and q[1] + w <= W:
                    # 壁判定
                    if S[q[0]+h][q[1]+w] != '#':
                        # 徒歩判定(4パターン)
                        elif (w == -1 and h == 0) or (w == 0 and h == -1) or (w == 1 and h == 0) or (w == 0 and h == 1):
                                # ゴールの場合
                                if q[0]+h == DH and q[1]+w == DW:
                                    ans = min(ans,q[2])
                                    able = True
                                    if ans == 0:
                                      print(ans)
                                      exit()
                                # 未処理の場合
                                elif S[q[0]+h][q[1]+w] == '.':
                                    S[q[0]+h][q[1]+w] = str(q[2])
                                    Q.append([q[0]+h,q[1]+w,q[2]])
                                # 処理済の場合
                                else:
                                    if int(S[q[0]+h][q[1]+w]) > q[2]:
                                        S[q[0]+h][q[1]+w] = str(q[2])
                                        Q.append([q[0]+h,q[1]+w,q[2]])
                        # ワープの場合
                        else:
                            if q[0]+h == DH and q[1]+w == DW:
                                ans = min(ans,q[2]+1)
                                able = True
                            elif S[q[0]+h][q[1]+w] == '.':
                                S[q[0]+h][q[1]+w] = str(q[2]+1)
                                Q.append([q[0]+h,q[1]+w,q[2]+1])
                            else:
                                if int(S[q[0]+h][q[1]+w]) > q[2]+1:
                                    S[q[0]+h][q[1]+w] = str(q[2]+1)
                                    Q.append([q[0]+h,q[1]+w,q[2]+1])                            
print(ans) if able else print(-1)

Submission status: Runtime Error

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

S = []
for _ in range(H):
    s = list(map(str, input()))
    S.append(s)


node = [[-1 for i in range(W)] for j in range(H)]
node[ch-1][cw-1] = 0


start = [[ch-1, cw-1]]

houkou = [[0, 1],[0, -1], [1, 0], [-1,0]]

ans = 0

while len(start) != 0:
        road = start.pop(0)
        h = road[0]
        w = road[1]
        for i in houkou:

            if 0 <= h+i[0] and h+i[0] < H:
                if 0 <= w+i[1] and w+i[1] < W:
                    if S[h+i[0]][w+i[1]] == '.':
                        node[h+i[0]][w+i[1]] = node[h][w]
                        start.append([h+i[0], w+i[1]])

        if node[dh-1][dw-1] == 0:
            break

l = [[ch-1, cw-1]]
q = [[ch-1, cw-1]]

if node[dh-1][dw-1] != 0:
    while len(l)!=0:
        ll = l.pop(0)
        h,w = ll[0], ll[1]
        if S[h][w] == '.':
                for x in [-2, -1, 0, 1, 2]:
                    for y in [-2, -1, 0, 1, 2]:
                        if 0 <= h+x < H:
                            if 0 <= w+y < W:
                                if S[h+x][w+y] == '.' :
                                    if (node[h+x][w+y] > node[h][w]) or (node[h+x][w+y] == -1):
                                        if [x, y] in [[1,0],[-1,0],[0,1],[0,-1]]:
                                            node[h+x][w+y] = node[h][w]
                                            if [h+x,w+y] in q:
                                                continue
                                            l.append([h+x,w+y])
                                            q.append([h+x,w+y])

                                        else:
                                            node[h+x][w+y] = node[h][w] + 1
                                            if [h+x,w+y] in q:
                                                continue
                                            l.append([h+x,w+y])
                                            q.append([h+x,w+y])
                                            




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

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    H, W, M = in_nn()

    hcnt = [0] * H
    wcnt = [0] * W

    hw = []

    for i in range(M):
        h, w = in_nn()
        h, w = h - 1, w - 1
        hw.append((h, w))

    for i in range(M):
        h, w = hw[i]
        hcnt[h] += 1
        wcnt[w] += 1

    max_h = max(hcnt)
    max_w = max(wcnt)

    ans = max_h + max_w - 1

    h_index = []
    w_index = []

    for i in range(H):
        if hcnt[i] == max_h:
            h_index.append(i)

    for i in range(W):
        if wcnt[i] == max_w:
            w_index.append(i)

    hw_set = set(hw)
    # print(h_index)
    # print(w_index)

    hn = len(h_index)
    wn = len(w_index)

    f = False
    for i in range(hn):
        for j in range(wn):
            if (h_index[i], w_index[j]) not in hw_set:
                f = True

        if f or hn * i > 10**7:
            ans += 1
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
hw=input("").split(" ")
h=int(hw[0])
w=int(hw[1])
hhh=input("").split(" ")
ch=int(hhh[0])-1
dh=int(hhh[1])-1
www=input("").split(" ")
cw=int(www[0])-1
dw=int(www[1])-1
liss=[]
lisc=[]
for _1 in range(h):
    tmplis1=[]
    tmplis3=[]
    tmplis2=input("")
    for i in range(w):
        tmplis1+=[tmplis2[i]]
        if(tmplis2[i]=="#"):
            tmplis3+=[-1]
        else:
            tmplis3+=[1000]
    
    lisc+=[tmplis3]
    liss+=[tmplis1]
    
frag1=0
baket=[[ch,cw]]
nbaket=[]
step=0
while(lisc[dh][dw]==1000 and frag1==0):
    cnt=0
    while(len(baket)>cnt):
        tmp=baket[cnt]
        tmp1=tmp[0]
        tmp2=tmp[1]
        
        if(tmp2<w-1 and lisc[tmp1][tmp2+1]==1000):
            lisc[tmp1][tmp2+1]==step
            baket+=[[tmp1,tmp2+1]]
        
        
        if(tmp2>0 and lisc[tmp1][tmp2-1]==1000):
            lisc[tmp1][tmp2-1]==step
            baket+=[[tmp1,tmp2-1]]
        if(tmp1<h-1 and lisc[tmp1+1][tmp2]==1000):
            lisc[tmp1+1][tmp2]==step
            baket+=[[tmp1+1,tmp2]]
        if(tmp1>0 and lisc[tmp1-1][tmp2]==1000):
            lisc[tmp1-1][tmp2]==step
            baket+=[[tmp1-1,tmp2]]
        cnt+=1
    step+=1
    for i in baket:
        for ii in range(-2,3):
            for iii in range(-2,3):
                itm1=i[0]+ii
                itm2=i[1]+iii
                if (itm1<h-1 and itm1>-1 and itm2<w-1 and itm2>-1 and lisc[itm1][itm2]==1000):
                    lisc[itm1][itm2]=step
                    nbaket+=[[itm1,itm2]]
    if(len(nbaket)==0):
        frag1=1
if(lisc[dw][dh]==1000):
    print(-1)
else:
    print(lisc[dw][dh])

Submission status: Runtime Error

Solution code:
m = []
h, w = 0, 0

def is_not_road(x, y):
    return x < 0 or x >= h or y < 0 or y >= w or m[x][y] < 0

def paint(x, y, c):
    global m
    if is_not_road(x, y):
        return
    if m[x][y] > 0 and m[x][y] <= c:
        return

    m[x][y] = c
    paint(x - 1, y, c)
    paint(x + 1, y, c)
    paint(x, y - 1, c)
    paint(x, y + 1, c)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if abs(i) + abs(j) <= 1: continue
            paint(x + i, y + j, c + 1)

def main():
    global h, w
    h, w = list(map(int, input().split()))
    cx, cy = list(map(lambda c: int(c) - 1, input().split()))
    dx, dy = list(map(lambda c: int(c) - 1, input().split()))

    for _ in range(h):
        s = input()
        m.append([0 if c == '.' else -1 for c in s])

    paint(cx, cy, 1)
    if m[dx][dy] > 0:
        print(m[dx][dy] - 1)
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
now_position = [list(map(int,input().split()))]
goal_position = list(map(int,input().split()))
now_position[0].append(0)
maze = [list(input()) for i in range(W)]
d = [[0,1],[0,-1],[1,0],[-1,0]]
e = [[0,2],[0,-2],[2,0],[-2,0],[1,1],[1,-1],[-1,1],[-1,-1],[2,2],[2,-2],[-2,2],[-2,-2],[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]]
count = float('inf')
while now_position:
  y,x,z = now_position.pop()
  if y==goal_position[0] and x==goal_position[1]:
    count = min(count,z)
  for dy,dx in d:
    ny,nx = y+dy,x+dx
    if 0<ny<=H and 0<nx<=W and maze[ny-1][nx-1]!='#':
      now_position.append([ny,nx,z])
  for dy,dx in e:
    ny,nx = y+dy,x+dy
    if 0<ny<=H and 0<nx<=W and maze[ny-1][nx-1]!='#':
      now_position.append([ny,nx,z+1])
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
Input = input().split()
H = int(Input[0])
W = int(Input[1])
Start = [int(Input[2])-1,int(Input[3])-1]
Goal  = [int(Input[4])-1,int(Input[5])-1]
Maze  = Input[6:]
Dist  = np.full((H,W),np.inf)
Queue = deque()
Queue.append(Start)
Dist[Start[0],Start[1]] = 0
while Queue:
    NowH,NowW = Queue.popleft()
    Cost = Dist[NowH,NowW]
    for NewH in range(NowH-2,NowH+3):
        for NewW in range(NowW-2,NowW+3):
            if 0<=NewH<H and 0<=NewW<W:
                if Maze[NewH][NewW]=='#':
                    NewCost = Cost+1    
                else:
                    NewCost = Cost
                if NewCost<Dist[NewH,NewW]:
                    Dist[NewH,NewW] = NewCost
                    Queue.append([NewH,NewW])
print(int(Dist[Goal[0],Goal[1]]))

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().split()))
Ch, Cw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
maze = []
for i in range(h):
    maze.append([j for j in input()])

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

from collections import deque
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

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


    sx = Ch
    sy = Cw
    
    gx = Dh
    gy = Dw

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    
    increment = 0
    
    while que:
    # キューが空になるまでループ
        while que:
            # キューの先頭を取り出す
            p = que.popleft()
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                break

            for i in range(4):
                    # 移動した後の点を (nx, ny) とする
                    nx = p[0] + dx[i]
                    ny = p[1] + dy[i]

                    # 移動が可能かの判定とすでに訪れたことがあるかの判定
                    # d[nx][ny] != INF なら訪れたことがある
                    if 0 <= nx < w and 0 <= ny < h and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                            que.append((nx, ny))
                            d[nx][ny] = d[p[0]][p[1]]
                            
        for i in range(h):
            for j in range(w):
                if d[i][j] == increment:
                    for p in range(8):
                        # 移動した後の点を (nx, ny) とする
                        nx = i + wx[p]
                        ny = j + wy[p]
                        # 移動が可能かの判定とすでに訪れたことがあるかの判定
                        # d[nx][ny] != INF なら訪れたことがある
                        if 0 <= nx < w and 0 <= ny < h and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                                que.append((nx, ny))
                                d[nx][ny] = d[i][j] + 1
        increment += 1
                            
    return d[gx][gy]

print(bfs() if bfs() != float("inf") else -1)

Submission status: Runtime Error

Solution code:
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def dfs(h, w):
    seen[h][w] = True

    for dir in range(4):
        nh = h + dx[dir]
        nw = w + dy[dir]

        if nh < 0 or nh >= H or nw < 0 or nw >= W: continue
        if field[nh][nw] == "#": continue

        if seen[nh][nw]: continue

        dfs(nh, nw)


def dfs2(h, w):
    seen2[h][w] = True

    for nh in range(h+3):
        for nw in range(w+3):

            if nh < 0 or nh >= H or nw < 0 or nw >= W: continue
            if field[nh][nw] == "#": continue
            if seen2[nh][nw]: continue

            dfs2(nh, nw)


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
field = [list(input()) for _ in range(H)]
seen = [[False] * (W) for _ in range(H)]
seen2 = [[False] * (W) for _ in range(H)]

cnt = 0
for h in range(H):
    for w in range(W):
        if seen[h][w]: continue
        if field[h][w] == "#": continue
        dfs(h, w)
        cnt += 1
dfs2(ch, cw)
if seen2[dh][dw]:
    print(cnt-1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    H,W,M = map(int,input().split())
    h = [[0,i] for i in range(H)]
    w = [[0,i] for i in range(W)]
    HW = np.zeros((H,W))
    for i in range(M):
        tmp_0,tmp_1 = map(int,input().split())
        tmp_0 -= 1
        tmp_1 -= 1
        h[tmp_0][0] += 1
        w[tmp_1][0] += 1
        HW[tmp_0][tmp_1] += 10
    
    list.sort(h, reverse=True)
    list.sort(w, reverse=True)
    max_h = h[0][0]
    max_w = w[0][0]
    ans = max_h + max_w
    for i in range(len(h)):
        if h[i][0] < max_h:
            break
        HW[h[i][1]] += 1
        
    for i in range(len(w)):
        if w[i][0] < max_w:
            break
        HW[:,w[i][1]] += 1
    
    if 2 not in HW:
        ans -= 1
    
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
        dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])