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:
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
bool is_integer(double x)
{
    return floor(x) == ceil(x);
}
class Move
{
public:
    int w;
    int h;
    int warp;
};
int main()
{
    int h, w;
    int ch, cw, dh, dw;
    char s[1001][1001] = {'#'};
    cin >> h >> w >> ch >> cw >> dh >> dw;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cin >> s[i][j];
        }
    }
    queue<Move> walk_que;
    queue<Move> warp_que;
    Move *p_start = new Move();
    p_start->h = ch;
    p_start->w = cw;
    p_start->warp = 0;
    warp_que.push(*p_start);
    // スタート地点から行けるマス
    while (!warp_que.empty())
    {
        Move warp = warp_que.front();
        warp_que.pop();
        walk_que.push(warp);
        if (s[warp.h][warp.w] == '*')
        {
            continue;
        }
        while (!walk_que.empty())
        {
            Move walk = walk_que.front();
            walk_que.pop();
            int aw = walk.w;
            int ah = walk.h;
            int awarp = walk.warp;
            if (s[ah][aw] == '*')
            {
                continue;
            }
            if (ah == dh && aw == dw)
            {
                cout << awarp << endl;
                return 0;
            }
            s[ah][aw] = '*';
            // cout << aw << ' ' << ah << ' ' << awarp << endl;
            for (int i = -2; i <= 2; i++)
            {
                for (int j = -2; j <= 2; j++)
                {
                    if (i == 0 && j == 0)
                        continue;
                    if (ah + i < 0 || ah + i >= h)
                    {
                        continue;
                    }
                    if (aw + j < 0 || aw + j >= w)
                    {
                        continue;
                    }
                    if (i * i + j * j == 1)
                    {
                        if (s[ah + i][aw + j] == '.')
                        {
                            Move *tmp = new Move();
                            tmp->h = ah + i;
                            tmp->w = aw + j;
                            tmp->warp = awarp;
                            walk_que.push(*tmp);
                        }
                    }
                    else
                    {
                        if (s[ah + i][aw + j] == '.')
                        {
                            Move *tmp = new Move();
                            tmp->h = ah + i;
                            tmp->w = aw + j;
                            tmp->warp = awarp + 1;
                            warp_que.push(*tmp);
                        }
                    }
                }
            }
        }
    }
    cout << -1 << endl;
}

Submission status: Runtime Error

Solution code:

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter

rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=1<<20
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
#    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
#                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,0


show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h


nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
d=[-1]*n
g=[[]for i in range(n)]
for i in range(n):
    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1!=m[i]:
            g[i]+=(nx,1),
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1!=m[i]:
            g[i]+=(nx,0),

