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: Time Limit Exceeded

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=[[-1]*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()
    if v[h][w]<0:
        v[h][w]=d
    for i,j in x:
        if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=='.' and v[h+i][w+j]<0:
            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 v[h+i][w+j]<0:
            q.append((h+i,w+j,d+1))
print(v[dh-1][dw-1])

Submission status: Time Limit Exceeded

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
Q = deque([(ch-1, cw-1)])

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
while Q:
    y, x = Q.popleft()
    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]>dist[y][x]:
                    dist[ny][nx] = dist[y][x]
                    Q.append((ny, nx))
            else:
                if dist[ny][nx]>dist[y][x]+1:
                    dist[ny][nx] = dist[y][x]+1
                    Q.append((ny, nx))
if dist[dh-1][dw-1]>=10**17:
    print(-1)
else:
    print(dist[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
          q.put([hh, ww])
          T[hh][ww] = k
      for i in range(-2, 3):
        for j in range(-2, 3):
          hh = h + i
          ww = w + j
          if hh < 0: continue
          if hh > H: continue
          if ww < 0: continue
          if ww > W:continue
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            T[hh][ww] = k + 1

    return T, k


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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                        if (dh, dw) in move:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
c1, c2 = map(int, input().split())
d1, d2 = map(int, input().split())
c1 += 1
c2 += 1
d1 += 1
d2 += 1
S = ["#"*(W+4)]*2 + ["##"+input()+"##" for _ in range(H)] + ["#"*(W+4)]*2

ans = [[10000000]*(W+4) for _ in range(H+4)]
ans[c1][c2] = 0
q = deque([[c1, c2]])

x = [[-1, 0], [0, -1], [0, 1], [1, 0]]

while q:
    h, w = q.popleft()
    
    for a, b in x:
        nh = h+a
        nw = w+b
        if S[nh][nw] == ".":
            if ans[nh][nw] > ans[h][w]:
                ans[nh][nw] = ans[h][w]
                q.appendleft([nh, nw])
    
    for a in range(-2, 3):
        for b in range(-2, 3):
            nh = h+a
            nw = w+b
            if S[nh][nw] == ".":
                if ans[nh][nw] > ans[h][w]+1:
                    ans[nh][nw] = ans[h][w]+1
                    q.append([nh, nw])

if ans[d1][d2] == 10000000:
    print(-1)
else:
    print(ans[d1][d2])

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj))
        for ni in range(i - 2, i + 2 + 1, 1):
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                    if dist[ni][nj] > d + 1:
                        dist[ni][nj] = d + 1
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    H, W = read_values()
    C = tuple(read_index())
    D = tuple(read_index())
    S = [input().strip() for _ in range(H)]

    F = [10 ** 10] * (H * W)

    Q = [(0, C)]
    F[C[0] * W + C[1]] = 0
    while Q:
        c, (h, w) = heapq.heappop(Q)
        if (h, w) == D:
            print(c)
            return

        if F[h * W + w] > c:
            continue
        for d in (1, -1):
            if 0 <= w + d < W and S[h][w + d] == "." and F[h * W + w + d] > c:
                F[h * W + w + d] = c
                heapq.heappush(Q, (c, (h, w + d)))
            if 0 <= h + d < H and S[h + d][w] == "." and F[(h + d) * W + w] > c:
                F[(h + d) * W + w] = c
                heapq.heappush(Q, (c, (h + d, w)))
        
        for hh in range(h - 2, h + 3):
            for ww in range(w - 2, w + 3):
                if 0 <= ww < W and 0 <= hh < H and S[hh][ww] == "." and F[hh * W + ww] > c:
                    F[hh * W + ww] = c + 1
                    heapq.heappush(Q, (c + 1, (hh, ww)))
    
    print(-1)
            

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh, dw in move:
                if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                    heappush(q, (dist, h+dh, w+dw))
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                        heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = lambda: sys.stdin.readline().rstrip()
  from heapq import heappop,heappush
  h,w=map(int,input().split())
  n=h*w
  hw=lambda hh,ww:hh*w+ww
  ch,cw=map(int,input().split())
  s=hw(ch-1,cw-1)
  dh,dw=map(int,input().split())
  g=hw(dh-1,dw-1)
  b=[list(input())for _ in range(h)]
  edge=[[]for _ in range(h*w)]
  for i in range(h):
    for j in range(w):
      if b[i][j]=="#":continue
      if i!=h-1:
        if b[i+1][j]==".":
          edge[hw(i,j)].append((hw(i+1,j),0))
          edge[hw(i+1,j)].append((hw(i,j),0))
      if j!=w-1:
        if b[i][j+1]==".":
          edge[hw(i,j)].append((hw(i,j+1),0))
          edge[hw(i,j+1)].append((hw(i,j),0))
      for ii in range(max(0,i-2),min(h,i+3)):
        for jj in range(max(0,j-2),min(w,j+3)):
          if i==ii and j==jj:continue
          if b[ii][jj]==".":
            edge[hw(i,j)].append((hw(ii,jj),1))
  inf = 10**20
  ans = [inf]*n
  ans[s] = 0
  hh = [(0, s)]
  while hh:
    c, v = heappop(hh)
    if ans[v] < c:
      continue
    for u, t in edge[v]:
      if c+t < ans[u]:
        ans[u] = c+t
        heappush(hh, (c+t, u))
  if ans[g]==10**20:ans[g]=-1
  print(ans[g])
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

