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:
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 = [input().rstrip() for i in range(H)]
    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:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for _ in range(H)]

num = 0
if S[0][0] == '#':
    S[0][0] = -1
else:
    num += 1
    S[0][0] = num

for i in range(1, H):
    if S[i][0] == '#':
        S[i][0] = -1
    elif S[i-1][0] > 0:
        S[i][0] = S[i-1][0]
    else:
        num += 1
        S[i][0] = num

for j in range(1, W):
    if S[0][j] == '#':
        S[0][j] = -1
    elif S[0][j-1] > 0:
        S[0][j] = S[0][j-1]
    else:
        num += 1
        S[0][j] = num

for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == '#':
            S[i][j] = -1
        elif S[i-1][j] < 0 and S[i][j-1] < 0:
            num += 1
            S[i][j] = num
        elif S[i-1][j] < 0:
            S[i][j] = S[i][j-1]
        elif S[i][j-1] < 0:
            S[i][j] = S[i-1][j]
        else:
            S[i][j-1] = min(S[i-1][j], S[i][j-1])
            S[i-1][j] = min(S[i-1][j], S[i][j-1])
            S[i][j] = min(S[i-1][j], S[i][j-1])

G = [{} for _ in range(num)]

for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue

        start_i = max(0, i-2)
        start_j = max(0, j-2)
        end_i = min(H, i+3)
        end_j = min(W, j+3)
        for x in range(start_i, end_i):
            for y in range(start_j, end_j):
                if S[x][y] > 0 and S[x][y] != S[i][j]:
                    G[S[x][y]-1][S[i][j]-1] = 1
                    G[S[i][j]-1][S[x][y]-1] = 1

for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue

        start_i = max(0, i-2)
        start_j = max(0, j-2)
        end_i = min(H, i+3)
        end_j = min(W, j+3)
        for x in range(start_i, end_i):
            for y in range(start_j, end_j):
                if (x, y) in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
                    if S[x][y] > 0 and S[x][y] != S[i][j]:
                        G[S[x][y]-1][S[i][j]-1] = 0
                        G[S[i][j]-1][S[x][y]-1] = 0

from heapq import heapify, heappop, heappush
def dijkstra(s):
    dist = [float('inf')] * num
    dist[s] = 0

    heap = [(s, 0)]
    heapify(heap)
    while heap:
        v, c = heappop(heap)
        if c > dist[v]: continue
        for u, d in G[v].items():
            tmp = d + dist[v]
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(heap, (u, tmp))

    return dist

start = S[Ch-1][Cw-1]-1
end = S[Dh-1][Dw-1]-1
dist = dijkstra(start)

ans = -1 if dist[end] == float('inf') else dist[end]
print(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())
a = []
for _ in range(h):
    a.append(input())
INF = 10**9
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
step = [[INF]*w for _ in range(h)]
step[ch-1][cw-1] = 0
q = deque([(ch-1, cw-1)])
nq = deque()
while True:
    while q:
        y, x = q.popleft()
        nq.append((y, x))
        for dy, dx in dxdy:
            if not (0<=x+dx<w and 0<=y+dy<h):
                continue
            if a[y+dy][x+dx]=='#':
                continue
            if step[y+dy][x+dx]>step[y][x]:
                step[y+dy][x+dx] = step[y][x]
                q.append((y+dy, x+dx))
    while nq:
        y, x = nq.popleft()
        for i in range(25):
            dy = i//5-2
            dx = i%5-2
            if not (0<=x+dx<w and 0<=y+dy<h):
                continue
            if a[y+dy][x+dx]=='#':
                continue
            if step[y+dy][x+dx]>step[y][x]+1:
                step[y+dy][x+dx] = step[y][x]+1
                q.append((y+dy, x+dx))
    if not q:
        break
if step[dh-1][dw-1]==INF:
    print(-1)
else:
    print(step[dh-1][dw-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))


h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [set() for i in range(2)]
i = 0
a[i].add(start)
dist[start] = 0

while a[i]:
    p = a[i].pop()
    if dist[goal] <= dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        a[i].add(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        a[i-1].add(q)
                        dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Accepted

Solution code:
# 01-BFS
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
# 01-BFSのちょっと丁寧な解説 - ARMERIA
# https://betrue12.hateblo.jp/entry/2018/12/08/000020

from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))
    gen_warp_can_reach = (
        (h, w, (h, w) in can_walk)  # 移動先，徒歩で行けるか
        for h in range(-2, 3) for w in range(-2, 3) if not h == 0 == w)
    warp_can_reach = tuple(gen_warp_can_reach)
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# 01-BFS
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
# 01-BFSのちょっと丁寧な解説 - ARMERIA
# https://betrue12.hateblo.jp/entry/2018/12/08/000020

from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))
    gen_warp_can_reach = (
        (h, w, (h, w) in can_walk)  # 移動先，徒歩で行けるか
        for h in range(-2, 3) for w in range(-2, 3) if not h == 0 == w)
    warp_can_reach = set(gen_warp_can_reach)
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

# 二次元ダイクストラ
def Dijkstra(start, goal, size):
    sy, sx = start
    gy, gx = goal
    dist = [[float('inf')] * W for i in range(H)]
    pos = [(0, sy, sx)]
    heapify(pos)
    dist[sy][sx] = 0

    while len(pos):
        cost, y, x = heappop(pos)

        if y == gy and x == gx:
            return cost
        if dist[y][x] < cost:
            continue
        # エッジは探索のたびに生成していく
        # walking
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.':
                if dist[ny][nx] > cost:
                    dist[ny][nx] = cost
                    heappush(pos, (cost, ny, nx))
        # warp
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                wy = y + w_y
                wx = x + w_x
                if 0 <= wy < H and 0 <= wx < W and maze[wy][wx] == '.':
                    if dist[wy][wx] > cost + 1:
                        dist[wy][wx] = cost + 1
                        heappush(pos, (cost + 1, wy, wx))
    return dist[gy][gx]

