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:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)


warp = [[dy, dx] for dy in range(-2, 3) for dx in range(-2, 3) if abs(dy) + abs(dx) > 1]

def main():
    H, W = LI()
    CH, CW = LI1()
    DH, DW = LI1()
    S = SR(H)
    dist = make_list(H, W, default=-1)

    q = deque()
    dist[CH][CW] = 0
    q.append((0, CH, CW))

    while q:
        d, y, x = q.popleft()

        for dy, dx in dire:
            newx, newy = x + dx, y + dy
            if 0 <= newx < W and 0 <= newy < H and S[newy][newx] == ".":
                if dist[newy][newx] == -1 or dist[newy][newx] > d:
                    dist[newy][newx] = d
                    q.appendleft((d, newy, newx))

        for dy, dx in warp:
            newx, newy = x + dx, y + dy
            if 0 <= newx < W and 0 <= newy < H and S[newy][newx] == ".":
                if dist[newy][newx] == -1 or dist[newy][newx] > d + 1:
                    dist[newy][newx] = d + 1
                    q.append((d + 1, newy, newx))

    print(dist[DH][DW])







if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main(input, print):
    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, 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)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [input() for _ in range(H)]
    path = [[-1 for _ in range(W)] for _ in range(H)]

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.popleft()
        cnt = path[y][x]

        for k in range(len(move)):
            i, j = move[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for k in range(len(move2)):
            i, j = move2[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.append((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
import heapq

def solve():
    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    ty, tx = map(lambda x: int(x) - 1, input().split())
    graph = [input() for i in range(H)]
    INF = 10 ** 9
    dist = [INF] * (H * W)
    que = []

    def push(y, x, d):
        v = y * W + x
        if dist[v] <= d:
            return
        dist[v] = d
        heapq.heappush(que, (d, v))

    push(sy, sx, 0)

    while que:
        d, v = heapq.heappop(que)
        y, x = divmod(v, W)
        if dist[v] < d:
            continue
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny, nx = y + dy, x + dx
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue
                if graph[ny][nx] == '#':
                    continue
                push(ny, nx, d + (abs(dy) + abs(dx) > 1))

    t = ty * W + tx
    if dist[t] == INF:
        return -1
    else:
        return dist[t]

print(solve())

Submission status: Accepted

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

s = [list(input()) for _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.pop()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.append([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.appendleft([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque


def is_inside(x, y, W, H, G):
    return (x <= H-1 and y <= W-1 and
            x >= 0 and y >= 0 and
            G[x][y] != "#")


def main():
    H, W = map(int, input().split())
    Cx, Cy = map(int, input().split())
    Dx, Dy = map(int, input().split())

    G = [list(input()) for _ in range(H)]
    INF = int(1e9)
    q = deque()
    q.append((Cx-1, Cy-1, -INF, Cx-1, Cy-1))
    warps = [[INF] * W for _ in range(H)]
    while q:
        x, y, warp, prev_x, prev_y = q.popleft()

        if warps[x][y] != INF:
            continue

        num_warps = warps[prev_x][prev_y] + warp
        warps[x][y] = num_warps

        for step_x in range(-2, 3):
            for step_y in range(-2, 3):
                x_, y_ = x+step_x, y+step_y
                if is_inside(x_, y_, W, H, G) and warps[x_][y_] == INF:
                    if ((max(abs(step_x), abs(step_y)) == 1) and
                            (min(abs(step_x), abs(step_y)) == 0)):

                        q.appendleft((x_, y_, 0, x, y))
                    else:
                        q.append((x_, y_, 1, x, y))

    ans = warps[Dx-1][Dy-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input here
_INPUT = """\
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""

def main():
    H, W = map(int, input().split())
    c = tuple(map(int, input().split()))
    d = tuple(map(int, input().split()))
    d_y = d[0]-1
    d_x = d[1]-1
    s = [list(input()) for i in range(H)]

    visited = [[-1]*W for j in range(H)]
    visited[c[0]-1][c[1]-1] = 0

    main_q = deque()
    main_q.append((c[0]-1,c[1]-1))
    magic_q = deque()
    direction = [(0,1),(1,0),(-1,0),(0,-1)]

    #魔法使わないbfs
    while main_q:
        y, x = main_q.popleft()
        magic_q.append((y,x))

        for i in range(4):
            moved_y = y + direction[i][0]
            moved_x = x + direction[i][1]

            if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                continue
            if s[moved_y][moved_x] == '#':
                continue
            if s[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                main_q.append((moved_y, moved_x))
                visited[moved_y][moved_x] = visited[y][x]

        if not main_q:
            while magic_q:
                y, x = magic_q.popleft()

                for k in range(-2,3):
                    for l in range(-2,3):
                        moved_y = y + k
                        moved_x = x + l

                        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                            continue
                        if s[moved_y][moved_x] == '#':
                            continue
                        if s[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                            main_q.append((moved_y, moved_x))
                            visited[moved_y][moved_x] = visited[y][x] + 1
    print(visited[d_y][d_x])


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Accepted

Solution code:
import heapq

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
ty, tx = map(lambda x: int(x) - 1, input().split())
s, t = sy * W + sx, ty * W + tx
graph = [input() for _ in range(H)]

INF = 1 << 30
dist = [INF] * (H * W)
que = []

def push(v, d):
    if(dist[v] <= d):
        return
    dist[v] = d
    heapq.heappush(que, (d, v))

def move(ny, nx, d):
    if ny < 0 or ny >= H or nx < 0 or nx >= W:
        return
    if graph[ny][nx] == '.':
        push(ny * W + nx, d)

push(s, 0)

while que:
    d, v = heapq.heappop(que)
    if d > dist[v]:
        continue
    if v == t:
        break
    y, x = divmod(v, W)
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))

if dist[t] == INF:
    print(-1)
else:
    print(dist[t])

Submission status: Accepted

Solution code:
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw - 1, Ch - 1))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if S[ny][nx] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny][nx] == -1 or costmap[y][x] < costmap[ny][nx]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny][nx] = costmap[y][x]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx < 0 or nx >= W or ny < 0 or ny >= H:
                    continue
                if S[ny][nx] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny][nx] == -1 or costmap[y][x] + 1 < costmap[ny][nx]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny][nx] = costmap[y][x] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dh - 1][Dw - 1])

Submission status: Accepted

Solution code:
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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


def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny - 1][nx - 1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny - 1][nx - 1] = costmap[y - 1][x - 1]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny - 1][nx - 1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] + 1 < costmap[ny - 1][nx - 1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny - 1][nx - 1] = costmap[y - 1][x - 1] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dh - 1][Dw - 1])

Submission status: Accepted

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=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())

ch, cw = map(int, input().split())

dh, dw = map(int, input().split())

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

maze = []
for i in range(H):
    h = list(input())
    maze.append(h)

dist = [[float("inf") for _ in range(W)] for _ in range(H)]
dist[ch][cw] = 0

queue = deque([(ch, cw, 0)])

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

    if y == dh and x == dw:
        print(d)
        exit()

    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + i, x + j
        if 0 <= new_y < H and 0 <= new_x < W:
            if maze[new_y][new_x] != '#':
                if dist[new_y][new_x] > d:
                    dist[new_y][new_x] = d
                    queue.appendleft((new_y, new_x, d))

    for i in range(-2, 3):
        for j in range(-2, 3):
            new_y, new_x = y + i, x + j
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] != '#':
                    if dist[new_y][new_x] > d+1:
                        dist[new_y][new_x] = d+1
                        queue.append((new_y, new_x, d+1))

print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(h)]

d = deque([(sy, sx)])
cur = 1
while True:
    visited = set()
    while d:
        y, x = d.pop()
        visited.add((y, x))
        S[y][x] = cur
        if (y, x) == (gy, gx):
            print(cur-1)
            sys.exit()
        for dyi, dxi in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                d.append((y+dyi, x+dxi))

    for y, x in visited:
        for dyi in range(-2, 3):
            for dxi in range(-2, 3):
                if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                    d.append((y+dyi, x+dxi))
    if not d:
        print(-1)
        sys.exit()
    cur += 1

Submission status: Accepted

Solution code:
from collections import deque


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 歩き
    walk_list = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    # ワープ
    warp_list = [[-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]]
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    warp_checked = [[0 for _ in range(W)] for _ in range(H)]
    warp_que = deque([(DH, DW)])
    c = 0
    while len(warp_que) > 0:
        # warp_queから歩きのみでいける範囲の探索
        walk_que = deque()
        while len(warp_que) > 0:
            h, w = warp_que.pop()
            cnt[h][w] = c
            walk_que.append((h, w))
            tmp_walk_que = deque([(h, w)])
            while len(tmp_walk_que) > 0:
                h, w = tmp_walk_que.pop()
                for dh, dw in walk_list:
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and \
                        S[nh][nw] == '.' and cnt[nh][nw] == INF:
                        cnt[nh][nw] = c
                        tmp_walk_que.append((nh, nw))
                        walk_que.append((nh, nw))
        # ワープでしかいけない範囲の探索
        while len(walk_que) > 0:
            h, w = walk_que.pop()
            for dh, dw in warp_list:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and \
                    warp_checked[nh][nw] == 0 and cnt[nh][nw] == INF:
                    warp_checked[nh][nw] = 1
                    warp_que.append((nh, nw))
        c += 1

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
ch,cw = na()
dh,dw = na()
ch,cw = ch-1,cw-1
dh,dw = dh-1,dw-1
s = []
for i in range(h):
  s.append(ns())

from collections import deque

g = [[10000000000]*w for i in range(h)]
g[ch][cw] = 0
d = deque([(ch,cw,0)])

while d:
  x,y,num = d.popleft()
  pq = [(-1,0),(0,1),(1,0),(0,-1)]
  for p,q in pq:
    if not (0<=x+p<h and 0<=y+q<w):
      continue
    u = s[x+p][y+q]
    if u == '.':
      if num < g[x+p][y+q]:
        g[x+p][y+q] = num
        d.appendleft((x+p,y+q,num))

  for i in range(-2,3):
    for j in range(-2,3):
      if not (0<=x+i<h and 0<=y+j<w):
        continue
      p = s[x+i][y+j]
      if p == '.':
        if num+1 < g[x+i][y+j]:
          g[x+i][y+j] = num+1
          d.append((x+i,y+j,num+1))

ans = g[dh][dw]

print('-1' if ans == 10000000000 else ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw =  map(int, input().split())
Dh, Dw = map(int, input().split())

maze = ["#" * (W+4)]
maze.append("#" * (W+4))

for i in range(H):
    maze.append("##"+input()+"##")
maze.append("#" * (W+4))
maze.append("#" * (W+4))

ans = [[-1] * (W+4) for _ in range(H+4)]

for i in range(H+4):
    for j in range(W+4):
        if maze[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]]
warp = [[-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]]

movelst = deque([[Ch, Cw]])
movelst2 = deque([])

while len(movelst) > 0:
    x, y = movelst.popleft()
    movelst2.append([x, y])
    for p, q in move:
        v1, v2 = x+p, y+q
        if ans[v1][v2] == -1:
            movelst.append([v1, v2])
            ans[v1][v2] = ans[x][y]
    
    if len(movelst) == 0:
        while len(movelst2) > 0:
            x2, y2 = movelst2.popleft()
            for v1, v2 in warp:
                i, j = x2+v1, y2+v2
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2] + 1
                    movelst.append([i, j])

print(ans[Dh][Dw])

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
cy,cx = map(int,input().split())
dy,dx = map(int,input().split())
s = [input() for j in range(h)]

chk = [[-1]*(w) for _ in range(h)]

seg = [[] for _ in range(h*w)]

div = 0

vx = [0,1,0,-1]
vy = [1,0,-1,0]

q = deque()
q.appendleft([cy-1,cx-1,0])
#seg[0].append([c[0],c[1],div])
while len(q) > 0:
    y,x,div = q.popleft()
    #print(y,x,div)
    if chk[y][x] != -1:
        continue
    chk[y][x] = div
    for i in range(4):
        y_n = y + vy[i]
        x_n = x + vx[i]
        if y_n >= 0 and y_n <= h-1 and x_n >= 0 and x_n <= w-1:
            if s[y_n][x_n] == '.':
                if chk[y_n][x_n] == -1:
                    q.appendleft([y_n,x_n,div])
                    
    for i in range(5):
        for j in range(5):
            y_n = y + (-2+i)
            x_n = x + (-2+j)
            
            if y_n >= 0 and y_n <= h-1 and x_n >= 0 and x_n <= w-1:
                if s[y_n][x_n] == '.':
                    if chk[y_n][x_n] == -1:
                        q.append([y_n,x_n,div+1])
                        
                        
print(chk[dy-1][dx-1])
#print(chk)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
#
# H, W, = 4, 4
# CH, CW = 1, 1
# DH, DW = 4, 4
#
# ARR = [
#     "..#.",
#     "..#.",
#     ".#..",
#     ".#.."
# ]
#
#
#
# H,W = 4, 4
# CH, CW = 1, 4
# DH, DW = 4, 1
# ARR = [
#     ".##.",
#     "####",
#     "####",
#     ".##."
# ]
#
#
#
# H,W = 4, 4
# CH,CW = 2, 2
# DH,DW = 3, 3
# ARR = [
#     "....",
#     "....",
#     "....",
#     "...."
# ]
#
#
# H,W = 4, 5
# CH,CW = 1, 2
# DH,DW = 2, 5
#
# ARR = [
#     "#.###",
#     "####.",
#     "#..##",
#     "#..##"
# ]
#
#

H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
ARR = []

for i in range(H):
    ARR.append(input())




def calculate(h, w, ch, cw, dh, dw, arr):

    status = [[-1 for j in range(w)] for i in range(h)]

    q = deque()

    q.append((ch - 1, cw - 1))
    status[ch - 1][cw - 1] = 0

    while len(q) > 0:
        currentY, currentX = q.popleft()
        childrens = [(currentY, currentX - 1), (currentY + 1, currentX), (currentY, currentX + 1),
                     (currentY - 1, currentX)]

        for child in childrens:
            childY, childX = child
            if childX >= 0 and childX < w and childY >= 0 and childY < h:
                if arr[childY][childX] == ".":
                    if status[childY][childX] == -1:
                        q.insert(0,(childY, childX))
                        status[childY][childX] = status[currentY][currentX]
                    else:
                        if status[childY][childX] > status[currentY][currentX]:
                            status[childY][childX] = status[currentY][currentX]
                            q.insert(0,(childY, childX))

        for i in range(-2, 3):
            for j in range(-2, 3):
                childY = currentY + i
                childX = currentX + j
                if (childY, childX) in childrens:
                    continue

                if childX >= 0 and childX < w and childY >= 0 and childY < h:
                    if arr[childY][childX] == ".":
                        if status[childY][childX] == -1:
                            status[childY][childX] = (status[currentY][currentX] + 1)
                            q.append((childY, childX))
                        else:
                            if status[childY][childX] > (status[currentY][currentX] + 1):
                                status[childY][childX] = (status[currentY][currentX] + 1)
                                q.append((childY, childX))
    print(status[dh-1][dw-1])
calculate(H,W,CH,CW,DH,DW,ARR)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = [input() for _ in range(H)]

d.appendleft((Ch-1, Cw-1, 0))
score = [[-1] * W for _ in range(H)]
score[Ch-1][Cw-1] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x, s = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx, s))
          score[y+dy][x+dx] = s
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx, s+1))
          score[y+dy][x+dx] = s+1

print(score[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
import math
#import numpy as np
#import numba
#from numba import njit, b1, i4, i8, f8
#from numba import jit
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

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

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch+=-1
    Cw+=-1
    Dh,Dw = map(int,input().split())
    Dh+=-1
    Dw+=-1
    S = [None for i in range(H)]
    
    for i in range(H):
        S[i] = input()
        
    ans=0
    visited = [[False for i in range(W)] for j in range(H)]
    walk_deque = deque()
    walk_deque.append((Ch,Cw))
    visited[Ch][Cw]=True
    while(1):
        new_visited = []
        while(len(walk_deque) != 0):
            Ph,Pw = walk_deque.popleft()
            new_visited.append([Ph,Pw])
            #print(Ph,Pw)
            if Ph==Dh and Pw==Dw:
                print(ans)
                return
            for i in range(4):
                tmph = Ph+dy[i]
                tmpw = Pw+dx[i]
                if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                    if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                        walk_deque.append((tmph,tmpw))
                        visited[tmph][tmpw]=True

        #print("warp")
        for h,w in new_visited:
            for x in [-2,-1,0,1,2]:
                for y in [-2,-1,0,1,2]:
                    tmph = h+y
                    tmpw = w+x
                    if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                        if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                            walk_deque.append((h+y,w+x))
                            visited[h+y][w+x]=True
        ans+=1
        if len(walk_deque)==0:
            print(-1)
            return
        
if __name__ == '__main__':
    main()