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:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #0:未訪問、1:訪問済み
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

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

while q:
    fro_h, fro_w=q.popleft()
    if visit[(fro_h, fro_w)]==1: continue
    visit[(fro_h, fro_w)]=1
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)] and visit[(to_h, to_w)]==0:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)] and visit[(to_h, to_w)]==0:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

from collections import deque
import itertools

h,w = map(int,readline().split())
cx,cy = map(int,readline().split())
gx,gy = map(int,readline().split())
cx -= 1
cy -= 1
grid = [readline().rstrip() for i in range(h)]

dist = [[INF]*w for i in range(h)]
dist[cx][cy] = 0

l2 = list(itertools.product([-2,-1,0,1,2],repeat = 2))
l1 = [(-1,0),(1,0),(0,-1),(0,1)]
q1 = deque([(cx,cy)])
q2 = deque([(cx,cy)])

while q1 or q2:
    if q1:
        x,y = q1.popleft()
        for dy,dx in l1:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] > dist[x][y]:
                dist[nx][ny] = dist[x][y]
                q1.append((nx,ny))
                q2.append((nx,ny))
    else:
        x,y = q2.popleft()
        for dy,dx in l2:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                q1.append((nx,ny))
                q2.append((nx,ny))

print(dist[gx-1][gy-1] if dist[gx-1][gy-1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

from collections import deque
import itertools

h,w = map(int,readline().split())
cx,cy = map(int,readline().split())
gx,gy = map(int,readline().split())
cx -= 1
cy -= 1
grid = [readline().rstrip() for i in range(h)]

dist = [[INF]*w for i in range(h)]
dist[cx][cy] = 0

l2 = list(itertools.product([-2,-1,0,1,2],repeat = 2))
l1 = [(-1,0),(1,0),(0,-1),(0,1)]
q1 = deque([(cx,cy)])

while q1:
    if q1:
        x,y = q1.popleft()
        for dy,dx in l1:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] > dist[x][y]:
                dist[nx][ny] = dist[x][y]
                q1.appendleft((nx,ny))
        for dy,dx in l2:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                q1.append((nx,ny))

print(dist[gx-1][gy-1] if dist[gx-1][gy-1] != INF else -1)

Submission status: Accepted

Solution code:
#入力受け取りの高速化、しなくてもよい
#但し文字列のまま扱うときは注意、例えば . は46として、 # は35として扱われる
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
#ここまでが高速化
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()
#0 based index (0始まり)にする
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
#dqが徒歩、2が魔法での移動を入れる
dq=deque([(nx,ny)])
dq2=deque([])
#かかるコストを保存しておく
T=[[float('inf')]*w for  a in range(h)]
#初期値は0で、スタート地点に保存
T[nx][ny]=0
#徒歩でのx,yの差分
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
#魔法での移動の差分、tuple( (i,j) |-2<=i,j<=2かつ(i,j)!=(0,0)  )と等価
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    #先に徒歩で行けるだけ行きたいので、徒歩を使い切るまでは魔法で行った地点たちに手を出さない
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            #盤面の外や壁にぶつかるのは除外
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                #コストを更新できるなら改めて捜査
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    #徒歩で行ける地点を使い切ったので、今度は魔法で行ける地点を捜査
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])

Submission status: Accepted

Solution code:
from collections import deque
def main():
    H, W = map(int, input().split())
    sh,sw = map(int, input().split())
    gh,gw = map(int, input().split())
    gh,gw = gh-1,gw-1
    field = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, sh-1, sw-1))
    INF = 10 ** 30
    dist = [[INF] * W for _ in range(H)]
    dist[sh-1][sw-1] = 0
    while q:
        cnt, h, w = deque.popleft(q)
        if dist[h][w] < cnt: continue
        if h == gh and w == gw: return cnt
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh = h+i
                nw = w+j
                if nh < 0 or nw < 0: continue
                if nh >= H or nw >= W: continue
                if field[nh][nw]  == "#": continue
                if (i, j) in ((1,0),(0,1),(-1,0),(0,-1)):
                    if dist[nh][nw] <= cnt: continue
                    dist[nh][nw] = cnt
                    deque.appendleft(q, (cnt, nh, nw))
                else:
                    if dist[nh][nw] <= cnt+1: continue
                    dist[nh][nw] = cnt+1
                    deque.append(q, (cnt+1, nh, nw))
    return -1

print(main())

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Submission status: Accepted

