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:
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
            for i in range(len(tree)):
                tree[i] = set(tree[i])
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = []
for i in range(h):
  s.append(input())
cango = {}
d = {}
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      continue
    else:
      cango[i*w+j] = {}
      d[i*w+j] = -1
    for x in range(max(0, j-2), min(w, j+3)):
      for y in range(max(0, i-2), min(h, i+3)):
        if x == i and y == j:
          continue
        if s[x][y] == '.':
          if abs(i-x) + abs(j-y) == 1:
            cango[i*w+j][x*w+y] = 0
          else:
            cango[i*w+j][x*w+y] = 1
que = [ch*w+cw]
d[ch*w+cw] = 0
while que:
  v = que.pop(0)
  print("v = " + str(v))
  for vv in cango[v]:
    if d[vv] != -1:
      continue
    elif d[vv] == -1:
      print("vv = " + str(vv))
      d[vv] = 0
    d[vv] = d[v] + cango[v][vv]
    que.append(vv)
    if vv == dh*w+dw:
      print(d[vv])
      sys.exit()
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w = list(map(int,input().split(' ')))
sy,sx = list(map(int,input().split(' ')))
gy,gx = list(map(int,input().split(' ')))
maze = [[None]*w]*h
for i in range(h):
    maze[i] = list(input())

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

d = [[float("inf")] * w for i in range(h)]
warp = [[float("inf")] * w for i in range(h)]

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


que = deque([])

que.append((sy,sx))

d[sy][sx] = 0
warp[sy][sx] = 0


while que:
    p = que.popleft()

    if p[0] == gy and p[1] == gx:
        break

    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]

        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):

            que.append((ny, nx))

            if warp[p[0]][p[1]] < warp[ny][nx]:
                warp[ny][nx] = warp[p[0]][p[1]]
            d[ny][nx] = d[p[0]][p[1]] + 1
    for i,j in [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2], [-1,-2],[-1,-1],[-1,1],[-1,2],[-0,-2],[-0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
        ny = p[0]+i
        nx = p[1]+j
        if 0 <= nx < w and 0 <= ny < h:

            if maze[ny][nx] != "#":
                if d[ny][nx] == float("inf"):
                    que.append((ny, nx))
                    warp[ny][nx] = warp[p[0]][p[1]] + 1
                if not d[ny][nx] == float("inf"):
                    if warp[p[0]][p[1]]+1 < warp[ny][nx]:
                        warp[ny][nx] = warp[p[0]][p[1]] + 1
                        que.append((ny, nx))
if not warp[gy][gx] == float("inf"):
    print(warp[gy][gx])
else:
    print(-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()))
dp = [[1e10+1 for __ in range(w)] for _ in range(h)]
isFirst = True
S = [[] for _ in range(h)]
for i in range(h):
    S[i] = list(input())
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])

for i in range(h):
    S[i] = list(input())
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])
# print(dp)
if dp[ch-1][cw-1] == 1e10+1 or dp[dh-1][dw-1] == 1e10+1:
    print(-1)
else:
    print(abs(dp[ch-1][cw-1] - dp[dh-1][dw-1]))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
C = np.frombuffer(read(), dtype="S1").reshape(
    H, -1)[:, :W]  # 整形の仕方すごい。一番右の列はいらないから消している。
C = 1 * (C == b'#')  # エレガント


def search_empty(C, i, j, count):
    C[i, j] = count
    # 上
    if j > 0 and C[i, j - 1] == 0:
        search_empty(C, i, j - 1, count)
    # 左
    if i > 0 and C[i - 1, j] == 0:
        search_empty(C, i - 1, j, count)
    # 右
    if i < W - 1 and C[i + 1, j] == 0:
        search_empty(C, i + 1, j, count)
    # 下
    if j < H - 1 and C[i, j + 1] == 0:
        search_empty(C, i, j + 1, count)


count = 2
for i in range(H):
    for j in range(W):
        if C[i, j] == 0:
            search_empty(C, i, j, count)
            count += 1

D = np.zeros((count, count))

for i in range(H):
    for j in range(W):
        if C[i, j] != 1:
            for k in range(-2, 3):
                for l in range(-2, 3):
                    k = i + k
                    l = j + l
                    if k < 0 or k >= H:
                        continue
                    if l < 0 or l >= W:
                        continue
                    if C[k, l] != 1 and C[i, j] != C[k, l]:
                        D[C[i, j], C[k, l]] = 1
                        D[C[k, l], C[i, j]] = 1

start = C[ch-1, cw-1]
end = C[dh-1, dw-1]

count = 0

if start == end:
    print(0)