H,W=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=[[1<<30]*W for i in range(H)]

sh-=1
sw-=1
gh-=1
gw-=1

ANS[sh][sw]=0

Q=deque([(sh,sw)])

while Q:
    x,y=Q.popleft()

    for i in range(x-2,x+3):
        if 0<=i<H:           
            for j in range(y-2,y+3):
                if 0<=j<W:                
                    if MAP[i][j]=="." and abs(i-x)+abs(j-y)==1 and ANS[i][j]>ANS[x][y]:
                        ANS[i][j]=ANS[x][y]
                        Q.append((i,j))
                    elif MAP[i][j]=="." and abs(i-x)+abs(j-y)>1 and ANS[i][j]>ANS[x][y]+1:
                        ANS[i][j]=ANS[x][y]+1
                        Q.append((i,j))

if ANS[gh][gw]==1<<30:
    print(-1)
else:
    print(ANS[gh][gw])

Submission status: Time Limit Exceeded

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
visited = [[inf] * W for _ in range(H)]
visited[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 visited[u + i][v + j] > visited[u][v]):
            visited[u + i][v + j] = visited[u][v]
            q.append((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 visited[u + i][v + j] > visited[u][v] + 1):
                visited[u + i][v + j] = visited[u][v] + 1
                q.append((u + i, v + j))

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

Submission status: Time Limit Exceeded

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)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx,sy)]
heapq.heapify(hq)
while hq:
    d,x,y = heapq.heappop(hq)
    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
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx,ny))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx,ny))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])

Submission status: Time Limit Exceeded

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())
S = [list(input()[:-1]) for i in range(h)]

d = [[10**20]*w for i in range(h)]

dq = deque([(ch-1,cw-1,0)])
d[ch-1][cw-1] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]

while dq:
    nx,ny,nd = dq.popleft()
    if nd < d[nx][ny]:continue
    for delta in range(4):
        tx,ty = nx+dx[delta], ny + dy[delta]
        if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]:
            d[tx][ty] = d[nx][ny]
            dq.appendleft((tx,ty,d[tx][ty]))
    for deltax in range(-2,3):
        for deltay in range(-2,3):
            tx,ty = nx+deltax, ny + deltay
            if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]+1:
                d[tx][ty] = d[nx][ny] + 1
                dq.appendleft((tx,ty,d[tx][ty]))

