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:
## 01BFSで解く
from collections import deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())
fs = [input() for i in range(H)]

INF = float("inf")
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.append((0, (ch-1)*N+(cw-1)))
while q:
    cnt, n  = q.popleft()
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw
            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] < INF:continue
            if abs(dh) + abs(dw) <= 1:
                q.appendleft((cnt, hn*N+wn))
            else:
                q.append((cnt+1, hn*N+wn))
# for r in dps:
#     print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

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

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

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny = dy + sy
            nx = dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                # q.appendleft 使用
                q.appendleft((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8 = dy8 + sy
            nx8 = dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                # q.appendleft 使用しない
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

from collections import deque
INF = float('inf')
dist = [[INF]*W for _ in range(H)]
dist[sy][sx] = 0
q = deque([(sx,sy)])
while q:
    x,y = q.popleft()
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '#': continue
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                q.appendleft((nx,ny))
                dist[ny][nx] = dist[y][x]
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                q.append((nx,ny))
                dist[ny][nx] = dist[y][x] + 1

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

Submission status: Accepted

Solution code:

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))


while q:
    u, v = q.popleft()
    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if (0 <= u + i < H and 0 <= v + j < W
                and X[u + i][v + j] == "."
                and dist[u + i][v + j] > dist[u][v]):
            dist[u + i][v + j] = dist[u][v]
            q.appendleft((u + i, v + j))

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

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)

Submission status: Accepted

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

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

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#BFS
visited = [[False] * W for _ in range(H)]
willSearch = [[False] * W for _ in range(H)]
Q = deque()
QN = deque()
Q.append((0,Ch,Cw))
QN.append((0,Ch,Cw))
while Q:
  while Q:
    c,x,y = Q.popleft()
    if visited[x][y]:
      continue
    visited[x][y] = True
    QN.append((c,x,y))
    #print(c,x,y)
    if x == Dh and y == Dw:
      print(c)
      exit(0)
    for dx,dy in dpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c,nx,ny))
        QN.append((c,nx,ny))
        willSearch[nx][ny] = True
  while QN:
    c,x,y = QN.popleft()
    for dx,dy in mpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c+1,nx,ny))
        #print("m", c+1, nx,ny)
        #willSearch[nx][ny] = True
      
print(-1)

Submission status: Accepted

Solution code:

from collections import deque
def resolve():
    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())
    maze = [input() for _ in range(H)]

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

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(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)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else -1
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
## 01BFS
## 2値の場合、priority queueみたいなのを工夫して計算量を落とせる
# 0の場合 : 先頭に値を追加 appendleft
# 1の場合 : 後方に値を追加 append
# 常に先頭から取り出す pop
# ※queueを２つ用いても良い

from collections import deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

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

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft(((ch-1)*INF+(cw-1),0))
while len(q)>0:
    n,cnt = q.popleft()
    h,w = divmod(n, INF)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn*INF+wn, cnt))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn*INF+wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections
import itertools
 
def main():
    input = sys.stdin.readline
    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().rstrip()) for _ in range(h)]
    
    que = collections.deque()
    que.append((ch, cw))
    cost = [[float("INF")] * w for _ in range(h)]
    cost[ch][cw] = 0
    
    while que:
        py, px = que.popleft()
        for dy, dx in itertools.product(range(-2, 3), repeat = 2):
            ny, nx = py + dy, px + dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
                if dy == dx == 0:
                    continue
                if (dy, dx) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    if cost[ny][nx] > cost[py][px]:
                        cost[ny][nx] = cost[py][px]
                        que.appendleft((ny, nx))
                else:
                    if cost[ny][nx] > cost[py][px] + 1:
                        cost[ny][nx] = cost[py][px] + 1
                        que.append((ny, nx))
                        
    if cost[dh][dw] == float("INF"):
        print(-1)
    else:
        print(cost[dh][dw])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]
dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

q = deque([(ch, cw)])
dist[ch][cw] = 0
while q:
    y, x = q.popleft()
    for dy, dx in dwalk:
        py = y+dy; px = x+dx
        if not 0<=py<h: continue
        if not 0<=px<w: continue
        if area[py][px]=='#': continue
        if dist[py][px]>dist[y][x]:
            dist[py][px] = dist[y][x]
            q.appendleft((py, px))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            py = y+dy; px = x+dx
            if not 0<=py<h: continue
            if not 0<=px<w: continue
            if area[py][px]=='#': continue
            if dist[py][px]>dist[y][x]+1:
                dist[py][px] = dist[y][x]+1
                q.append((py, px))

if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)