ans = Dijkstra((Ch, Cw), (Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

"""
pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 歩いて移動
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            # 0-1 bfs
            # 先頭に置く
            pos.appendleft([ny, nx])
            dp[ny][nx] = dp[y][x]
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            # 歩いて移動不可能でないと使わない
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])
"""

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 = [input().rstrip() for i in range(H)]
    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:
        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))

        if not dq:
            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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

# 二次元ダイクストラ
def Dijkstra(start, goal, size):
    sy, sx = start
    gy, gx = goal
    dist = [[float('inf')] * W for i in range(H)]
    pos = [(0, sy, sx)]
    heapify(pos)
    dist[sy][sx] = 0

    while len(pos):
        cost, y, x = heappop(pos)

        if y == gy and x == gx:
            return cost
        if dist[y][x] < cost:
            continue
        # エッジは探索のたびに生成していく
        # walking
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.':
                if dist[ny][nx] > cost:
                    dist[ny][nx] = cost
                    heappush(pos, (cost, ny, nx))
        # warp
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                wy = y + w_y
                wx = x + w_x
                if 0 <= wy < H and 0 <= wx < W and maze[wy][wx] == '.':
                    if dist[wy][wx] > cost + 1:
                        dist[wy][wx] = cost + 1
                        heappush(pos, (cost + 1, wy, wx))
    return dist[gy][gx]

ans = Dijkstra((Ch, Cw), (Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# 01-BFS
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
# 01-BFSのちょっと丁寧な解説 - ARMERIA
# https://betrue12.hateblo.jp/entry/2018/12/08/000020

from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                yield (h, w, (h, w) in can_walk)
    warp_can_reach = tuple(gen_warp_can_reach())  # 移動先，徒歩で行けるか
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

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 = [input().rstrip() for i in range(H)]
    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:
        x, y = dq.pop()
        #コスト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))
                
        if not dq:
            dq = 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
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.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 s[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]]
    magic = [
        [-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]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [[]for i in range(2)]
i = 0
a[i].append(start)
dist[start] = 0

while a[0] or a[1]:
    p = a[i].pop()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        a[i].append(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        a[i-1].append(q)
                        dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]


print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Accepted

Solution code:
import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline




def solve(dist, start, goal, moves):
    q = [start]
    c0 = 0
    c1 = 1
    while q:
        nq = []
        while q:
            x = q.pop()
            if x == goal:
                return c0
            if dist[x] < c0:
                continue
            for d,l in moves:
                nx = x+d
                dnx = dist[nx]
                if dnx > c0:
                    dist[nx] = c0
                    q.append(nx)
                elif dnx < 0:
                    for t in l:
                        p = x+t
                        if dist[p] > c1:
                            dist[p] = c1
                            nq.append(p)
        q = nq
        c0 += 1
        c1 += 1
    return -1




if __name__ == '__main__':

    MOVES = (
    ((1, 0), ((2,-1),(2,0),(2,1),(2,2),(1,1))),
    ((-1, 0),((-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1))),
    ((0, 1), ((1,2),(0,2),(-1,2),(-2,2),(-1,1))),
    ((0, -1), ((1,-2),(0,-2),(-1,-2),(2,-2),(1,-1))),
    )

    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)+1,readline().split()))
    goal = tuple(map(lambda i:int(i)+1,readline().split()))

    H += 4
    W += 4

    dist = [-1]*(W*H)
    convert = lambda x,y: x*W+y

    start = convert(*start)
    goal = convert(*goal)

    i = 2*W+2
    for s in read().split():
        for c in s.decode():
            if c == '.':
                dist[i] = 10**7
            i += 1
        i += 4

    moves = tuple((convert(*d),tuple(convert(*d) for d in l)) for d,l in MOVES)

    print(solve(dist,start,goal,moves))

Submission status: Accepted

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black" and D[X][Y]>D[x][y]:
                    D[X][Y]=D[x][y]
                    color[X][Y]="gray"
                    queue.appendleft([X,Y])

        for i in range(max(0,x-2),min(h,x+3)):
            for j in range(max(0,y-2),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black" and D[X][Y]>D[x][y]+1:
                        D[X][Y]=D[x][y]+1
                        color[X][Y]="gray"
                        queue.append([X,Y])
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    gh, gw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    S = read().split()

    dist = [[INF] * W for _ in range(H)]
    walk = ((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))

    Q = deque()
    Q.append((sh, sw))
    Q2 = deque()
    dist[sh][sw] = 0

    while Q:
        while Q:
            h, w = Q.popleft()
            d = dist[h][w]
            flag = 0
            for dh, dw in walk:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.':
                        if dist[nh][nw] > d:
                            dist[nh][nw] = d
                            Q.append((nh,nw))
                    else:
                        flag += 1
            if flag:
                Q2.append((h,w))
        while Q2:
            h, w = Q2.popleft()
            d = dist[h][w]
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.' and dist[nh][nw] == INF:
                        dist[nh][nw] = d + 1
                        Q.append((nh,nw))
    if dist[gh][gw] != INF:
        print(dist[gh][gw])
    else:
        print(-1)



if __name__ == '__main__':
    main()