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:
H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for i in range(H)]
from collections import deque
q=deque([(ch-1,cw-1,0)])
v=[[9**9]*W for i in range(H)]
x=((1,0),(-1,0),(0,-1),(0,1))
y=((2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2))
while q:
    h,w,d=q.popleft()
    for i,j in x:
        if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=='.' and d<v[h+i][w+j]:
            v[h+i][w+j]=d
            q.appendleft((h+i,w+j,d))
    for i,j in y:
        if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=='.' and d+1<v[h+i][w+j]:
            v[h+i][w+j]=d+1
            q.append((h+i,w+j,d+1))
print(v[dh-1][dw-1] if v[dh-1][dw-1]<9**9 else -1)

Submission status: Accepted

Solution code:
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 = [input() for _ in range(height)]

    adjacents = (
        (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
                if (h, w) in adjacents:
                    continue
                yield (h, w)

    warp_can_reach = tuple(gen_warp_can_reach())

    qu = deque()
    qu.append((init_h, init_w))
    distances = [[-1] * width for _ in range(height)]
    # distances のインデックスアクセスが遅いので，訪問済みは set で管理する。
    arrived_total = set()
    arrived_total.add((init_h, init_w))
    warp_count = 0

    def append_qu(now_h, now_w, next_go_to):
        """行き先へ進めそうならキューに追加し， arrived_total に記録する。"""
        for h_delta, w_delta in next_go_to:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if (new_h, new_w) in arrived_total:
                continue
            if grid[new_h][new_w] == '#':
                arrived_total.add((new_h, new_w))
                continue
            qu.append((new_h, new_w))
            arrived_total.add((new_h, new_w))

    while qu:
        arrived_set_by_cost = set()
        # 歩行 BFS
        while qu:
            h, w = qu.popleft()
            if h == dest_h and w == dest_w:
                return warp_count
            distances[h][w] = warp_count
            arrived_set_by_cost.add((h, w))
            append_qu(h, w, adjacents)

        warp_count += 1
        # ワープして行ける場所を列挙し，次期スタート地点とする。
        for h, w in arrived_set_by_cost:
            append_qu(h, w, warp_can_reach)

    return distances[dest_h][dest_w]


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    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 = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input()[:-1] + "##")
    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
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
             (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
             (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
             (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
        
    not_yet = [(ch, cw)]
    one_time = []
    
    while len(not_yet) > 0:
        x, y = not_yet.pop()
        one_time.append((x, y))
        for (p, q) in move:
            v1, v2 = x+p, y+q
            if ans[v1][v2] == -1:
                not_yet.append((v1, v2))
                ans[v1][v2] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.pop()
                for (v1, v2) in move2:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        not_yet.append((i, j))
          
    print(ans[dh][dw])
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())

array_st=list(map(int,input().split()))
array_gl=list(map(int,input().split()))
start_point=[]
goal_point=[]
for i in range(2):
    start_point.append(array_st[i]-1)
    goal_point.append(array_gl[i]-1)

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

d=deque()
d.append([start_point[0],start_point[1],0])

road=[-1,1]

ans=-1
while d:
    v=d.popleft()
    if matrix[v[0]][v[1]]=="x":
        continue
    matrix[v[0]][v[1]]="x"
    if [v[0],v[1]]==goal_point:
        ans=v[2]
        break
    for i in road:
        if v[0]+i>=0 and v[0]+i<H:
            if matrix[v[0]+i][v[1]]==".":
                d.appendleft([v[0]+i,v[1],v[2]])
        if v[1]+i>=0 and v[1]+i<W:
            if matrix[v[0]][v[1]+i]==".":
                d.appendleft([v[0],v[1]+i,v[2]])

    for i in range(-2,3):
        for j in range(-2,3):
            if v[0]+i>=0 and v[0]+i<H:
                if v[1]+j>=0 and v[1]+j<W:
                    if matrix[v[0]+i][v[1]+j]==".":
                        d.append([v[0]+i,v[1]+j,v[2]+1])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,(ux,uy) = hpp(q)
    if (ux,uy)==goal:
        break
#     print(ux,uy, num, prv)
#     for xx,yy,vv in zip(dx,dy,vvs):
    for xx in range(-2,3):
        for yy in range(-2,3):
            if (xx==yy==0):
                continue
            if abs(xx)+abs(yy)>1:
                vv = 1
            else:
                vv = 0
            x = ux+xx
            y = uy+yy
            num = pnum+vv
            if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
                continue            
            if seen[x*w+y] is None or seen[x*w+y]>num:
                seen[x*w+y] = num
                hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
#. 46 # 35
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
dq=deque([(nx,ny)])
dq2=deque([])
T=[[float('inf')]*w for  a in range(h)]
T[nx][ny]=0
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
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:
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)]
    V = [[-1]*W for i in range(H)]  # V[h][w]を頂点iとする
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    # グループ分け
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    # グラフを作成、全てのマスで5*5の範囲を走査
    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

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

    # for i in range(vertex):
    #     print(G[i])

    # スタートからゴールまでbfsして最短距離を求める
    s = V[Ch][Cw]
    g = V[Dh][Dw]
    que = deque([0])

    dist = [-1 for _ in range(vertex)]
    par = [-1]*vertex
    que = deque()
    dist[s] = 0
    par[s] = -2  # rootは親なし
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if par[v] != -1:
                continue
            par[v] = u
            dist[v] = dist[u] + 1
            que.append(v)
    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


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)]
    V = [[-1]*W for i in range(H)]  # V[h][w]を頂点iとする
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    # グループ分け
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    # グラフを作成、全てのマスで5*5の範囲を走査
    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

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

    # for i in range(vertex):
    #     print(G[i])

    # スタートからゴールまでbfsして最短距離を求める
    s = V[Ch][Cw]
    g = V[Dh][Dw]
    que = deque([0])

    dist = [-1 for _ in range(vertex)]
    par = [-1]*vertex
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if par[v] != -1:
                continue
            par[v] = u
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


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