li = [[start, 0]]
while len(li):
    z, c = li.pop(0)
    if c == max(C.flatten()):
        print(-1)
        break
    for i in range(2, int(max(C.flatten()))+1):
        if i != z and D[z, i] != 0:
            li.append([i, c + 1])
    if c != 0 and end == z:
        print(c)
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    (h, w, m) = [int(e) for e in lines[0].split(" ")]
    hw = []
    for i in range(1, m + 1):
        hw.append([int(e) - 1 for e in lines[i].split(" ")])

    return (h, w, m, hw)

def solve(h, w, m, hw):

    d = dict()
    for e in hw:
        d[(e[0], e[1])] = 1

    current = 0

    d_total_i = dict()
    for i in range(h):

        total_i = 0
        for k in range(w):
            total_i = total_i + d.get((i, k), 0)

        d_total_i[i] = total_i

    d_total_j = dict()
    for j in range(w):
        
        total_j = 0
        for l in range(h):
            total_j = total_j + d.get((l, j), 0)

        d_total_j[j] = total_j



    for i in range(h):
        for j in range(w):

            total = d_total_i[i] + d_total_j[j]           

            if d.get((i, j)) == 1:
                total = total - 1

            if total > current:
                current = total

    return current



def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Runtime Error

Solution code:
c = lst.count('.')
ans = 0

dfs(sh, sw)

if visited[gh][gw]:
    print(ans)
ov = -1
nv = - 2
while ov != nv:
    ov = sum(visited[gh][gw], []).count(1)
    for h in range(H):
        for w in range (W):
            if visited[h][w] == 0 and lst[h][w] != '#':
                arr = np.array(visited)[max(0, h-2):min(H, h+3),max(0, w-2):min(W, w+3)].tolist()
                if sum(arr, []).count(1) >= 1:
                    ans += 1
                    dfs(h,w)
                    nv = sum(visited[gh][gw], []).count(1)
                    if flg:
                        break
                
if visited[gh][gw]:
    print(ans)
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 [h+x,w+y] in q:
                                    continue
                                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:
def ispossible(i,j):
    if i<0 or j<0 or i>=n or j>=m or a[i][j]=='#':
        return False
    return True
def func(i,j):
    if(v[i][j]==1):
        return
    for k1 in range(-1,2):
        for k2 in range(-1,2):
            if(abs(k1)==abs(k2)):
                continue
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j])
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
                    v[i+k1][j+k2]=1
    for k1 in range(-2,3):
        for k2 in range(-2,3):
            if(ispossible(i+k1,j+k2)):
                dp[i+k1][j+k2]=min(dp[i+k1][j+k2],dp[i][j]+1)
                if(v[i+k1][j+k2]==0):
                    func(i+k1,j+k2)
                    v[i+k1][j+k2]=1
n,m=[int(i) for i in input().split()]
x1,y1=[int(i)-1 for i in input().split()]
x2,y2=[int(i)-1 for i in input().split()]
dp=[[10**9 for i in range(m)]for j in range(n)]
a=[[i for i in input()]for j in range(n)]
v=[[0 for i in range(m)]for j in range(n)]
dp[x1][y1]=0
func(x1,y1)
if(dp[x2][y2]==10**9):
    print(-1)
else:
    print(dp[x2][y2])

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())
CH = CH - 1
CW = CW - 1
DH = DH - 1
DW = DW - 1
s = (CH,CW)
g = (DH,DW)

S = [0 for i in range(0,H)]
for i in range(0,H):
    a = input()
    S[i] = [a[i:i+1] for i in range(len(a))]
    
nohani = [(2,2),(2,3),(2,1),(3,2),(1,2)]
hani = []
for i in range(5):
    for j in range(5):
      if (i,j) not in nohani:   
         hani.append((i-2,j-2))

maze_adj_maho = {}
for x in range(H):
  for y in range(W):
    l = []
    for (dx,dy) in hani:
      if (0<=x+dx<W) and (0<=y+dy<H) and S[x+dx][y+dy]!='#':
        l.append((x+dx,y+dy))
    maze_adj_maho[(x,y)] = l

maze_adj = {}
for x in range(H):
  for y in range(W):
    l = []
    for (dx,dy) in [(1,0),(0,1),(-1,0),(0,-1)]: 
      if (0<=x+dx<W) and (0<=y+dy<H) and S[x+dx][y+dy]!='#':
        l.append((x+dx,y+dy))
    maze_adj[(x,y)] = l

def bfs(adj,adj2,v,S):
  prev = {} # 直前にどの頂点を訪れたか
  dist = {} # 距離
  for i in range(H):
      for j in range(W):
          dist[(i,j)] = 10000000
  queue = deque([(v,0,'start')]) # vを距離0の初期点として訪れることを予約
  while queue:
    v,d,p = queue.popleft() # キューの最初の要素を取り出す
    if v in prev: continue # vを訪問済みなら次の要素へ
    prev[v] = p # 訪問済みでなければpからvへ訪問したと記録
    dist[v] = min(d,dist[v]) # 距離はdであると記録
    for u in adj[v]:
       if u not in prev:
        if u in queue:
          queue.append((u,d,v)) # 後でuを訪問することを予約
    for u in adj2[v]:
      if u not in adj[v]:
       if u not in prev:
          if u not in queue:
            queue.append((u,d+1,v)) # 後でuを訪問することを予約
        
  for i in range(H):
      for j in range(W):
          if dist[(i,j)] == 10000000:
              dist[(i,j)] = -1
  return prev,dist

