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
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))


def main():
    H, W = map(int, readline().split())
    Ch, Cw = map(int, readline().split())
    Dh, Dw = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    seen = [[False] * W for _ in range(H)]
    queue = deque([(Ch, Cw)])
    while queue:
        x, y = queue.popleft()
        seen[x][y] = True
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if (
                0 <= nx < H
                and 0 <= ny < W
                and not seen[nx][ny]
                and (dist[nx][ny] == -1 or dist[nx][ny] > dist[x][y])
                and S[nx][ny] == '.'
            ):
                dist[nx][ny] = dist[x][y]
                queue.appendleft((nx, ny))
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if (
                    0 <= nx < H
                    and 0 <= ny < W
                    and not seen[nx][ny]
                    and dist[nx][ny] > dist[x][y] + 1
                    and S[nx][ny] == '.'
                ):
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque
def main():
    H,W = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    field = [input() for _ in range(H)]

    wmap = [[-1] * W for _ in range(H)]
    wmap[start[0]-1][start[1]-1] = 0

    d = deque()
    d.appendleft((start[1]-1,start[0]-1))

    warpd = d.copy()

    def flood():
        while len(d) > 0:
            pos = d.pop()
            warpd.append(pos)
            posx, posy = pos
            w = wmap[posy][posx]
            for x,y in [(posx-1, posy), (posx+1, posy), (posx, posy-1), (posx, posy+1)]:
                if 0 <= x < W and 0 <= y < H and field[y][x] == "." and wmap[y][x] == -1:
                    wmap[y][x] = w
                    d.appendleft((x,y))
                    warpd.append((x,y))

    # くばる
    def warp():
        movable = set()
        while len(warpd) > 0:
            x,y = warpd.pop()
            w = wmap[y][x]
            
            for my in range(-2, 3):
                for mx in range(-2, 3):
                    px = x + mx
                    py = y + my
                    if 0 <= px < W and 0 <= py < H and field[py][px] == "." and wmap[py][px] == -1:
                        wmap[py][px] = w+1
                        movable.add((px,py))

        for item in movable:
            d.append(item)

    while len(d) != 0 and wmap[goal[0]-1][goal[1]-1] == -1:
        flood()
        warp()

    print(wmap[goal[0]-1][goal[1]-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split()); base = 1000
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
visit = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = []
Q.append((0,C[0]+C[1]*base))
while Q:
  score,z = heappop(Q)
  x = z%base;y=z//base
  if visit[x][y]:
    continue
  visit[x][y] = True
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = nx+ny*base
      heappush(Q,(score,u))
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = mx+my*base
      #print(v,p,"X")
      heappush(Q,(score+1,p))
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
    i, j, cnt = Q.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = cnt
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i + di < h and 0 <= j + \
                    dj < w and S[i + di][j + dj] == "." and D[i + di][j + dj] == -1:
                if abs(di) + abs(dj) == 1:
                    Q.appendleft((i + di, j + dj, cnt))
                else:
                    Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1

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

que = deque([(0,ch,cw)])
while que:
    d,i,j = que.popleft()
    if (i,j) == (dh,dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for cdi,cdj in coordinates:
        ni,nj = i + cdi, j + cdj
        if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.':
            que.appendleft((d,ni,nj))
    for di in range(-2,3):
        for dj in range(-2,3):
            if di == dj == 0:
                continue
            ni,nj = i+di,j+dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and not visited[ni][nj]:
                que.append((d+1,ni,nj))
print(-1)

Submission status: Accepted

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

from collections import deque

q = deque([])
q.append([sy, sx, 0])

mx=[0,0,1,-1]
my=[1,-1,0,0]

vis = [[-1]*w for i in range(h)]
vis[sy][sx]=0

while len(q)>0:
  y, x, c = q.popleft()

  for i in range(4):
    nx=x+mx[i]
    ny=y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and (vis[ny][nx]>c or vis[ny][nx]==-1):
      vis[ny][nx]=c
      q.appendleft([ny,nx,c])
  
  for xi in range(5):
    for yi in range(5):
      nx=x+xi-2
      ny=y+yi-2    
      if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]==-1:
        vis[ny][nx]=c+1
        q.append([ny,nx,c+1])
print(vis[gy][gx])

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
 
 
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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
cx-=1;cy-=1;dx-=1;dy-=1
B = []
for _ in range(H):
    B.append(input().strip())

D = [0]*(H*W)
bb = -1
t = 0
t2c = dict()
for i in range(H):
    for j in range(W):
        if B[i][j] == "#":
            D[i*W+j] = bb
            continue
        if D[i*W+j]>0:
            continue
        t += 1
        t2c[t] = set()
        stack = [(i, j)]
        while stack:
            u, v = stack.pop()
            D[W*u+v] = t
            t2c[t].add((u, v))
            for x, y in [(u+1, v), (u-1, v), (u, v-1), (u, v+1)]:
                if x >= H or x<0:
                    continue
                if y >= W or y<0:
                    continue
                if B[x][y] == "#":
                    D[x*W+y] = bb
                    continue
                if D[x*W+y]:
                    continue
                stack.append((x, y))
depth = 0
cs = [D[cx*W+cy]]
tt = D[dx*W+dy]
vs = set([cs[0], -1])
if tt in vs:
    print(0)
    sys.exit()
while True:
    depth += 1
    nexts = []
    for c in cs:
        for i, j in t2c[c]:
            for ii in range(max(0, i-2), min(i+3, H)):
                for jj in range(max(0, j-2), min(j+3, W)):
                    if D[ii*W+jj] in vs:
                        continue
                    vs.add(D[ii*W+jj])
                    nexts.append(D[ii*W+jj])
                    if D[ii*W+jj] == tt:
                        print(depth)
                        sys.exit()
    cs = nexts
    if not cs:
        break
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
 
 
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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        if [nowh,noww]==[Dh,Dw]:
            print(s2[nowh][noww])
            exit()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '#':
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    print(-1)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

sy,sx = map(int,readline().split())
gy,gx = map(int,readline().split())

sy -= 1
sx -= 1
gy -= 1
gx -= 1

G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

# 幅優先探索
INF = 10 ** 10
costs = [[INF] * W for i in range(H)]

from collections import deque
q = deque([])
# y,x,魔法の回数,親y,親x
q.append((sy,sx,0))

cases = {(0,1),(0,-1),(1,0),(-1,0)}
while q:
  y,x,co = q.popleft()
  if costs[y][x] <= co:
    continue
  if G[y][x] == "#":
    continue
  costs[y][x] = co
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if G[y + c[0]][x + c[1]] == "#":
        continue
      if costs[y + c[0]][x + c[1]] <= co:
        continue
      q.appendleft((y + c[0], x + c[1], co))
  for i in range(-2,3):
    for j in range(-2,3):
      if (i,j) in cases or (i,j) == (0,0):
        continue
      if 0 <= y + i < H and 0 <= x + j < W:
        if G[y + i][x + j] == "#":
          continue
        if costs[y + i][x + j] <= co + 1:
          continue
        q.append((y + i, x + j, co + 1))

if costs[gy][gx] == INF:
  print(-1)
else:
  print(costs[gy][gx])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
#幅優先探索 BFS
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()]