Submission status: Accepted

Solution code:
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)]
    V = [[-1]*W for i in range(H)]  # V[h][w]を頂点iとする
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    # グループ分け
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    # グラフを作成、全てのマスで5*5の範囲を走査
    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

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

    # for i in range(vertex):
    #     print(G[i])

    # スタートからゴールまでbfsして最短距離を求める
    s = V[Ch][Cw]
    g = V[Dh][Dw]
    que = deque([0])

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
INF = 1e7
def main():
    H,W=map(int, input().split())
    sx, sy = map(int, input().split())
    dh, dw = map(int, input().split())
    sx -= 1
    sy -= 1
    S = [input() for _ in range(H)]
    def dijkstra(sx, sy):
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        D[sx][sy] = 0
        PQ = [(0, (sx, sy))]
        heapq.heapify(PQ)
        while PQ: # PQに候補がある限り
            _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if abs(dx) + abs(dy) == 1:
                            if D[ux][uy] < D[xx][yy]:
                                D[xx][yy] = D[ux][uy]
                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
                        else:
                            if D[ux][uy] + 1 < D[xx][yy]:
                                D[xx][yy] = D[ux][uy] + 1
                                heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
        return D
    D = dijkstra(sx, sy)
    if D[dh-1][dw-1] >= INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])
main()

Submission status: Accepted

Solution code:
import heapq
INF = 1e7
def main():
    H,W=map(int, input().split())
    sx, sy = map(int, input().split())
    dh, dw = map(int, input().split())
    sx -= 1
    sy -= 1
    S = [input() for _ in range(H)]
    def dijkstra(sx, sy):
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        D[sx][sy] = 0
        PQ = [(0, (sx, sy))]
        heapq.heapify(PQ)
        while PQ: # PQに候補がある限り
            _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                            D[xx][yy] = D[ux][uy] + is_not_neighbor
                            heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
        return D
    D = dijkstra(sx, sy)
    if D[dh-1][dw-1] >= INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])
main()

Submission status: Accepted

Solution code:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
def dijkstra(sx, sy):
    D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
    D[sx][sy] = 0
    PQ = [(0, (sx, sy))]
    heapq.heapify(PQ)
    while PQ: # PQに候補がある限り
        _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx, yy = ux+dx, uy+dy
                if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                    is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                    # neighborでなければコストが1増える
                    if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                        D[xx][yy] = D[ux][uy] + is_not_neighbor
                        heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
    return D