Solution code:
# 01BFS
INF = 10**9 + 7


def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]

    def bfs_2d(c, sy, sx, gh, gw, H, W):
        que0 = deque()
        que1 = deque()
        dist = [[INF]*W for i in range(H)]

        dist[sy][sx] = 0
        que0.append((sy, sx))
        while que0 or que1:
            if que0:
                uh, uw = que0.popleft()
            else:
                uh, uw = que1.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = uh + dh
                    next_w = uw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not(0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if c[next_h][next_w] == "#":
                        continue
                    if dist[next_h][next_w] > dist[uh][uw] + cost:
                        dist[next_h][next_w] = dist[uh][uw] + cost
                        if cost == 0:
                            que0.append((next_h, next_w))
                        else:
                            que1.append((next_h, next_w))
        return dist[gh][gw] if dist[gh][gw] != INF else -1

    ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 01BFS
INF = 10**9 + 7


def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]

    def bfs_2d(c, sy, sx, gh, gw, H, W):
        que = deque()
        dist = [[INF]*W for i in range(H)]

        dist[sy][sx] = 0
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = uh + dh
                    next_w = uw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not(0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if c[next_h][next_w] == "#":
                        continue
                    if dist[next_h][next_w] > dist[uh][uw] + cost:
                        dist[next_h][next_w] = dist[uh][uw] + cost
                        if cost == 1:
                            que.append((next_h, next_w))
                        else:
                            que.appendleft((next_h, next_w))
        return dist[gh][gw] if dist[gh][gw] != INF else -1

    ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    C1, C2 = map(lambda x: int(x) - 1, readline().split())
    D1, D2 = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]



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


    for h in range (H):
        Sh = S[h]
        th = t[h]
        for w in range (W):
            if Sh[w] == '#':
                th[w] = -1


    q = deque([(C1,C2)])
    a = 0
    t[C1][C2] = a

    while q:
        warpq = []
        while q:
            h,w = q.popleft()
            warpq.append((h,w))
            if 0 < h and t[h-1][w] > a:
                t[h-1][w] = a
                q.append((h-1,w))
            if H-1 > h and t[h+1][w] > a:
                t[h+1][w] = a
                q.append((h+1,w))
            if 0 < w and t[h][w-1] > a:
                t[h][w-1] = a
                q.append((h,w-1))
            if w < W-1 and t[h][w+1] > a:
                t[h][w+1] = a
                q.append((h,w+1))

        if t[D1][D2]!= INF:
            break

        a+=1

        for h,w in warpq:
            for i in range (max(0,h-2),min(H,h+3)):
                ti = t[i]
                for j in range (max(0,w-2),min(W,w+3)):
                    if ti[j] >a:
                        ti[j] = a
                        q.append((i,j))


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

main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))

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


main()

Submission status: Accepted

Solution code:
from queue import Queue
from collections import deque

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

S = []
for _ in range(H):
    S.append(list(input()))

path = dict()
cache = set()

Score = [[-1 for _ in range(W)] for __ in range(H)]

Cur = (Cw-1, Ch-1)
Q = deque()
Q.appendleft(Cur)
Score[Cur[1]][Cur[0]] = 0

# path[Cur] = 0
G = (Dw-1, Dh-1)

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

wdx = []
wdy = []

while not len(Q) == 0:

    node = Q.popleft()
    cx, cy = node

    # move
    for di in range(4):
        nx = cx + dx[di]
        ny = cy + dy[di]

        if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.' and (Score[ny][nx] == -1 or Score[ny][nx] > Score[cy][cx]):
            nt = (nx, ny)
            Q.appendleft(nt)
            Score[ny][nx] = Score[cy][cx]
    
    # warp
    for wdx in range(-2, 3, 1):
        for wdy in range(-2, 3, 1):
            if wdx == wdy == 0:
                continue

            nx = cx + wdx
            ny = cy + wdy
            nt = (nx, ny)

            if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.' and (Score[ny][nx] == -1 or Score[ny][nx] > Score[cy][cx] + 1):
                nt = (nx, ny)
                Q.append(nt)
                Score[ny][nx] = Score[cy][cx] + 1

print(Score[G[1]][G[0]])