S = [input() for i in range(H)]
cost = [[-1]*W for i in range(H)]

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

ans = -1
while(q):
    cnt, cx, cy = q.popleft()
    if cost[cx][cy]<0:
        cost[cx][cy]=cnt
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=cx+dx<H and 0<=cy+dy<W and S[cx+dx][cy+dy]=='.':
                    if cost[cx+dx][cy+dy]<0:
                        if [dx,dy] in [[1,0],[-1,0],[0,1],[0,-1]]:
                            q.appendleft([cnt,cx+dx,cy+dy])
                        else:
                            q.append([cnt+1,cx+dx,cy+dy])

print(cost[dh][dw])

Submission status: Accepted

Solution code:
import queue

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
#c->d

s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()#start point of each domain

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while (not q.empty()) and distance[dh][dw]==10**7:
  sth,stw=q.get()
  qi=queue.Queue()#BFS
  qi.put([sth,stw])
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]!=1:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]=="." and seen[warph][warpw]==0:
        q.put([warph,warpw])
        seen[warph][warpw]=2
        distance[warph][warpw]=distance[i][j]+1



if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = deque()
q.append((0, Ch*W+Cw))

while q:
    d, ij = q.popleft()
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di
            J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    q.appendleft((d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    q.append((d+1, I*W+J))
ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
S = [list(input()) for _ in range(h)]

from collections import deque
# 座標, 座標, ワープカウント
q = deque([[ch, cw, 0]])
wall = deque()
visited = [[-1] * w for _ in range(h)]
visited[ch][cw] = 0
ans = -2
while True:
    # つながっているエリアを探索
    while q:
        i, j, wc = q.popleft()
        if i == dh and j == dw:
            ans = wc
            break
        next_to_wall = False
        for mi, mj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = i + mi, j + mj

            if 0 <= nj < w and 0 <= ni < h:
                if S[ni][nj] == '.' and visited[ni][nj] != wc:
                    visited[ni][nj] = wc
                    q.append([ni, nj, wc])
                elif S[ni][nj] == '#':
                    next_to_wall = True
        if next_to_wall:
            wall.append([i, j, wc])
    else:
        # 飛ぶ場所がなかったら終了
        if not wall:
            ans = -1
    if ans > -2:
        break

    while wall:
        i, j, wc = wall.popleft()
        for wi, wj in ((-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)):
            ni, nj = i+wi, j+wj
            if (0 <= nj < w and 0 <= ni < h and S[ni][nj] == '.' and
                (visited[ni][nj] == -1 or visited[ni][nj] > wc+1)):
                visited[ni][nj] = wc+1
                q.append([ni, nj, wc+1])
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
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 TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	S[ch][cw]=0
	Q=deque()
	Q.append([0,ch,cw])


	d1=[(0,1),(0,-1),(-1,0),(1,0)]
	d2=[(i,j) for i in range(-2,3) for j in range(-2,3)]

	while Q:
		#print(Q)
		d,x,y=Q.popleft()

		for xx,yy in d1:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])

		for xx,yy in d2:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d+1
				Q.append([d+1,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d+1:
				S[x+xx][y+yy]=d+1
				Q.appendleft([d+1,x+xx,y+yy])



	#print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque
import itertools


def bfs():
    H, W = map(int, input().split())
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]

    tests = (0, 1), (1, 0), (-1, 0), (0, -1)
    # warps = itertools.product(range(-2, 3), range(-2, 3))

    start = (0, C[0] - 1, C[1] - 1)
    goal = (D[0] - 1, D[1] - 1)

    queue = deque()
    # (ワープ回数, x, y)
    queue.append(start)

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

        # 通常移動
        for dx, dy in tests:
            nx = x + dx
            ny = y + dy

            if not (0 <= nx < H):
                continue

            if not (0 <= ny < W):
                continue

            if S[nx][ny] != "#":
                if S[nx][ny] != "." and w_n >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n
                    queue.appendleft((w_n, nx, ny))

        # warp
        for dx, dy in itertools.product(range(-2, 3), range(-2, 3)):
            nx = x + dx
            ny = y + dy

            if not (0 <= nx < H):
                continue

            if not (0 <= ny < W):
                continue

            if S[nx][ny] != "#":
                if S[nx][ny] != "." and w_n + 1 >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n + 1
                    queue.append((w_n + 1, nx, ny))

    if S[goal[0]][goal[1]] == ".":
        print(-1)
    else:
        print(S[goal[0]][goal[1]])


bfs()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))