D = dijkstra(sx, sy)
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Submission status: Accepted

Solution code:
#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        for k,l in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
            if 0<=k<h and 0<=l<w:
                if dp[k][l]!=-1:
                    if dp[k][l]>dp[i][j]:
                        dp[k][l]=dp[i][j]
                        now.appendleft([k,l])
        for k in range(i-2,i+3):
            for l in range(j-2,j+3):
                if 0<=k<h and 0<=l<w:
                    if dp[k][l]!=-1:
                        if dp[k][l]>dp[i][j]+1:
                            dp[k][l]=dp[i][j]+1
                            now.append([k,l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Accepted

Solution code:
import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    C = NLI()
    D = NLI()
    C = [x-1 for x in C]
    D = [x-1 for x in D]
    grid = [SI() for _ in range(H)]

    que = deque()
    cost = [[10**10]*W for _ in range(H)]
    cost[C[0]][C[1]] = 0
    que.append(C)
    while que:
        now = que.popleft()
        now_cost = cost[now[0]][now[1]]

        for i in range(-2, 3):
            if now[0] + i < 0 or now[0] + i >= H:
                continue
            for j in range(-2, 3):
                if now[1]+j < 0 or now[1]+j >= W:
                    continue
                if i == j == 0:
                    continue
                goto = [now[0]+i, now[1]+j]
                goto_cost = cost[goto[0]][goto[1]]
                if grid[goto[0]][goto[1]] == "#":
                    continue

                dist = abs(goto[0]-now[0]) + abs(goto[1]-now[1])
                if dist == 1:
                    if now_cost < goto_cost:
                        cost[goto[0]][goto[1]] = now_cost
                        que.appendleft(goto)
                else:
                    if now_cost + 1 < goto_cost:
                        cost[goto[0]][goto[1]] = now_cost + 1
                        que.append(goto)

    ans = cost[D[0]][D[1]]
    print(ans if ans < 10**10 else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import deque
def resolve():
    drc4 = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

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

    INF = 10 ** 12
    dist = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx))
    dist[sy][sx] = 0
    cnt = 0
    while True:
        next_warp = []
        while q:
            sy, sx = q.popleft()
            next_warp.append((sy, sx))
            for dy, dx in drc4:
                ny = dy + sy
                nx = dx + sx
                if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and dist[ny][nx] == INF:
                    dist[ny][nx] = cnt
                    q.append((ny, nx))

        for sy, sx in next_warp:
            for dy8, dx8 in warp:
                ny8 = dy8 + sy
                nx8 = dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and dist[ny8][nx8] == INF:
                    dist[ny8][nx8] = cnt + 1
                    q.append((ny8, nx8))

        if not q or dist[gy][gx] != INF:
            break
        cnt += 1

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

# 迷路読み込み
H,W = map(int, input().split())
c1,c2= map(int, input().split())
d1,d2= map(int, input().split())
A=[list(input()) for i in range(H)]
edges = [[] for i in range(H * W)]

for i in range(H):
    for j in range(W):
        for di in range(-2,3):
            for dj in range(-2, 3):
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and A[i][j]!='#' and A[ni][nj]!='#':
                    if di==0 and dj==0:
                        continue
                    elif (di==0 and dj==1) or (di==1 and dj==0) or (di==-1 and dj==0) or (di==0 and dj==-1):
                        edges[i * W + j].append((ni * W + nj,0))
                    else:
                        edges[i * W + j].append((ni * W + nj,1))

s=(c1-1)*W+c2-1
g=(d1-1)*W+d2-1
dist = [10**9]*(H*W)
dist[s] = 0
que = deque()
que.append(s)

while len(que) > 0:
    i = que.popleft()
    for j, c in edges[i]:
        d = dist[i] + c
        if d < dist[j]:
            dist[j] = d
            if c == 1:
                que.append(j)
            else:
                que.appendleft(j)


ans=dist[g]
if ans==pow(10,9):
    print(-1)
else:
    print(ans)