d,_=dijkstra(g,sh*w+sw)
ans=d[gh*w+gw]
if ans==inf:
    ans=-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]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([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
warp = [[INF]*w for _ in range(h)]
ans=bfs(maze, warp, 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


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij=='#':
                dist[j][i] = -1
    que = deque([(x, y)])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for cnt, l in enumerate((near_a, near_b)):
            for i, j in l:
                if (0 <= i < w and 0 <= j < h and
                        dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                    dist[j][i] = dist[y][x] + cnt
                    if cnt == 0:
                        que.appendleft((i, j))
                    elif cnt == 1:
                        que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs(Cw - 1, Ch - 1)[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([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)]

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

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
C=list(map(int,input().split()))
D=list(map(int,input().split()))
M=[]
for i in range(H):
    L=[]
    for k in input():
        L.append(k)
    M.append(L)
def X(x,y):
    if x==D[0] and y==D[1]:
        return c
    elif M[x-1][y]==".":
        c+=1
        return X(x-1,y)
    elif M[x+1][y]==".":
        c+=1
        return X(x+1,y)
    elif M[x][y-1]==".":
        c+=1
        return X(x,y-1)
    elif M[x][y+1]==".":
        c+=1
        return X(x,y+1)
    if c>10*3:
        for i in range(-2,3):
            for j in range(-2,3):
                if 0<=x+i<=H-1 and 0<=y+j<=W-1 and M[x+i][y+j]==".":
                    return X(x+i,y+j)
print(X(C[0],C[1]))

Submission status: Runtime Error

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    # 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
    walled_maze = ['##{}##'.format(row) for row in maze]
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))

    INF = 10 ** 12
    path = [[INF] * (H + 4) for _ in range(W + 4)]
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    yet = deque()
    yet.append((Ch + 2, Cw + 2, 0))    # 囲った壁の分だけプラス
    path[Ch + 2][Cw + 2] = 0
    done = deque()

    while yet:
        y, x, s = yet.popleft()
        done.append((y, x, s))
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                yet.append((ny, nx, s))
        if len(yet) == 0:
            while done:
                y, x, s = done.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                        path[ny][nx] = s + 1
                        yet.append((ny, nx, s + 1))
    ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)

Submission status: Runtime Error

Solution code:
from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    # 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
    walled_maze = ['##{}##'.format(row) for row in maze]
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))

    INF = 1 << 30
    path = [[INF] * (H + 4) for _ in range(W + 4)]
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    yet = deque()
    yet.append((Ch + 2, Cw + 2, 0))    # 囲った壁の分だけプラス
    path[Ch + 2][Cw + 2] = 0
    done = deque()

    while yet:
        y, x, s = yet.popleft()
        done.append((y, x, s))
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                yet.append((ny, nx, s))
        if len(yet) == 0:
            while done:
                y, x, s = done.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                        path[ny][nx] = s + 1
                        yet.append((ny, nx, s + 1))
    ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))

    INF = 10**15
    d = [[INF for _ in range(W)] for _ in range(H)]    

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

    stack = deque()
    stack.append((ch, cw, 0))
    
    while stack:
        x, y, c = stack.popleft()
        
        if(d[x][y] == INF):
            d[x][y] = c
        
        if(x == dh-1 and y == dw-1):
            break
    
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
        
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            if(grid[nx][ny] == "#"):
                continue
            if(d[nx][ny] == INF):
                stack.appendleft((nx, ny, d[x][y]))
        
        for i in range(-2, 3):
            for j in range(-2, 3):
                if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                    continue
                if(grid[x+i][y+j] == "#"):
                    continue
                if(d[x][y] + 1 >= d[x+i][y+j]):
                    continue
                if(d[x+i][y+j] == INF):
                    stack.append((x+i, y+j, d[x][y]+1))
        
    
    print(d[dh-1][dw-1])
        
main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))

    d = [[10**15 for _ in range(W)] for _ in range(H)]    

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

    stack = deque()
    stack.append((ch, cw, 0))
    
    while stack:
        x, y, c = stack.popleft()
        
        if(d[x][y] == INF):
            d[x][y] = c
        
        if(x == dh-1 and y == dw-1):
            break
    
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
        
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            if(grid[nx][ny] == "#"):
                continue
            if(d[nx][ny] == INF):
                stack.appendleft((nx, ny, d[x][y]))
        
        for i in range(-2, 3):
            for j in range(-2, 3):
                if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                    continue
                if(grid[x+i][y+j] == "#"):
                    continue
                if(d[x][y] + 1 >= d[x+i][y+j]):
                    continue
                if(d[x+i][y+j] == INF):
                    stack.append((x+i, y+j, d[x][y]+1))
        
    
    print(d[dh-1][dw-1])
        
main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
from numba import njit

read = sys.stdin.read
readline = sys.stdin.readline

@njit
def solve():
  H,W = map(int,input().split())
  C_h,C_w = map(lambda x:int(x)-1,input().split())
  D_h,D_w = map(lambda x:int(x)-1,input().split())
  S = [readline() for _ in range(H)]

  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

  while len(deq):
    h,w = deq.popleft()
    if seen[h][w]:
      continue
      seen[h][w] = True
    for dh,dw in move_a:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
        dist[nh][nw] = dist[h][w]
        deq.appendleft((nh,nw))
    for dh,dw in move_b:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
        dist[nh][nw] = dist[h][w]+1
        deq.append((nh,nw))

  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

solve()

Submission status: Runtime Error

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

import numpy as np
from numba import njit

from sys import stdin
from collections import deque