H,W = map(int,input().split())
curX,curY = map(int,input().split())
curX -= 1
curY -= 1
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = [ list(input()) for _ in range(H) ]
q = deque([(curX,curY)])
dist = [ [float('inf')]*W for _ in range(H) ]
dist[curX][curY] = 0

while q:
  r,c = q.popleft()
  if r==goalX and c==goalY: break
  hop = dist[r][c]

  # if be able to move 1 step
  for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
    nr,nc = r+x,c+y
    if 0<=nr<H and 0<=nc<W and graph[nr][nc]!="#" and dist[nr][nc]>hop:
      dist[nr][nc] = hop
      q.appendleft((nr,nc))

  for i in range(-2, 3):
    for j in range(-2, 3):
      nr,nc = r+i,c+j
      if 0<=nr<H and 0<=nc<W and graph[nr][nc]!="#" and dist[nr][nc]>hop+1:
        dist[nr][nc] = hop+1
        q.append((nr,nc))

ans = dist[goalX][goalY]
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections
import itertools

def main():
    input = sys.stdin.readline
    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().rstrip()) for _ in range(h)]
    
    que = collections.deque()
    que.append((ch, cw))
    cost = [[float("INF")] * w for _ in range(h)]
    cost[ch][cw] = 0
    
    while que:
        py, px = que.popleft()
        for dy, dx in itertools.product(range(-2, 3), repeat = 2):
            ny, nx = py + dy, px + dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
                if dy == dx == 0:
                    continue
                if (dy, dx) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    if cost[ny][nx] > cost[py][px]:
                        cost[ny][nx] = cost[py][px]
                        que.appendleft((ny, nx))
                else:
                    if cost[ny][nx] > cost[py][px] + 1:
                        cost[ny][nx] = cost[py][px] + 1
                        que.append((ny, nx))
                        
    if cost[dh][dw] == float("INF"):
        print(-1)
    else:
        print(cost[dh][dw])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

"""
ダイクストラ　ギリギリ
"""
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

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

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        # この枝刈がないと通らない
        if dist[y][x] < cost: continue
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque
import sys
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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

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

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        if dist[y][x] < cost: continue
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

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

squares = []
for i in range(H):
    squares.append([None]*(W))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            squares[i][j] = -1  # Wall

squares[Ch][Cw]=0

d1 = deque()
d2 = deque()
d1.append([Ch, Cw])

warps = 0

def visit(i1, j1, i2, j2, with_warp = False):  # (i1,j1) to (i2,j2)
    if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
        return
    sq2 = squares[i2][j2]
    if sq2 == None:
        if with_warp:
            squares[i2][j2] = warps + 1  # sq2 = warps + 1 <- doesn't work
        else:
            squares[i2][j2] = warps  # sq2 = warps <- doesn't work
        d1.append([i2, j2])
        if i2 == Dh and j2 == Dw:
            print(squares[i2][j2])
            exit()

while (len(d1)>0):
    while (len(d1)>0):
        src = d1.popleft()
        visit(src[0], src[1], src[0] - 1, src[1])
        visit(src[0], src[1], src[0] + 1, src[1])
        visit(src[0], src[1], src[0], src[1] - 1)
        visit(src[0], src[1], src[0], src[1] + 1)
        d2.append(src)

    while (len(d2)>0):
        src = d2.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                visit(src[0], src[1], src[0]+i, src[1]+j, True)

    warps += 1

print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

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())
maze = [list(input()) for _ in range(H)] # 迷路
walkFrom = deque([(Ch, Cw)]) # 歩く出発地点の候補集
warpFrom = deque() # ワープ出発地点の候補集
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: not x in WalkRange + [(0, 0)], product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h_dist, w_dist in moveRange:
    h_to, w_to = h_from + h_dist, w_from + w_dist
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))

# 迷路上の到達可能な全ての場所について、道(".")を必要なワープ回数で上書きする
maze[Ch][Cw] = warpCount
while walkFrom:
  # 歩ける範囲をすべて歩く
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  # 一度のワープで到達できる未踏の場所すべてにワープする
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '#'] else print(goal)

Submission status: Accepted

Solution code:
from collections import deque


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

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

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

walk = [(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)] + walk]

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

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())
maze = [list(input()) for _ in range(H)] # 迷路
walkFrom = deque([(Ch, Cw)]) # 歩く出発地点の候補集
warpFrom = deque() # ワープ出発地点の候補集
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h_dist, w_dist in moveRange:
    h_to, w_to = h_from + h_dist, w_from + w_dist
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))