print(d[dh-1][dw-1] if d[dh-1][dw-1] != 10**20 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def dijkstra(s, n, edge):
  inf = 10**20
  ans = [inf]*n
  ans[s] = 0
  root = [-1]*n
  h = [[0, s]]
  while h:
    c, v = heappop(h)
    if ans[v] < c:
      continue
    for u, t in edge[v]:
      if c+t < ans[u]:
        ans[u] = c+t
        root[u] = v
        heappush(h, [c+t, u])
  return ans
h,w=map(int,input().split())
hw=lambda hh,ww:hh*w+ww
ch,cw=map(int,input().split())
s=hw(ch-1,cw-1)
dh,dw=map(int,input().split())
g=hw(dh-1,dw-1)
b=[list(input())for _ in range(h)]
edge=[[]for _ in range(h*w)]
for i in range(h):
  for j in range(w):
    if b[i][j]=="#":continue
    if i!=h-1:
      if b[i+1][j]==".":
        edge[hw(i,j)].append((hw(i+1,j),0))
        edge[hw(i+1,j)].append((hw(i,j),0))
    if j!=w-1:
      if b[i][j+1]==".":
        edge[hw(i,j)].append((hw(i,j+1),0))
        edge[hw(i,j+1)].append((hw(i,j),0))
    for ii in range(max(0,i-2),min(h,i+3)):
      for jj in range(max(0,j-2),min(w,j+3)):
        if i==ii and j==jj:continue
        if b[ii][jj]==".":
          edge[hw(i,j)].append((hw(ii,jj),1))
ans=dijkstra(s,h*w,edge)[g]
if ans==10**20:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
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 = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
heap = [(0, Ch, Cw)]
while heap:
    d, i, j = heappop(heap)
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            heappush(heap, (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]:
                heappush(heap, (d + 1, ni, nj))
print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    r = float('inf')
    move_y = [-1, 0, 1, 0]
    move_x = [0, 1, 0, -1]
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for k1 in range(4):
            j1 = koko_y + move_y[k1]
            j2 = koko_x + move_x[k1]
            if maze[j1][j2] == 'G':
                r = min(r, koko_num)
            elif maze[j1][j2] == '.':
                maze[j1][j2] = koko_num
                q.appendleft((j1, j2))
            elif type(maze[j1][j2]) == int:
                if maze[j1][j2] > koko_num:
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    r = min(r, koko_num + 1)
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.append((i1, i2))
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    c = list(map(lambda x: int(x)+1, input().split()))
    d = list(map(lambda x: int(x)+1, input().split()))
    s = ['#'*(w+4)]*2 + ['#'*2 + input() + '#'*2 for _ in range(h)] + ['#'*(w+4)]*2

    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[c[0]][c[1]] = 0

    move1 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    move2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i)+abs(j) > 1]

    yet = deque([(c[0], c[1])])
    done = deque()

    while yet:
        y, x = yet.popleft()
        done.append((y, x))
        for dy, dx in move1:
            ydy, xdx = y+dy, x+dx
            if ans[ydy][xdx] == -1:
                yet.append((ydy, xdx))
                ans[ydy][xdx] = ans[y][x]

        if len(yet) == 0:
            while done:
                y, x = done.popleft()
                for dy, dx in move2:
                    ydy, xdx = y+dy, x+dx
                    if ans[ydy][xdx] == -1:
                        ans[ydy][xdx] = ans[y][x] + 1
                        yet.append((ydy, xdx))

    print(ans[d[0]][d[1]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    start_h, start_w = map(lambda x: int(x)+1, input().split())
    goal_h, goal_w = map(lambda x: int(x)+1, input().split())

    s = ["#"*(w+4)]
    s.append("#"*(w+4))
    for _ in range(h):
        s.append("##" + input() + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))

    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[start_h][start_w] = 0

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

    yet = deque([(start_h, start_w)])
    done = deque()

    while yet:
        x1, y1 = yet.popleft()
        done.append((x1, y1))
        for (p, q) in move1:
            v1, v2 = x1+p, y1+q
            if ans[v1][v2] == -1: #"."でまだ辿り着いていないマス
                yet.append((v1, v2))
                ans[v1][v2] = ans[x1][y1]

        if len(yet) == 0:
            while done:
                x2, y2 = done.popleft()
                for (p, q) in move2:
                    i, j = x2+p, y2+q
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        yet.append((i, j))

    print(ans[goal_h][goal_w])

if __name__ == "__main__":
    main()

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())
grid = []
cost = []
INF = 10**9+7

for i in range(H):
    b = input()
    grid.append(b)
    c = [INF for _ in range(W)]
    cost.append(c)