Submission status: Accepted

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [data() for i in range(n)]
inf = 10 ** 10
q = deque()
q.append([sx, sy])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
jump = [[inf] * m for _ in range(n)]
jump[sx][sy] = 0
while q:
    sx, sy = q.popleft()
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if jump[tx][ty] > jump[sx][sy]:
                q.appendleft([tx, ty])
                jump[tx][ty] = jump[sx][sy]
    for i in range(-2, 3):
        for j in range(-2, 3):
            tx, ty = sx + i, sy + j
            if valid(tx, ty) and mat[tx][ty] == ".":
                if jump[tx][ty] > jump[sx][sy] + 1:
                    q.append([tx, ty])
                    jump[tx][ty] = jump[sx][sy]+1
if jump[ex][ey] == 10 ** 10:
    print(-1)
    exit()
print(jump[ex][ey])

Submission status: Accepted

Solution code:
from heapq import *
import sys; input = sys.stdin.readline
inf = int(1e10)
n, m = map(int, input().split())
x, y = map(int, input().split())
dx, dy = map(int, input().split())
x, y, dx, dy = x-1, y-1, dx-1, dy-1
matrix = [list(input().strip()) for _ in range(n)]
v = [[inf for _ in range(m)] for _ in range(n)]
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def valid(x, y): return (0<=x<n) and (0<=y<m) and (matrix[x][y] != '#')
v[x][y] = 0
q = [(0, (x, y))]
while q:
	d, node = heappop(q)
	for i in moves:
		xx, yy = node[0]+i[0], node[1]+i[1]
		if valid(xx, yy) and v[xx][yy] > d:
			v[xx][yy] = d
			heappush(q, (v[xx][yy], (xx, yy)))
	for i in range(node[0]-2, node[0]+3):
		for j in range(node[1]-2, node[1]+3):
			if valid(i, j) and v[i][j] > d + 1:
				v[i][j] = d + 1
				heappush(q, (v[i][j], (i, j)))
if v[dx][dy] == inf: print(-1)
else: print(v[dx][dy])

Submission status: Accepted

Solution code:
INF = 10**9 + 7


def main():
    from heapq import heappop, heappush
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]

    dist = [[INF]*W for _ in range(H)]
    dist[Ch][Cw] = 0
    que = [(0, Ch*W + Cw)]
    while que:
        u_dist, u = heappop(que)
        uh, uw = u//W, u % W
        if dist[uh][uw] < u_dist:
            continue
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = uh + dh
                nw = uw + dw
                if nh < 0 or H <= nh or nw < 0 or W <= nw:
                    continue
                if A[nh][nw] == "#":
                    continue
                cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                if dist[nh][nw] > dist[uh][uw] + cost:
                    dist[nh][nw] = dist[uh][uw] + cost
                    heappush(que, (dist[nh][nw], nh*W + nw))

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

    # for h in range(H):
    #     print(dist[h])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

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

s = []
for _ in range(H):
    s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]

q = []
heapq.heappush(q, (0, (ch, cw)))

while q:
    c, (h, w) = heapq.heappop(q)
    if cs[h][w] < c:
        continue
    cs[h][w] = c
    for nh, nw in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c < cs[nh][nw]:
            cs[nh][nw] = c
            heapq.heappush(q, (c, (nh, nw)))
    for nh in range(h - 2, h + 3):
        for nw in range(w - 2, w + 3):
            if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c + 1 < cs[nh][nw]:
                cs[nh][nw] = c + 1
                heapq.heappush(q, (c + 1, (nh, nw)))