# 迷路上の到達可能な全ての場所について、道(".")を必要なワープ回数で上書きする
maze[Ch][Cw] = warpCount
while walkFrom:
  # 歩ける範囲をすべて歩く
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  # 一度のワープで到達できる未踏の場所すべてにワープする
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '#'] else print(goal)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    h, w = rl()
    starth, startw = rl()
    endh, endw = rl()
    maze = []
    for i in range(h):
        maze.append(list(input()))

    def nbrs(x, y):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                yield (nx, ny)

    def magic(x, y):
        for nx in range(x - 2, x + 3):
            for ny in range(y - 2, y + 3):
                if nx == x and ny == y: continue
                if 0 <= nx and nx < h and 0 <= ny and ny < w:
                    yield (nx, ny)


    bridges = dd(set)
    def dfs(x, y, num):
        if maze[x][y] != '.':
            return
        else:
            maze[x][y] = num
            for nx, ny in magic(x, y):
                if maze[nx][ny] not in ['.', '#', num]:
                    bridges[num].add(maze[nx][ny])
                    bridges[maze[nx][ny]].add(num)
            for nx, ny in nbrs(x, y):
                dfs(nx, ny, num)

    num = 0
    for x in range(h):
        for y in range(w):
            if maze[x][y] == ".":
                dfs(x, y, num)
                num += 1
   
    curr = [maze[starth-1][startw-1]]
    goal = maze[endh-1][endw-1]
    if curr[0] == goal:
        print (0)
        return

    seen = set(curr)
    depth = 0
    while curr:
        ring = []
        depth += 1
        for node in curr:
            for nxt in bridges[node]:
                if nxt not in seen:
                    if nxt == goal:
                        print (depth)
                        return
                    seen.add(nxt)
                    ring.append(nxt)
        curr = ring

    print (-1)



mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

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())
maze = [list(input()) for _ in range(H)]
walkFrom = deque([(Ch, Cw)]) # 歩く出発地点の候補集
warpFrom = deque() # ワープ出発地点の候補集
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h, w in moveRange:
    h_to, w_to = h_from + h, w_from + w
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


while walkFrom:
  # 歩ける範囲をすべて歩く
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  # ワープする
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '#'] else print(goal)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

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())
maze = [list(input()) for _ in range(H)]
walkFrom = deque([(Ch, Cw)]) # 歩く出発地点の候補集
warpFrom = deque() # ワープ出発地点の候補集
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h, w in moveRange:
    h_to, w_to = h_from + h, w_from + w
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


while walkFrom:
  # 歩ける範囲をすべて歩く
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  # ワープする
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print(goal) if not goal in ['.', '#'] else print('-1')

Submission status: Accepted

Solution code:
#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 
#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:#qがある間の遷移 BSF
    visit = [] #徒歩で動いたところをメモする
    while q:#徒歩用のq
        nh,nw = q.popleft()
        visit.append((nh,nw))
        #徒歩での遷移
        move = [(-1,0),(1,0),(0,-1),(0,1)]
        for ih,iw in move:
            if  (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                    q.append((nh+ih,nw+iw))
                    dp[nh+ih][nw+iw] = dp[nh][nw]
    while visit:#徒歩で訪れたところからワープ先を探す
    #ワープで遷移
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
import copy

from collections import deque
 
H, W = [int(x) for x in input().split()]

Ch,Cw = map(int,input().split())

Ch,Cw = Ch-1,Cw-1

Dh,Dw = map(int,input().split())

Dh,Dw = Dh-1,Dw-1

cell = [list(input()) for i in range(H)]

dp = [[-1]*W for _ in range(H)]

copy_stack = []
copy_stack.append([Ch,Cw])

nstack = []

dp[Ch][Cw] = 0

def search(stack):
    while len(stack) > 0:
        h,w = stack.pop()
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
                if cell[nh][nw] == '.':
                    dp[nh][nw] = dp[h][w]
                    stack.append([nh,nw])
                    copy_stack.append([nh,nw])
                   
while True:
    if len(copy_stack):
        nstack = copy.copy(copy_stack)
    else:
        copy_stack = copy.copy(nstack)
    search(nstack)
    #print(dp)
    if dp[Dh][Dw] == -1:
        while len(copy_stack)>0:
            h,w = copy_stack.pop()
            for ddy in range(-2,3):
                for ddx in range(-2,3):
                    if ddy==ddx==0:
                        continue
                    nnh = h + ddy
                    nnw = w + ddx
                    if 0 <= nnh < H and 0 <= nnw < W:
                        if cell[nnh][nnw] == '.' and dp[nnh][nnw] == -1:
                            dp[nnh][nnw] = dp[h][w] + 1
                            nstack.append([nnh,nnw])
        if len(nstack) == 0:
            break
    else:
        break
                        
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)