@njit(cache=True)
def mytest():

  q = deque()

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

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


  INF = 10 ** 18
  org_list = deque()
  cost_list = [[INF]*w for i in range(h)]

  for i in range(h):
    # 文字列の入力
    s = stdin.readline()
    org_list.append(s)





  cost_list[ch][cw] = 0

  cost = 0
  ph = ch
  pw = cw

  q.append([ph, pw])

  # 上右下左
  ido_h = [-1, 0, 1, 0]
  ido_w = [0, 1, 0, -1]

  magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
  while q:

    ph, pw = q.popleft()
    cost = cost_list[ph][pw]

    for i in range(4):
      nh = ph + ido_h[i]
      nw = pw + ido_w[i]

      if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
        continue
      val = org_list[nh][nw]
      val_cost = cost_list[nh][nw]

      if val == "#" or val_cost <= cost:
        continue

      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])


    # ワープ
    for ih, iw in magic:
      nh = ph + ih
      nw = pw + iw
      if nh < 0 or h -1 < nh:
        continue
      if nw < 0 or w -1 < nw:
        continue
      if cost_list[nh][nw] <= cost:
        continue

      if org_list[nh][nw] == ".":
        cost_list[nh][nw] = cost + 1
        q.append([nh, nw])

  result = cost_list[dh][dw]
  if result == INF:
    result = -1

  # # 最後デバッグ
  # for li in org_list:
  #   print(li)
  # for li in cost_list:
  #   print(li)


  print(result)

mytest()

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if (nh<0 or nw<0 or nh>=H or nw>=W) and S[nh][nW]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if (nh<0 or nw<0 or nh>=H or nw>=W) and S[nh][nw] == '#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**5)

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

S = [input() for _ in range(H)]
room = [[-1]*W for _ in range(H)]

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

cur = 0

def dfs(y, x):
    room[y][x] = cur
    for i, j in zip(dx,dy):
        nx = x+i
        ny = y+j
        if nx<0 or W<=nx or ny<0 or H<=ny:
            continue
        if room[ny][nx] != -1 or S[ny][nx] == '#':
            continue
        dfs(ny,nx)

# 前処理
for x in range(W):
    for y in range(H):
        if S[y][x] == '#' or room[y][x] != -1:
            continue
        cur+=1
        dfs(y,x)

edge = defaultdict(list)

# 5*5範囲を探索
for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            continue
        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue
                st = room[y][x]
                ed = room[ny][nx]
                if S[ny][nx]=='#' or st == ed:
                    continue
                edge[st].append(ed)
                edge[ed].append(st)

st = room[ch][cw]
ed = room[dh][dw]

q = deque()
q.append(st)

ans = [-1] * 10**5
cur = 0
ans[st] = 0
while len(q) != 0:
    t = q.pop()
    if t == ed:
        break
    cur += 1
    for t in edge[t]:
        q.append(t)
        ans[t] = cur

print(ans[ed])

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q_walk = deque()
    q_warp = deque()
    q_walk.append((x, y))
    while q_walk > 0:
        x, y = q_walk.popleft() 
        q_warp.append((x, y))
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q_walk.append((nx, ny))
        if len(q_wark) == 0:
            while len(q_warp) > 0:
                x2, y2 = q_warp.popleft()
                for dxx in range(-2, 3):
                    for dyy in range(-2, 3):
                        nxx = x2 + dxx
                        nyy = y2 + dyy 
                        if not 0 <= nxx < h or not 0 <= nyy < w:
                            continue
                        if maze[nxx][nyy] == "#":
                            continue
                        if dist[nxx][nyy] <= d+1:
                            continue
                        dist[nxx][nyy] = d+1
                        q_warp.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])

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()
  maze[y-1][x-1] = '#'
  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 collections
h, w, si, sj, ti, tj, *s = open(0).read().split()
INF = 10**9
dist = [[INF] * w for _ in range(h)]
q = collections.deque([[si, sj]])
dist[si][sj] = 0
while q:
    i, j = q.popleft()
    d = dist[i][j]
    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj
        if not (0 <= ni < h and 0 <= nj < j):
            continue
        if s[ni][nj] == '#':
            continue
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni, nj = i + di, j + dj
            if not (0 <= ni < h and 0 <= nj < j):
                continue
            if s[ni][nj] == '#':
                continue
            if dist[ni][nj] < d + 1:
                continue
            dist[ni][nj] = d + 1
            q.append([ni, nj])
ans = dist[ti][tj]
if ans == INF or ans == 0:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # 移動先が通路かつ現状必要ワープ回数が多い
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([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)]

visited = [[-1]*w for _ in range(h)]
warp = [[10000]*w for _ in range(h)]
ans=bfs(maze, visited, sy-1, sx-1, gy-1, gx-1)
if ans==10000:
    ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)