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())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv = [[-1,0],[1,0],[0,-1],[0,1]]
warplist = []
for h in range(-2,2,1):
  for w in range(-2,2,1):
    if h!=0 and w!=0:
      warplist.append([h,w])
maze = []
goned = [[None]*(W) for j in range(H)]
for i in range(H):
  maze.append(input())

def wfs(h,w):
  goned[h][w] = cnt
  for vh,vw in mv:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if goned[tgh][tgw] is None and maze[tgh][tgw] != "#":
        wfs(tgh,tgw)
        wps.append([tgh,tgw])

def warp(h,w):
  for vh,vw in warplist:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if goned[tgh][tgw] is None and maze[tgh][tgw] != "#":
        tgs.append([tgh,tgw])
wps=[]
tgs = [[sh-1,sw-1]]
cnt = 0
while len(tgs)>0:
  wps=[]
  for tg in tgs:
    wfs(tg[0],tg[1])
  tgs = []
  for wp in wps:
    warp(wp[0],wp[1])
  cnt+=1
print(-1 if goned[eh][ew] is None else goned[eh][ew])

Submission status: Runtime Error

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
y=0

for i in range(h):
  a.append(list(input()))

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)>0 or len(f)>0 or y==0:
  while len(c)>0 or y==0:
    ch,cw=c[0]
    if ch==dh-1 and cw==dw-1:
        y=1
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  for i in f:
    if i not in d:
      c.append(i)
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Runtime Error

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)

for i in range(h):
  a.append(list(input()))

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e and not in d:
      f.append(e)

while len(c)>0 or len(f)>0:
  while len(c)>0:
    ch,cw=c[0]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  c=f
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Runtime Error

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    S = ["##"+input()+"##" for _ in range(H)]
    for i in range(2):
        S.insert(0, "#"*(W+4))
        S.append("#"*(W+4))

    inf = int(1e9)
    cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
    cost0 = deque()
    ans = -1

    cost0.append((CH+1, CW+1, 0))
    cost[CH+1][CW+1] = 0

    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

    cost1 = deque()

    while cost0:
        h, w, c = cost0.popleft()
        cost1.append((h, w, c))

        for i, j in move:
            dh = h+i
            dw = w+j
            if S[dh][dw] == "." and c < cost[dh][dw]:
                cost[dh][dw] = c
                cost0.appendleft((dh, dw, cost[dh][dw]))

        if len(cost0) == 0:
            while cost1:
                h, w, c = cost1.popleft()
                for i, j in warp:
                    dh = h+i
                    dw = h+j
                    if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                        cost[dh][dw] = c+1
                        cost0.append((dh, dw, cost[dh][dw]))

        if cost[DH+1][DW+1] != inf:
            ans = cost[DH+1][DW+1]

    print(ans)


if __name__ == "__main__":
    solve()

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 = ["##"+input()+"##" for _ in range(H)]
for i in range(2):
    S.insert(0, "#"*(W+4))
    S.append("#"*(W+4))

inf = int(1e9)
cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
cost0 = deque()
ans = -1

cost0.append((CH+1, CW+1, 0))
cost[CH+1][CW+1] = 0

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

cost1 = deque()

while cost0:
    h, w, c = cost0.popleft()
    cost1.append((h, w, c))

    for i, j in move:
        dh = h+i
        dw = w+j
        if S[dh][dw] == "." and c < cost[dh][dw]:
            cost[dh][dw] = c
            cost0.appendleft((dh, dw, cost[dh][dw]))

    if len(cost0) == 0:
        while cost1:
            h, w, c = cost1.popleft()
            for i, j in warp:
                dh = h+i
                dw = h+j
                if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                    cost[dh][dw] = c+1
                    cost0.append((dh, dw, cost[dh][dw]))

    if cost[DH+1][DW+1] != inf:
        ans = cost[DH+1][DW+1]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = ["##"+input()+"##" for _ in range(H)]
for i in range(2):
    S.insert(0, "#"*(W+4))
    S.append("#"*(W+4))

inf = int(1e9)
cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
cost0 = deque()
ans = -1

cost0.append((C[0]+1, C[1]+1, 0))
cost[C[0]+1][C[1]+1] = 0

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

cost1 = deque()

while cost0:
    h, w, c = cost0.popleft()
    cost1.append((h, w, c))

    for i, j in move:
        dh = h+i
        dw = w+j
        if S[dh][dw] == "." and c < cost[dh][dw]:
            cost[dh][dw] = c
            cost0.appendleft((dh, dw, cost[dh][dw]))

    if len(cost0) == 0:
        while cost1:
            h, w, c = cost1.popleft()
            for i, j in warp:
                dh = h+i
                dw = h+j
                if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                    cost[dh][dw] = c+1
                    cost0.append((dh, dw, cost[dh][dw]))

    if cost[D[0]+1][D[1]+1] != inf:
        ans = cost[D[0]+1][D[1]+1]

print(ans)

