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:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from collections import deque

h,w = ip()
ax,ay = ip()
bx,by = ip()
ax -= 1; ay -= 1; bx -= 1; by -= 1
mat = [input().strip() for i in range(h)]
dist = [[float('inf')]*w for i in range(h)]
dist[ax][ay] = 0
dx,dy = [1,-1,0,0],[0,0,-1,1]
dq = deque()
dq.append([ax,ay])
while dq:
    cx,cy = dq.popleft()
    for i in range(4):
        nx,ny = cx+dx[i], cy+dy[i]
        if 0 <= nx < h and 0 <= ny < w and mat[nx][ny] == '.':
            if dist[nx][ny] > dist[cx][cy]:
                dist[nx][ny] = dist[cx][cy]
                dq.appendleft([nx,ny])
    for i in range(cx-2,cx+3):
        for j in range(cy-2,cy+3):
            if 0 <= i < h and 0 <= j < w and mat[i][j] == '.':
                if dist[i][j] > dist[cx][cy]+1:
                    dist[i][j] = dist[cx][cy]+1
                    dq.append([i,j])
if dist[bx][by] == float('inf'): dist[bx][by] = -1
print(dist[bx][by])

Submission status: Accepted

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.appendleft((i,j,c))
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='#':q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Accepted

Solution code:
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) # [y, x]
    goal = list( map(int, input().strip().split() ) ) # [y, x]
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] # [y][x]
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    #print(dists)
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Submission status: Accepted

Solution code:
from collections import deque

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
Maze = [[_ for _ in input()] for __ in range(H)]
Q = deque()
Q.append((sy, sx, 0))
Cost = [[float('inf')] * W for _ in range(H)]
Cost[sy][sx] = 0
Move = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == j == 0:
            continue
        Move.append((i, j))
Walk = ((-1, 0), (1, 0), (0, 1), (0, -1))
while Q:
    y, x, cost = Q.popleft()
    if Cost[y][x] >= Cost[gy][gx]:
        break
    if cost > Cost[y][x]:
        continue
    for wy, wx in Walk:
        ny = y + wy
        nx = x + wx
        if ny < 0 or ny >= H or nx < 0 or nx >= W or Maze[ny][nx] == '#':
            continue
        if Cost[ny][nx] > cost:
            Q.appendleft((ny, nx, cost))
            Cost[ny][nx] = Cost[y][x]

    for my, mx in Move:
        ny = y + my
        nx = x + mx
        if ny < 0 or ny >= H or nx < 0 or nx >= W or Maze[ny][nx] == '#':
            continue
        if Cost[ny][nx] <= Cost[y][x] + 1:
            continue
        Cost[ny][nx] = Cost[y][x] + 1
        Q.append((ny, nx, cost+1))

if Cost[gy][gx] == float('inf'):
    Cost[gy][gx] = -1
print(Cost[gy][gx])