p = (Ch,Cw)
dqe = deque([p])
cost[Ch][Cw] = 0
while len(dqe) != 0:
    x,y = dqe.popleft()
    comsumption = cost[x][y]
    for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if nx < 0 or nx >= H or ny < 0 or ny >= W:
            continue
        if grid[nx][ny] == '#':
            continue
        if cost[nx][ny] <= comsumption:
            continue
        cost[nx][ny] = comsumption
        np = (nx,ny)
        dqe.appendleft(np)
    
    for nx in range(x-2,x+3):
        for ny in range(y-2,y+3):
            if (nx == x and ny == y):
                continue
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if grid[nx][ny] == '#':
                continue
            if cost[nx][ny] <= comsumption+1:
                continue
            cost[nx][ny] = comsumption+1
            np = (nx,ny)
            dqe.append(np)

ans = cost[Dh][Dw]
if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

maze = []
for i in range(h):
    t = list(input())
    maze.append(t)

maze[dh-1][dw-1] = "g"

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

ans = 0
queue = deque([(ch-1, cw-1)])
check = deque([])
while True:
    while queue:
        y, x = queue.popleft()
        check.append((y, x))
        for dxi, dyi in zip(dx, dy):
            if not (0<=x+dxi<w and 0<=y+dyi<h):
                continue
            if maze[y+dyi][x+dxi] == "g":
                print(ans)
                exit()
            if maze[y+dyi][x+dxi] != ".":#次の行き先が「街の中じゃない」もしくは「壁」
                pass
            else:
                queue.append((y+dyi, x+dxi))
                maze[y+dyi][x+dxi] = ans
    ans += 1
    while check:
        y, x = check.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                if not (0<=x+i<w and 0<=y+j<h):
                    continue
                if maze[y+j][x+i] == "g":
                    print(ans)
                    exit()
                if maze[y+j][x+i] != ".":
                    pass
                else:
                    maze[y+j][x+i] = ans
                    queue.append((y+j, x+i))
    if not queue:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["##"+input()+"##" for x in range(h)]
  for i in range(2):
    M.insert(0,"#"*(w+4))
    M.append("#"*(w+4))

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

import sys
input = lambda: sys.stdin.readline().rstrip("\r\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
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque, defaultdict
def bfs(x, y):
    wp = defaultdict(list)
    d = [[-1] * w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])
    while queue:
        u, v = queue.popleft()
        wp[0].append((u, v))
        next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
        for x, y in next_grid:
            if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                d[x][y] = d[u][v]
                queue.append((x, y))
    for i in range(10**6):
        if len(wp[i]) == 0:
            break
        queue = deque([])
        for x, y in wp[i]:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    u, v = x + dx, y + dy
                    if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] < 0:
                        d[u][v] = i + 1
                        queue.append((u, v))
        while queue:
            u, v = queue.popleft()
            wp[i + 1].append((u, v))
            next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
            for x, y in next_grid:
                if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                    d[x][y] = d[u][v]
                    queue.append((x, y))
    return d

d = bfs(ch, cw)
print(d[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque
def main():
  h,w = map(int,input().split())
  ch,cw = map(lambda x:int(x)+1,input().split())
  dh,dw = map(lambda x:int(x)+1,input().split())
  s = [["#"]*(w+4) for _ in range(2)]+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4) for _ in range(2)]
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      if s[ah][aw]!=".":
        continue
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import collections

input = stdin.readline

Y, X = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1
sx -= 1
ey, ex = map(int, input().split())
ey -= 1
ex -= 1
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
dis = [[float('inf')] * X for _ in range(Y)]

Q = collections.deque()
Q.append((sy, sx,))
dis[sy][sx] = 0
while Q:
    cy, cx = Q.popleft()
    for ny, nx in [(cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)]:
        if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx]:
            Q.appendleft((ny,nx))
            dis[ny][nx] = dis[cy][cx]
    for dy in range(-2,3):
        for dx in range(-2,3):
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx] + 1:
                Q.append((ny,nx))
                dis[ny][nx] = dis[cy][cx] + 1

print(dis[ey][ex] if dis[ey][ex] != float('inf') else -1)

Submission status: Accepted

Solution code:
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int,input().split())
si,sj = map(int,input().split())
ti,tj = map(int,input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1

s = list()
for i in range(H):
  s.append(input())

inf = 10**9

dist = [[inf] * W for i in range(H)]
dist[si][sj] = 0
q = deque()
q.appendleft([si,sj])

while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
    
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "#":
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)