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: Accepted

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_dxy(self, x: int, y: int) -> int:
        return self.width * x + y

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self._flatten_dxy(h + 2, w + 2)

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move_to_warp = {
            -w: (-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -w - 1),
            w: (w + 1, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2),
            -1: (-w - 2, -2, w - 2, w - 1, 2 * w - 2),
            1: (-w + 1, -2 * w + 2, -w + 2, 2, w + 2),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == self.goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                else:
                    for dx in warp:
                        nx = x + dx
                        if self.grid[nx] == self.wall:
                            continue
                        if dist[nx] > cur_dist + 1:
                            dist[nx] = cur_dist + 1
                            queue.append(nx)

        return dist[self.goal] if dist[self.goal] != unsearched else -1

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch,cw,dh,dw=ch-1,cw-1,dh-1,dw-1
S=[data() for i in range(h)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
dist=[[INF]*w for i in range(h)]
dist[ch][cw]=0

queue = [(0, (ch, cw))]
while queue:
    path_len, (u, v) = heappop(queue)
    if path_len == dist[u][v]:
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= u + i < h and 0 <= v + j < w and S[u + i][v + j] == '.':
                    if (i,j) in steps:
                        if path_len < dist[u+i][v+j]:
                            dist[u+i][v+j] = path_len
                            heappush(queue, (path_len, (u+i, v+j)))
                    else:
                        if 1 + path_len < dist[u + i][v + j]:
                            dist[u + i][v + j] = 1 + path_len
                            heappush(queue, (1 + path_len, (u + i, v + j)))


if dist[dh][dw]!=INF:
    out(dist[dh][dw])
else:
    out(-1)

Submission status: Accepted

Solution code:
#01BFS

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 in_area(x,y):
    return 0<=x<=H-1 and 0<=y<=W-1
    
def cango_step(x,y):
    cand0 =[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

def cango_warponly(x,y):
    cand0 =[(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),
            (x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2),
            (x+1,y-2),(x,y-2),(x-1,y-2),
            (x+1,y+2),(x,y+2),(x-1,y+2),
            (x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

q = deque([(-1,-1,CH-1,CW-1,0)]) 
been = [[False]*W for _ in range(H)]
INF=10**20
shortest =[[INF]*W for _ in range(H)]
shortest[CH-1][CW-1] = 0
    
reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.pop()
    #print(x_now,y_now,time)
    
#     if x_now==H-1 and y_now==W-1:
#         reach=True
#         break
        
    cand = cango_step(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time:
            q.append((x_now,y_now,x_new,y_new,time))
            shortest[x_new][y_new]=time
            
    cand = cango_warponly(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time+1:
            q.appendleft((x_now,y_now,x_new,y_new,time+1))
            shortest[x_new][y_new]=time+1
            
if shortest[DH-1][DW-1]==INF:
    print(-1)
else:
    print(shortest[DH-1][DW-1])

Submission status: Accepted

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=[input() for _ in range(h)]


cnt=[[-1]*w for _ in range(h)]
cnt[ch][cw]=0
from collections import deque

q=deque()
q2=deque()
q.append((ch,cw))
d=[(1,0),(-1,0),(0,1),(0,-1)]
d2=[(i-2,j-2) for i in range(5) for j in range(5)]
tmp=0
while q2 or q:
    while q:
        y,x=q.popleft()
        q2.append((y,x))
        for dx,dy in d:
            if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 and  s[y+dy][x+dx]=="." and cnt[y+dy][x+dx]<0:
                cnt[y+dy][x+dx]=cnt[y][x]
                q.append((y+dy,x+dx))
    y,x=q2.popleft()
    tmp+=1
    for dx,dy in d2:
        #print(y,x,dx,dy,s[y+dy][x+dx],cnt[y+dy][x+dx])
        if 0<=y+dy<=h-1 and 0<=x+dx<=w-1 and  s[y+dy][x+dx]=="." and cnt[y+dy][x+dx]<0:
            cnt[y+dy][x+dx]=cnt[y][x]+1
            q.append((y+dy,x+dx))

print(cnt[dh][dw])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    D = [[-1] * W for _ in [0] * H]  # -1がINFを意味する
    que = [(0, si, sj)]
    while que:
        c, i, j = heappop(que)
        if D[i][j] != -1:
            continue
        D[i][j] = c
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
                nc = c
            else:  # ワープして行ける
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from itertools import product, permutations, combinations
from collections import deque

# もし歩くだけなら簡単
# ワープをどう処理する？
# もし周囲5*5を候補にするなら24*10**6 んー間に合うか微妙


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())

S = read_map_as(H)
D = [[-1] * W for _ in [0] * H]  # -1がINFを意味する
que = deque([(0, si, sj)])
while que:
    c, i, j = que.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = c
    for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or S[ni][nj] == 1:
            continue
        if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
            que.appendleft((c, ni, nj))  # コストが低いので先に出したい
        else:  # ワープして行ける
            que.append((c + 1, ni, nj))  # コストが高いのであとに出したい

print(D[ti][tj])
# print(*D, sep='\n')

# unionfindで連結成分切り出してから、連結成分をまたぐときだけ+1するdfsかな?

Submission status: Accepted

Solution code:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1, b1
from heapq import heappop, heappush

#@njit(i8(b1[:,:], i8, i8, i8, i8), cache=True)
def solve(grid, ch, cw, dh, dw):
    h, w = grid.shape
    
    dist = np.full((h, w), INF, dtype=np.int64)
    dist[ch][cw] = 0

    que = [(0, ch, cw)]

    while que:
        cnt, y, x = heappop(que)

        if y == dh and x == dw:
            break

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue

                if abs(dx) == 2 or abs(dy) == 2 or (abs(dx) == 1 and abs(dy) == 1):
                    warp = 1
                else:
                    warp = 0

                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= w or ny < 0 or ny >= h or grid[ny][nx]:
                    continue
                
                if dist[ny][nx] > cnt + warp:
                    dist[ny][nx] = cnt + warp
                    heappush(que, (cnt + warp, ny, nx))

    if dist[dh][dw] == INF:
        return - 1
    else:
        return dist[dh][dw]


def Main():
    H, W = read_ints()
    ch, cw = read_ints(); ch -= 1; cw -= 1
    dh, dw = read_ints(); dh -= 1; dw -= 1

    grid = np.array([[g == '#' for g in read_str()] for _ in range(H)])
    
    print(solve(grid, ch, cw, dh, dw))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve','(b1[:,:], i8, i8, i8, i8,)')(solve)
    cc.compile()

if __name__ == '__main__':
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit()
    from my_module import solve
    Main()

Submission status: Accepted

Solution code:
# Date [ 2020-08-22 21:07:07 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit, u1, b1
from heapq import heappop, heappush

@njit(i8(b1[:,:], i8, i8, i8, i8), cache=True)
def solve(grid, ch, cw, dh, dw):
    h, w = grid.shape
    
    dist = np.full((h, w), INF, dtype=np.int64)
    dist[ch][cw] = 0

    que = [(0, ch, cw)]

    while que:
        cnt, y, x = heappop(que)

        if y == dh and x == dw:
            break

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue

                if abs(dx) == 2 or abs(dy) == 2 or (abs(dx) == 1 and abs(dy) == 1):
                    warp = 1
                else:
                    warp = 0

                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= w or ny < 0 or ny >= h or grid[ny][nx]:
                    continue
                
                if dist[ny][nx] > cnt + warp:
                    dist[ny][nx] = cnt + warp
                    heappush(que, (cnt + warp, ny, nx))

    if dist[dh][dw] == INF:
        return - 1
    else:
        return dist[dh][dw]


def Main():
    H, W = read_ints()
    ch, cw = read_ints(); ch -= 1; cw -= 1
    dh, dw = read_ints(); dh -= 1; dw -= 1

    grid = np.array([[g == '#' for g in read_str()] for _ in range(H)])
    
    print(solve(grid, ch, cw, dh, dw))

def cc_export(config):
    from numba.pycc import CC
    cc = CC('my_module')
    for func, signature in config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()

if __name__ == '__main__':
    Main()

Submission status: Accepted

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())
s=[list(input()) for _ in range(h)]

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]
mx=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.appendleft((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))

print(-1 if d[dh][dw]==float("inf") else d[dh][dw])

Submission status: Accepted

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self.width * (h + 2) + w + 2

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            if x == self.goal:
                break
            cur_dist = dist[x]

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

            for dx in warp:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal] if dist[self.goal] != unsearched else -1

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
CY, CX = map(lambda x: int(x)-1, input().split())
DY, DX = map(lambda x: int(x)-1, input().split())

gridgraph = [input() for _ in range(H)]
q = deque()
q.append([CY, CX])
# 更新されるなら追加
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
INF = float("inf")
distant = [[INF]*W for _ in range(H)]
distant[CY][CX] = 0
visited = set()
while len(q):
    cy, cx = q.popleft()
    if (cy, cx) in visited:
        continue
    visited.add((cy, cx))
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            distant[ny][nx] = distant[cy][cx]
            q.appendleft([ny, nx])
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                distant[target_y][target_x] = distant[cy][cx]+1
                q.append([target_y, target_x])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Accepted

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())
s=[list(input()) for _ in range(h)]

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]
mx=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.pop()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.appendleft((new_y, new_x))

print(-1 if d[dh][dw]==float("inf") else d[dh][dw])

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) + 1, input().split()) 
gy, gx = map(lambda x:int(x) + 1, input().split()) 
grid = [['#'] * (w + 4) for _ in range(2)]
for _ in range(h):
    grid.append(['#', '#'] + list(input()) + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

stack = [(sy, sx)]

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

visited = set()
ans = 0
while stack:
    edge = set()
    while stack:
        y, x = stack.pop()
        visited.add((y, x))
        if gy == y and gx == x:
            print(ans)
            quit()
        for my, mx in move:
            if (y+my, x+mx) in visited:
                continue
            if grid[y+my][x+mx] == '.':
                stack.append((y+my, x+mx))
            else:
                edge.add((y, x))
    ans += 1
    next_points = set()
    for y, x in edge:
        for dy in range(-2, 3):
            yy = y + dy
            for dx in range(-2, 3):
                xx = x + dx
                if grid[yy][xx] == '.' and not (yy, xx) in visited and not (yy, xx) in next_points:
                    next_points.add((yy, xx))
    stack = list(next_points)
print(-1)

Submission status: Accepted

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,0)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]!=INF else -1)