prev,dist = bfs(maze_adj,maze_adj_maho,s,S)
print (dist)
print (dist[g])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
amap = []
for _ in range(h):
  amap.append([ s for s in input()])
posh = ch - 1
posw = cw - 1
time = 0
ans = 10000
mva = [ (0,1), (1,0), (0,-1), (-1,0) ]
mvb = [ (-2,2), (-1,2), (0,2), (1,2), (2,2), 
        (-2, 1), (-1, 1), (1, 1), (2, 1), 
       (-2, 0), (2, 0),
       (-2, -1), (-1, -1), (1, -1), (2, -1), 
      (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2),
      ]
def possible(y, x):
  if x<0 or y>=h or y<0 or x>=w:
    return False
  if amap[y][x] == '#':
    return False
  if amap[y][x] == '.':
    return True

def dfs(posh, posw, time):
  global ans
  times = [ans]
  amap[posh][posw] = '#'
  if posh == (dh-1) and posw == (dw-1):
    if time < ans:
      ans = time
      return ans
  for y, x in mva:
    if possible(posh+y,posw+x):
      times.append(dfs(posh+y, posw+x, time))
  for y, x in mvb:
    if possible(posh+y,posw+x):
      time = time + 1
      times.append(dfs(posh+y, posw+x, time))
  return min(times)
ans = dfs(posh, posw, time)
if ans == 10000:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from collections import deque
import numpy as np
from itertools import permutations


class Lab:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.map = np.zeros(shape=(h, w), dtype=np.int8)
        self.max_c = 1
        self.tree = dict()

    def set_wall(self, ih, walls):
        self.map[ih] = walls

    def bfs(self, y, x, c):
        q = deque()
        p = y * 10000 + x
        q.append(p)
        visited = set()
        visited.add(p)

        while q:
            v = q.popleft()
            y, x = divmod(v, 10000)
            self.map[y][x] = c
            for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ny, nx = y+dy, x+dx
                if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                    continue
                if self.map[ny][nx] != 0:
                    continue
                p = ny * 10000 + nx
                if p in visited:
                    continue
                q.append(p)
                visited.add(p)

    def coloring(self):
        for y in range(self.h):
            for x in range(self.w):
                if self.map[y][x] == 0:
                    self.max_c += 1
                    self.bfs(y, x, self.max_c)

    def room(self):
        if self.max_c == 1:
            return

        for c in range(2, self.max_c+1):
            self.tree[c] = set()

        for y in range(self.h):
            for x in range(self.w):
                c = self.map[y][x]
                if c == 1:
                    continue
                for dy in range(-2, 3):
                    for dx in range(-2, 3):
                        ny, nx = y + dy, x + dx
                        if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                            continue
                        tc = self.map[ny][nx]
                        if tc not in (1, c):
                            self.tree[c].add(tc)


def solve():
    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

    lab = Lab(h, w)
    for i in range(h):
        walls = np.array(list(map(lambda x: int(x == "#"), input())))
        lab.set_wall(i, walls)

    lab.coloring()
    # print(lab.map)
    dc = lab.map[dh][dw]
    if dc == 1:
        return "-1"

    cc = lab.map[ch][cw]
    if dc == cc:
        return 0

    lab.room()
    # print(lab.tree)
    ct = lab.tree[cc]
    if dc in ct:
        return 1

    lab.tree.pop(cc)
    pre_set = ct
    min_dist = 10 ** 9
    for roots in permutations(lab.tree):
        # print(roots)
        dist = 0
        ok = False
        for nc in roots:
            if nc not in pre_set:
                break
            dist += 1
            if dc in pre_set:
                ok = True
                break
            pre_set = lab.tree[nc]
        if ok:
            min_dist = min(min_dist, dist)

    if min_dist == 10 ** 9:
        return "-1"

    return min_dist


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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)]

from collections import deque
todo = deque([])

def dfs(x,y):
    while len(todo) > 0:
        x,y = todo.pop()
        cS[x][y] = '#'
        for dx,dy in ([1,0],[-1,0],[0,1],[0,-1]):
            nx = x + dx
            ny = y + dy
            if nx >= 0 and nx < H and ny >= 0 and ny < W and cS[nx][ny] == '.':
                todo.append([nx,ny])