Submission status: Runtime Error

Solution code:
from queue import Queue
from collections import deque

H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = ["##"+input()+"##" for _ in range(H)]
for i in range(2):
    S.insert(0, "#"*(W+4))
    S.append("#"*(W+4))

inf = int(1e9)
cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
cost0 = deque()
ans = -1

cost0.append((C[0]+1, C[1]+1, 0))
cost[C[0]+1][C[1]+1] = 0

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

cost1 = deque()

while cost0:
    h, w, c = cost0.popleft()
    cost1.append((h, w, c))

    for i, j in move:
        dh = h+i
        dw = w+j
        if S[dh][dw] == "." and c < cost[dh][dw]:
            cost[dh][dw] = c
            cost0.appendleft((dh, dw, cost[dh][dw]))

    while cost1:
        h, w, c = cost1.popleft()
        for i, j in warp:
            dh = h+i
            dw = h+j
            if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                cost[dh][dw] = c+1
                cost0.append((dh, dw, cost[dh][dw]))

    if cost[D[0]+1][D[1]+1] != inf:
        ans = cost[D[0]+1][D[1]+1]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[x][y]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)+1, input().split()))
d = tuple(map(lambda x: int(x)+1, input().split()))
s = ['#'*(w+4)] * 2
for _ in range(h):
    s.append(f'##{input()}##')
s.extend(['#'*(h+4)] * 2)

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * (w+4) for _ in range(h+4)]
cost[c[0]][c[1]] = 0
yet = deque([(c[0], c[1], 0)])
done = deque()

while yet:
    y, x, m = yet.popleft()
    done.append((y, x, m))
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        yet.append((hh, ww, m))
    # Move B
    if not yet:
        while done:
            y, x, m = done.popleft()
            for dx, dy in move_b_area:
                hh, ww = y + dy, x + dx
                if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                    continue
                cost[hh][ww] = m + 1
                yet.append((hh, ww, m + 1))

print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
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
S = []
for i in range(H):
    S.append(list(input()))

def visit(S, h, w, d, H, W):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S) and 0 <= y < len(S[x]):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                    continue
                elif S[x][y] > d:
                    stack.append((x, y))
    for x, y in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                visit(S, h+dh, w+dw, d+1, H, W)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0, H, W)
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))

"""
import sys

if sys.argv[0] != "/.Main.py":
    import random

    for i in range(100):
        H = random.randint(2, 100)
        W = random.randint(2, 100)
        S = []
        for h in range(H):
            S.append([random.choice(".#") for _ in range(W)])

        Ch, Cw = random.randrange(0, H), random.randrange(0, W)
        Dh, Dw = random.randrange(0, H), random.randrange(0, W)
        S[Ch][Cw] = '.'
        S[Dh][Dw] = '.'
        print(H, W, (Ch, Cw), (Dh, Dw), solve(H, W, Ch, Cw, Dh, Dw, S))
"""

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
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
S = []
for i in range(H):
    S.append(list(input()))

def visit(S, h, w, d, H, W):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S) and 0 <= y < len(S[x]):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                    continue
                elif S[x][y] > d:
                    stack.append((x, y))
    for x, y in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                visit(S, h+dh, w+dw, d+1, H, W)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0, H, W)
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))

import sys

if sys.argv[0] != "/.Main.py":
    import random

    for i in range(100):
        H = random.randint(2, 100)
        W = random.randint(2, 100)
        S = []
        for h in range(H):
            S.append([random.choice(".#") for _ in range(W)])

        Ch, Cw = random.randrange(0, H), random.randrange(0, W)
        Dh, Dw = random.randrange(0, H), random.randrange(0, W)
        S[Ch][Cw] = '.'
        S[Dh][Dw] = '.'
        print(H, W, (Ch, Cw), (Dh, Dw), solve(H, W, Ch, Cw, Dh, Dw, S))

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 -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = []
for i in range(H):
    S.append(list(input()))

def visit(S, h, w, d):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S[h]) and 0 <= y < len(S):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                elif S[x][y] > d:
                    stack.append((x, y))
    hops = []
    for x, y in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                #print(d, hop, h+dh, w+dw)
                visit(S, h+dh, w+dw, d+1)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0)
    for h in range(H):
        #print("".join(map(str, S[h])))
        pass
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 1e3 + 10;
queue<pair<int,int>> q, q2;
int dist[N][N], h, w, sh, sw, eh, ew;
vector<pair<int,int>> ADJ = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<string> a;