Submission status: Accepted

Solution code:
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z:
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i; ny = y+j
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z+1:
                    nq.append([nx,ny,z+1])
                    mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
CY, CX = map(lambda x: int(x)-1, input().split())
DY, DX = map(lambda x: int(x)-1, input().split())

gridgraph = [input() for _ in range(H)]
q = deque()
q.append([CY, CX])
# 更新されるなら追加
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
INF = float("inf")
distant = [[INF]*W for _ in range(H)]
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            distant[ny][nx] = distant[cy][cx]
            q.appendleft([ny, nx])
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                distant[target_y][target_x] = distant[cy][cx]+1
                q.append([target_y, target_x])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    mylist = []
    for i in range(H):
        temp = input().rstrip()
        temp = tuple([True if temp[i]=="." else False for i in range(W)])
        mylist.append(temp)
    mylist = tuple(mylist)

    
    dist = Init(H, W, float('inf'))
    #dist2 = Init(H, W, float('inf'))
    dq = deque()
    dq2 = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    
    while dq:
        while dq:
            x, y = dq.popleft()
            if x == gx and y == gy:
                print(dist[gx][gy])
                sys.exit()


            #コスト1の移動
            for x2, y2 in move2:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] and dist[x2][y2] > dist[x][y]+1:
                    dist[x2][y2] = dist[x][y]+1
                    dq2.append((x2,y2))

            #コスト0の移動
            for x2, y2 in move1:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] and dist[x2][y2] > dist[x][y]:
                    dist[x2][y2] = dist[x][y]
                    dq.append((x2,y2))


        dq = deque(set(dq2))
        dq2 = deque()
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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())
    base = ["#" *(w+4)]
    base.append("#" * (w+4))
    for n in range(h):
        base.append("##" + input() + "##")
    base.append("#" * (w+4))
    base.append("#" * (w+4))
    ans = [[-1] * (w+4) for _ in range(h+4)]
    for j in range(w+4):
        for i in range(h+4):
            if base[i][j] == "#":
                ans[i][j] = -2
    ch+=1; cw+=1
    dh+=1; dw+=1
    ans[ch][cw] = 0
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    move2 = [
        [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
        [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
        [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
        [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
        [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
        ]
    q = deque([[ch, cw]])
    one_time = deque([])
    while len(q) > 0:
        x, y = q.popleft()
        one_time.append([x, y])
        for i, j in move:
            v1, v2 = x+i, y+j
            if ans[v1][v2] == -1:
                ans[v1][v2] = ans[x][y]
                q.append([v1, v2])
        if len(q) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.popleft()
                for i, j in move2:
                    v1, v2 = x2+i, y2+j
                    if ans[v1][v2] == -1:
                        ans[v1][v2] = ans[x2][y2] + 1
                        q.append([v1, v2])
    print(ans[dh][dw])

if __name__ == "__main__":
    main()