def main():
    H, W = map(int, readline().split())
    Ch, Cw = map(int, readline().split())
    Dh, Dw = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    dist = [[-1] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    queue = deque([(Ch, Cw)])
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if (
                0 <= nx < H
                and 0 <= ny < W
                and (dist[nx][ny] == -1 or dist[nx][ny] > dist[x][y])
                and S[nx][ny] == '.'
            ):
                dist[nx][ny] = dist[x][y]
                queue.appendleft((nx, ny))
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and S[nx][ny] == '.':
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))

    print(dist[Dh][Dw])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
#from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import heapq
def dijkstra(start, end):
	#dist = defaultdict(lambda: float('inf'))
	dist = [[float('inf')]*W for _ in range(H)]
	dist[start[0]][start[1]] = 0
	heap = []
	heapq.heappush(heap, (0, start))
	while heap:
		d, n = heapq.heappop(heap)
		if n == end:
			return d
		if dist[n[0]][n[1]] != d:
			continue
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			ni, nj = nn
			if dist[ni][nj] > nd:
				dist[ni][nj] = nd
				heapq.heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '#': return edges
	for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '#': continue
		edges.append(((ni, nj), 0))
	for di in range(-2, +3):
		for dj in range(-2, +3):
			ni, nj = i+di, j+dj
			if di == 0 and dj == 0: continue
			if (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				continue
			if not(0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			edges.append(((ni, nj), 1))
	return edges

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])
d = dijkstra(start, end)
print(d)

Submission status: Accepted

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

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 0

while 1:
    while stack1:
        sh, sw = stack1.pop()
        stack2.append((sh, sw))
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                if nh == Dh and nw == Dw:
                    print(answer)
                    exit()
                grid[nh][nw] = 1
                stack1.append((nh, nw))
    answer += 1

    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                    if nh == Dh and nw == Dw:
                        print(answer)
                        exit()
                    grid[nh][nw] = 1
                    stack1.append((nh, nw))
    if not stack1:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-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, 1), (0, 2), 
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if (wh, ww) in directions:
                if S[h+wh][w+ww] > S[h][w]:
                    S[h+wh][w+ww] = S[h][w]
                    q.appendleft((h+wh, w+ww))
            else:
                if S[h+wh][w+ww] > S[h][w] + 1:
                    S[h+wh][w+ww] = S[h][w] + 1
                    q.append((h+wh, w+ww))

if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(w+2) for _ in range(h+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.pop()
    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, (ch-1)*(10**4)+cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, yx = heappop(Q)
    y, x = divmod(yx, 10**4)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    dist[ny][nx] = d
                    heappush(Q, (d, ny*(10**4)+nx))
            else:
                if dist[ny][nx]>d+1:
                    dist[ny][nx] = d+1
                    heappush(Q, (d+1, ny*(10**4)+nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)