import copy
cS = copy.deepcopy(S)
fn = 0
for i in range(H):
    for j in range(W):
        if cS[i][j] == '.':
            todo.append([i,j])
            dfs(i,j)
            fn += 1

if fn == 1:
    print(0)
else:
    break

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 tmplis2:
        tmplis1+=[i]
        if(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
    baket=nbaket
if(lisc[dw][dh]==1000):
    print(-1)
else:
    print(lisc[dw][dh])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import copy
import sys

fieldMap = []
fieldMax = [4,4]
startPos = [1,4]
goalPos = [4,1]

fieldMax = list(map(int, input().split()))
startPos = list(map(int, input().split()))
goalPos = list(map(int, input().split()))

for i in range(fieldMax[0]):
    user4 = input()
    fieldMap.append(list(user4))

startPos[0] = startPos[0] -1
startPos[1] = startPos[1] -1
goalPos[0] = goalPos[0] -1
goalPos[1] = goalPos[1] -1

#fieldMap.append([".", "#", "#", "."])
#fieldMap.append(["#", "#", "#", "#"])
#fieldMap.append(["#", "#", "#", "#"])
#fieldMap.append([".", "#", "#", "."])

#print(fieldMap)
#print(goalPos)
fieldMap[goalPos[0]][goalPos[1]] = "g"

def move(x,y,field,warp):

    # goal判定
    if field[x][y] == "g":
        #print("GOAL!!!!",warpDo)
        result = warpDo
        print(result)
        #test = input()
        sys.exit(1)

    field[x][y] = "@"   # 踏破済み座標をポイント
    #print("nowPos:",x,y)
    #print(field)

    for d in range(4):
        moveX = x
        moveY = y
        if d == 0:  moveY = y - 1
        if d == 1:  moveX = x + 1
        if d == 2:  moveY = y + 1
        if d == 3:  moveX = x - 1
        if moveX >= 0 and moveX < fieldMax[0] and moveY >= 0 and moveY < fieldMax[1]:
            if field[moveX][moveY] == "." or field[moveX][moveY] == "g":
                #print("gone(",moveX,",",moveY,")")
                #test = input()

                # 再起
                move(moveX,moveY,copy.deepcopy(field),warp)

    # ワープ処理
    if warp > 0:
        for i in range(5):
            for j in range(5):
                moveX = x - 2+i
                moveY = y - 2+j
                if moveX >= 0 and moveX < fieldMax[0] and moveY >= 0 and moveY < fieldMax[1]:
                    if field[moveX][moveY] == "." or field[moveX][moveY] == "g":
                        #print("warp(",moveX,",",moveY,")")
                        move(moveX,moveY,copy.deepcopy(field),warp-1)

    #print("field=",x,y)
    return moveX





for k in range(4):
    warpDo = k
    move(startPos[0],startPos[1],copy.deepcopy(fieldMap),k)

#print( fieldMap)
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
s = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
visited[ch][cw] = 1
queue = deque([[ch, cw, 0]])
queue2 = deque([])


def bfs():
    global s, visited, queue, queue2
    while queue:
        tmp_h, tmp_w, res = queue.pop()
        for p, q in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = tmp_h+p, tmp_w+q
            if (new_h, new_w) == (dh, dw):
                return res
            if new_h < 0 or new_h >= h or \
               new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != '#' and \
                    visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                queue.appendleft([new_h, new_w, res])
            elif s[new_h][new_w] == '#':
                for p_ in [-2, -1, 0, 1, 2]:
                    for q_ in [-2, -1, 0, 1, 2]:
                        new_h, new_w = tmp_h+p_, tmp_w+q_
                        if new_h < 0 or new_h >= h or \
                                new_w < 0 or new_w >= w:
                            continue
                        elif s[new_h][new_w] != '#' and \
                                visited[new_h][new_w] == 0:
                            queue2.appendleft([new_h, new_w, res+1])
    while queue2:
        tmp_h, tmp_w, res = queue2.pop()
        if visited[tmp_h][tmp_w] == 0:
            queue.appendleft([tmp_h, tmp_w, res])
            break

    if (not queue) and (not queue2):
        return -1

    return bfs()


print(bfs())

Submission status: Runtime Error

Solution code:
def main():

    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(0)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs1a(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == '.':
                maze[nexty][nextx] = '!'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs2(cur_coor, r):
        for j1 in range(20):
            nextx = cur_coor[1] + warpx[j1]
            nexty = cur_coor[0] + warpy[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r + 1)
                return
            elif nextg == '.' or nextg == '-':
                maze[nexty][nextx] = '+'
                dfs2((nexty, nextx), r + 1)
            else:
                pass

    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
    dummy = ['#'] * (w + 4)
    maze = []
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    #dfs1a((dh, dw))
    rs = []
    dfs2((ch, cw) ,0)
    if rs:
        print(min(rs))
    else:
        print(-1)


if __name__ == '__main__':
    main()