void dfs(int r, int c) {
    q2.emplace(r, c);
    for (auto neigh : ADJ) {
        int nr = r + neigh.first, nc = c + neigh.second;
        if (nr < 0 || nr >= h || nc < 0 || nc >= w || a[nr][nc] == '#') continue;
        if (dist[r][c] < dist[nr][nc]) {
            dist[nr][nc] = dist[r][c];
            dfs(nr, nc);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> h >> w >> sh >> sw >> eh >> ew;
    sh--, sw--, eh--, ew--;
    a.resize(h);
    for (int i = 0; i < h; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            dist[i][j] = INF;
        }
    }
    q.emplace(sh, sw);
    dist[sh][sw] = 0;
    while (1) {
        bool ok = false;
        while (!q.empty()) {
            auto pos = q.front();
            q.pop();
            int r = pos.first, c = pos.second;
            if (r == eh && c == ew) {
                ok = true;
                break;
            }
            dfs(r, c);
        }
        if (ok) break;
        
        while (!q2.empty()) {
            auto pos = q2.front();
            q2.pop();
            int r = pos.first, c = pos.second;
            if (r == eh && c == ew) {
                ok = true;
                break;
            }
            
            for (int nr = max(0, r-2); nr <= min(h-1, r+2); nr++) {
                for (int nc = max(0, c-2); nc <= min(w-1, c+2); nc++) {
                    if (nr == r && nc == c) continue;
                    if (nr < 0 || nr >= h || nc < 0 || nc >= w || a[nr][nc] == '#') continue;
                    if (dist[r][c] + 1 < dist[nr][nc]) {
                        dist[nr][nc] = dist[r][c] + 1;
                        q.emplace(nr, nc);
                    }
                }
            }
        }
        if (ok) break;
        if (q.empty()) break;
    }
    
    if (dist[eh][ew] < INF) {
        cout << dist[eh][ew] << '\n';
    }
    else {
        cout << -1 << '\n';
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]]) < float('inf') else -1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

R = lambda: map(int, input().split())

H, W = R()
f = lambda x, y: (x - 2) * H + y - 2
s, t = (f(*(x + 1 for x in R())) for _ in (0, 0))
a =  ['#' * (W + 4)] * 4
a[2: 2] = ['##' + input() + '##' for _ in range(H)]
g = [[] for _ in range(H * W)]
for i in range(2, H + 2):
  for j in range(2, W + 2):
    if a[i][j] == '.':
      x = f(i, j)
      for k in range(i - 2, i + 3):
        for l in range(j - 2, j + 3):
          y = f(k, l)
          if x != y and a[k][l] == '.':
            w = abs(k - i) + abs(l - j) > 1
            g[x].append((y, w))

inf = 9**9            
dist = H * W * [inf]
dist[s] = 0
hp = []
heappush(hp, (0, s))
while hp:
  _, u = heappop(hp)
  for v, w in g[u]:
    if dist[v] > dist[u] + w:
      dist[v] = dist[u] + w
      heappush(hp, (dist[v], v))
print((-1, dist[t])[dist[t] < inf])

Submission status: Runtime Error

Solution code:
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for j, k in walk:
            ny, nx = y+j, x+k
            if maze[ny][nx] == "." and cost[ny][nx]>cost[x][y]:
                cost[ny][nx]=cost[x][y]
                queue.appendleft([ny,nx])
            
        # 移動B
        for ii, jj in warp:
            ny, nx = y+ii, x+jj
            if cost[y+ii][x+jj] > cost[y][x]+1 and maze[y+ii][x+jj]==".":
                cost[y+ii][x+jj]=cost[y][x]+1
                queue.append([y+ii,x+jj])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]
ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from collections import deque
import sys

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W = map(int, input().split())
start_i, start_j = map(lambda x: int(x) - 1, input().split())
goal_i, goal_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


warp_times = [[INF for j in range(W)] for i in range(W)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W = map(int, input().split())

start_i, start_j = map(int, input().split())
start_i -= 1
start_j -= 1

goal_i, goal_j = map(int, input().split())
goal_i -= 1
goal_j -= 1

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(field)

# bfs でワープなしで到達できるマスを探索
# 次に bfs でワープ
# i - 1 回目のワープで到達できる各マスから 5 x 5 の領域を探索したときに見つかる未到達のマスが i 回目のワープで到達できるマスになる


def adj(i, j):
    top, bottom = [i + 1, j], [i - 1, j]
    left, right = [i, j - 1], [i, j + 1]

    adj_list = []
    for i_adj, j_adj in top, bottom, left, right:
        if 0 <= i_adj <= H - 1 and 0 <= j_adj <= W - 1:
            if field[i_adj][j_adj] == '.':
                adj_list.append([i_adj, j_adj])

    return adj_list


def warp_adj(i, j):
    diff = [[i, j] for j in range(W) for i in range(H)]
    adj_set = set()

    for i_diff, j_diff in diff:
        i_adj = i + i_diff
        j_adj = j + j_diff
        if 0 <= i_adj <= H - 1 and 0 <= j_adj <= W - 1:
            if field[i_adj][j_adj] == '.':
                adj_set.add((i_adj, j_adj))

    return list(adj_set)


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for i_adj, j_adj in adj(i, j):
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for i_adj, j_adj in warp_adj(i, j):
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単にappendする
                que.append((i_adj, j_adj, times + 1))


warp_times = [[INF for j in range(W)] for i in range(W)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)