print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
sy, sx = LI()
gy, gx = LI()
sy -= 1
sx -= 1
gy -= 1
gx -= 1
maze = [input() for _ in range(h)]
dist = [[inf] * w for _ in range(h)]
que = deque([(sy, sx)])
dist[sy][sx] = 0
while que:
    y, x = que.popleft()
    for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        ny, nx = y + dy, x + dx
        if 0 <= ny < h and 0 <= nx < w:
            if maze[ny][nx] == '.' and dist[ny][nx] > dist[y][x]:
                dist[ny][nx] = dist[y][x]
                que.appendleft((ny, nx))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y + dy, x + dx
            if 0 <= ny < h and 0 <= nx < w:
                if maze[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1:
                    dist[ny][nx] = dist[y][x] + 1
                    que.append((ny, nx))
if dist[gy][gx] == inf:
    print(-1)
else:
    print(dist[gy][gx])

Submission status: Accepted

Solution code:
from collections import deque

H, W = [int(s) for s in input().split()]
Ch, Cw = [int(s) - 1 for s in input().split()]
Dh, Dw = [int(s) - 1 for s in input().split()]

fields = [list(input()) for _ in range(H)]
fields_num = [[-1] * W for _ in range(H)]
ok_field = '.'


def get_search_obj(i, j):
    ret = []
    moving_range = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    for dx, dy in moving_range:
        if 0 <= i + dx <= (H - 1) and 0 <= j + dy <= (W - 1) and fields[i + dx][j + dy] == ok_field:
            ret.append((i + dx, j + dy))
    return ret


def get_search_obj_cost2(i, j):
    ret = []
    moving_range = ((x, y) for x in range(- 2, 3) for y in range(- 2, 3))
    for dx, dy in moving_range:
        if 0 <= i + dx <= (H - 1) and 0 <= j + dy <= (W - 1) and fields[i + dx][j + dy] == ok_field:
            ret.append((i + dx, j + dy))
    return ret


def bfs(sx, sy):
    start = ((sx, sy), 0)
    dq = deque([start])
    visited = [[False] * W for _ in range(H)]
    while dq:
        (sx, sy), cost = dq.pop()
        if (sx, sy) == (Dh, Dw):
            return cost
        if visited[sx][sy]:
            continue
        else:
            visited[sx][sy] = True
        for x, y in get_search_obj(sx, sy):
            dq.append(((x, y), cost))
        for x, y in get_search_obj_cost2(sx, sy):
            dq.appendleft(((x, y), cost + 1))
    return -1


print(bfs(Ch, Cw))

Submission status: Accepted

Solution code:
INF=10**20
from heapq import heappop,heappush,heapify
def dijkstra(G,H,W,sh,sw):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[(0,sh*10000+sw)]
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    while que:
        mincost,u=heappop(que)
        h,w=u//10000,u%10000
        if(mincost>dist[h][w]):
            continue
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='#'):
                continue
            if(dist[h][w]<dist[nh][nw]):
                dist[nh][nw]=dist[h][w]
                heappush(que,(dist[nh][nw],nh*10000+nw))
        for nh in range(h-2,h+3):
            for nw in range(w-2,w+3):
                if (nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    continue
                if(G[nh][nw]=='#'):
                    continue
                if dist[h][w]+1<dist[nh][nw]:
                    dist[nh][nw]=dist[h][w]+1
                    heappush(que,(dist[nh][nw],nh*10000+nw))
    return dist

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())
G=[tuple(input()) for i in range(H)]
dist=dijkstra(G,H,W,Ch,Cw)
ans=dist[Dh][Dw]
if ans!=INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import heapq
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def dijkstra(init_v):
    next_v = [(0, init_v)]
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


ans = dijkstra(start)[goal]
print(-1 if ans == INF else ans)

Submission status: Accepted

Solution code:
from itertools import product
from collections import deque
INF = 1e7
def main():
    H, W = map(int, input().split())
    ch, cw = map(lambda x: int(x)+1, input().split())
    dh, dw = map(lambda x: int(x)+1, input().split())
    S = [["#"]*(W+4) for _ in range(H+4)]
    # whites = [] #　道であるindex
    for i in range(2, H+2):
        tmp = input()
        for j in range(2, W+2):
            S[i][j] = tmp[j-2]
            # if S[i][j] == ".":
                # whites.append((i,j))

    dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
    magic = list(product(range(-2, 3), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    
    # graph = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for dx, dy in dxdy:
    #         if S[x+dx][y+dy] == ".":
    #             graph[idx].append((x+dx, y+dy))
    # graph2 = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for mx, my in magic:
    #         if S[x+mx][y+my] == ".":
    #             graph2[idx].append((x+mx, y+my))
    
    def bfs(u,v):
        dist = [[INF] * (W+4) for _ in range(H+4)] #indexed from 1
        # seen = [[0] * (W+4) for _ in range(H+4)] #indexed from 1
        queue = deque()
        # seen[u][v] = 1
        dist[u][v] = 0
        queue.append((u,v))
        while queue:
            p, q = queue.popleft()
            # if not graph[(p,q)]:
            #     queue.popleft()
            #     continue
            # g,h = graph[(p,q)].popleft()
            # if seen[g][h]:
            #     continue
            # seen[g][h] = 1
            # dist[g][h] = min(dist[g][h], dist[p][q])
            for dx, dy in dxdy:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g,h))
            for dx, dy in magic:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:
                    dist[g][h] = dist[p][q]+1
                    queue.append((g,h))
            # dist[g][h] = min(dist[g][h], dist[p][q]+1)
            # queue.append((g,h))
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()