Submission status: Accepted

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [input() for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.appendleft((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury] + 1:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


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

Submission status: Accepted

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    S[CH-1][CW-1] = 0
    q = deque()
    q.appendleft((CH-1, CW-1))
    while q:
        # キューの先頭から候補を取り出す
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        # 距離0で到達可能な場所をキューの先頭に入れる
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                q.appendleft((ny, nx))
                S[ny][nx] = d0
        # 距離1で到達可能な場所をキューの末尾に入れる
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.append((ny, nx))
                S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

lim = 10**6

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

foo = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      foo[k][j] = lim
    

foo[Ch][Cw] = 0

now = deque([])
new = deque([(Ch, Cw)])
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  if foo[x+1][y] == lim:
    foo[x+1][y] = 0
    new.append((x+1, y))
  if foo[x][y+1] == lim:
    foo[x][y+1] = 0
    new.append((x, y+1))
  if foo[x-1][y] == lim:
    foo[x-1][y] = 0
    new.append((x-1, y))
  if foo[x][y-1] == lim:
    foo[x][y-1] = 0
    new.append((x, y-1))


ans = 0
while foo[Dh][Dw] == lim:
  if len(now) == 0:
    print(-1)
    exit() 
  ans += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    if foo[x+2][y+2] > ans:
      foo[x+2][y+2] = ans
      new.append((x+2, y+2))
    if foo[x+2][y+1] > ans:
      foo[x+2][y+1] = ans
      new.append((x+2, y+1))
    if foo[x+2][y] > ans:
      foo[x+2][y] = ans
      new.append((x+2, y))
    if foo[x+2][y-1] > ans:
      foo[x+2][y-1] = ans
      new.append((x+2, y-1))
    if foo[x+2][y-2] > ans:
      foo[x+2][y-2] = ans
      new.append((x+2, y-2))
    if foo[x+1][y+2] > ans:
      foo[x+1][y+2] = ans
      new.append((x+1, y+2))
    if foo[x+1][y-2] > ans:
      foo[x+1][y-2] = ans
      new.append((x+1, y-2))
    if foo[x][y+2] > ans:
      foo[x][y+2] = ans
      new.append((x, y+2))
    if foo[x][y-2] > ans:
      foo[x][y-2] = ans
      new.append((x, y-2))
    if foo[x-2][y+2] > ans:
      foo[x-2][y+2] = ans
      new.append((x-2, y+2))
    if foo[x-2][y+1] > ans:
      foo[x-2][y+1] = ans
      new.append((x-2, y+1))
    if foo[x-2][y] > ans:
      foo[x-2][y] = ans
      new.append((x-2, y))
    if foo[x-2][y-1] > ans:
      foo[x-2][y-1] = ans
      new.append((x-2, y-1))
    if foo[x-2][y-2] > ans:
      foo[x-2][y-2] = ans
      new.append((x-2, y-2))
    if foo[x-1][y+2] > ans:
      foo[x-1][y+2] = ans
      new.append((x-1, y+2))
    if foo[x-1][y-2] > ans:
      foo[x-1][y-2] = ans
      new.append((x-1, y-2))
    if foo[x-1][y-1] > ans:
      foo[x-1][y-1] = ans
      new.append((x-1, y-1))
    if foo[x-1][y+1] > ans:
      foo[x-1][y+1] = ans
      new.append((x-1, y+1))
    if foo[x+1][y+1] > ans:
      foo[x+1][y+1] = ans
      new.append((x+1, y+1))
    if foo[x+1][y-1] > ans:
      foo[x+1][y-1] = ans
      new.append((x+1, y-1))
      
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    if foo[x+1][y] == lim:
      foo[x+1][y] = 0
      new.append((x+1, y))
    if foo[x][y+1] == lim:
      foo[x][y+1] = 0
      new.append((x, y+1))
    if foo[x-1][y] == lim:
      foo[x-1][y] = 0
      new.append((x-1, y))
    if foo[x][y-1] == lim:
      foo[x][y-1] = 0
      new.append((x, y-1))
print(ans)

Submission status: Accepted

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [(y, x) for y, x in product(range(-2, 3), range(-2, 3))]
    S[CH-1][CW-1] = 0
    q = deque()
    q.append((CH-1, CW-1))
    while q:
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        # 距離0で到達可能な場所をBFS
        T = []
        r = deque()
        T.append((y0, x0))
        r.append((y0, x0))
        while r:
            y, x = r.popleft()
            for dy, dx in DIR0:
                ny, nx = y + dy, x + dx
                if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                    r.append((ny, nx))
                    T.append((ny, nx))
                    S[ny][nx] = d0
        # 距離1で到達可能な場所をBFS
        for y, x in T:
            for dy, dx in DIR1:
                ny, nx = y + dy, x + dx
                if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                    q.append((ny, nx))
                    S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import heapq
class Dijkstra:
    INF = 1 << 63

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append((cost << 31) + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p >> 31
            node = p - (cost << 31)
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to >> 31
                to_node = to - (to_cost << 31)
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, (to_cost << 31) + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == (1 << 63): print(-1)
else: print(ans)

Submission status: Accepted

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

Ch += 1
Cw += 1
Dh += 1
Dw += 1


S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

foo = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      foo[k][j] = 10**6

foo[Ch][Cw] = 0

now = []
new = [(Ch, Cw)]
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  if foo[x+1][y] == 10**6:
    foo[x+1][y] = 0
    new.append((x+1, y))
  if foo[x][y+1] == 10**6:
    foo[x][y+1] = 0
    new.append((x, y+1))
  if foo[x-1][y] == 10**6:
    foo[x-1][y] = 0
    new.append((x-1, y))
  if foo[x][y-1] == 10**6:
    foo[x][y-1] = 0
    new.append((x, y-1))


ans = 0
while foo[Dh][Dw] == 10**6:
  if len(now) == 0:
    print(-1)
    exit() 
  ans += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    if foo[x+2][y+2] > ans:
      foo[x+2][y+2] = ans
      new.append((x+2, y+2))
    if foo[x+2][y+1] > ans:
      foo[x+2][y+1] = ans
      new.append((x+2, y+1))
    if foo[x+2][y] > ans:
      foo[x+2][y] = ans
      new.append((x+2, y))
    if foo[x+2][y-1] > ans:
      foo[x+2][y-1] = ans
      new.append((x+2, y-1))
    if foo[x+2][y-2] > ans:
      foo[x+2][y-2] = ans
      new.append((x+2, y-2))
    if foo[x+1][y+2] > ans:
      foo[x+1][y+2] = ans
      new.append((x+1, y+2))
    if foo[x+1][y-2] > ans:
      foo[x+1][y-2] = ans
      new.append((x+1, y-2))
    if foo[x][y+2] > ans:
      foo[x][y+2] = ans
      new.append((x, y+2))
    if foo[x][y-2] > ans:
      foo[x][y-2] = ans
      new.append((x, y-2))
    if foo[x-2][y+2] > ans:
      foo[x-2][y+2] = ans
      new.append((x-2, y+2))
    if foo[x-2][y+1] > ans:
      foo[x-2][y+1] = ans
      new.append((x-2, y+1))
    if foo[x-2][y] > ans:
      foo[x-2][y] = ans
      new.append((x-2, y))
    if foo[x-2][y-1] > ans:
      foo[x-2][y-1] = ans
      new.append((x-2, y-1))
    if foo[x-2][y-2] > ans:
      foo[x-2][y-2] = ans
      new.append((x-2, y-2))
    if foo[x-1][y+2] > ans:
      foo[x-1][y+2] = ans
      new.append((x-1, y+2))
    if foo[x-1][y-2] > ans:
      foo[x-1][y-2] = ans
      new.append((x-1, y-2))
    if foo[x-1][y-1] > ans:
      foo[x-1][y-1] = ans
      new.append((x-1, y-1))
    if foo[x-1][y+1] > ans:
      foo[x-1][y+1] = ans
      new.append((x-1, y+1))
    if foo[x+1][y+1] > ans:
      foo[x+1][y+1] = ans
      new.append((x+1, y+1))
    if foo[x+1][y-1] > ans:
      foo[x+1][y-1] = ans
      new.append((x+1, y-1))
      
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    if foo[x+1][y] == 10**6:
      foo[x+1][y] = 0
      new.append((x+1, y))
    if foo[x][y+1] == 10**6:
      foo[x][y+1] = 0
      new.append((x, y+1))
    if foo[x-1][y] == 10**6:
      foo[x-1][y] = 0
      new.append((x-1, y))
    if foo[x][y-1] == 10**6:
      foo[x][y-1] = 0
      new.append((x, y-1))
print(ans)

Submission status: Accepted

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

class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1; sy -= 1
tx, ty = map(int, input().split())
tx -= 1; ty -= 1

S = [input() for _ in range(H)]


dxy = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = {}
next_points = set([(sx, sy)])
def bfs(d):
    global dist, next_points
    stack = list(next_points)
    next_points = set()
    while stack:
        x, y = stack.pop()
        if (x, y) in dist and dist[(x, y)] < d:
            continue
        dist[(x, y)] = d
        count = 0
        for dx, dy in dxy:
            xx = x + dx; yy = y + dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == '.':
                count += 1
                if (xx, yy) not in dist:
                    dist[(xx, yy)] = d
                    stack.append((xx, yy))
        
        if count < 4:
            for dx in range(-2, 3):
                xx = x + dx
                for dy in range(-2, 3):
                    yy = y + dy
                    if (xx, yy) not in dist and 0 <= xx < H and 0 <= yy < W \
                            and S[xx][yy] == '.':
                        next_points.add((xx, yy))

d = 0
while (tx, ty) not in dist:
    bfs(d)
    d += 1
    if len(next_points) == 0:
        if (tx, ty) in dist:
            print(dist[(tx, ty)])
        else:
            print(-1)
        quit()

print(dist[(tx, ty)])

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

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


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

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


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])


@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val

print(main(ss,ch,cw,dh,dw))