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:
# by the authority of GOD    author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase
from collections import deque,defaultdict

def main():
    h,w = map(int,input().split())
    x1,y1 = map(int,input().split())
    a1,b1 = map(int,input().split())
    arr = [list(input().strip()) for _ in range(h)]
    dp = [[0]*w for _ in range(h)]
    se = set()
    for i in range(h):
        for j in range(w):
            if arr[i][j] != '#':
                se.add((i,j))
    reg = 1
    while len(se):
        x = se.pop()
        curr = deque([x])
        while len(curr):
            y = curr.popleft()
            z = (y[0]+1,y[1])
            dp[y[0]][y[1]] = reg
            if z[0]<h and z[1]<w and z in se and arr[z[0]][z[1]] != '#':
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0],y[1]+1)
            if z[0] < h and z[1] < w and z in se and arr[z[0]][z[1]] != '#':
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0]-1, y[1])
            if z[0] >= 0 and z[1] >= 0 and z in se and arr[z[0]][z[1]] != '#':
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0],y[1] - 1)
            if z[0] >= 0 and z[1] >= 0 and z in se and arr[z[0]][z[1]] != '#':
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
        reg += 1
    path = defaultdict(set)
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '#':
                continue
            for r in range(-2,3):
                for q in range(-2,3):
                    if 0<=i+r<h and 0<=j+q<w and dp[i][j] != dp[i+r][j+q] and dp[i+r][j+q]:
                        path[dp[i][j]].add(dp[i+r][j+q])
    st = dp[x1-1][y1-1]
    en = dp[a1-1][b1-1]
    curr = deque([st])
    visi = {st}
    ans=fl=0
    val = 1
    tar = 0
    val1 = 0
    while len(curr):
        x = curr.popleft()
        tar += 1
        if x == en:
            fl = 1
            break
        for i in path[x]:
            if i not in visi:
                visi.add(i)
                curr.append(i)
                val1 += 1
        if tar == val:
            tar = 0
            val = val1
            val1 = 0
            ans += 1
    if fl:
        print(ans)
    else:
        print(-1)


#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

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())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.appendleft((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])

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
q1 = deque()
q1.append((C_h - 1, C_w - 1))
q2 = deque()


def bfs_1():
    while q1:
        u, v = q1.popleft()
        q2.append((u, v))
        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]
                q1.append((u + i, v + j))
                q2.append((u + i, v + j))


def bfs_2():
    while q2:
        u, v = q2.popleft()
        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
                    q1.append((u + i, v + j))


while q1 or q2:
    bfs_1()
    bfs_2()

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 queue
h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
s=[input() for _ in range(h)]
q=queue.deque([[sy-1,sx-1]])
q2=[[sy-1,sx-1]]
q3=[]
inf=10**7
dist=[[inf for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
dist[sy-1][sx-1]=0

while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
            dist[ny][nx]=min(dist[y][x],dist[ny][nx])
            q.append([ny,nx])
            q2.append([ny,nx])
    if not q:
        for y,x in q2:
            for dy in range(-2,3):
                for dx in range(-2,3):
                    ny,nx=y+dy,x+dx
                    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
                        dist[ny][nx]=min(dist[y][x]+1,dist[ny][nx])
                        q.append([ny,nx])
                        q3.append([ny,nx])
        q2=q3
        q3=[]
print(dist[gy-1][gx-1] if dist[gy-1][gx-1]!=inf else -1)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())

sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

l = [list(input()) for i in range(h)]

dp = [[float("INF")]*w for i in range(h)]

dp[sx][sy] = 0

q = deque([])
q.append([sx,sy])
dx = [0,0,1,-1]
dy = [1,-1,0,0]
count = 0
while True:
    cq = []
    while q:
        x,y = q.popleft()
        cq.append((x,y))
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and l[nx][ny] == "." and dp[nx][ny] > count:
                dp[nx][ny] = count
                q.append([nx,ny])
    if dp[gx][gy] < float("INF"):
        print(dp[gx][gy])
        exit()
    count += 1
    if len(cq) == 0:
        break
    for x,y in cq:
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i
                ny = y+j
                if 0 <= nx < h and 0 <= ny < w and l[nx][ny] == "." and dp[nx][ny] > count:
                    dp[nx][ny] = count
                    q.append([nx,ny])

if dp[gx][gy] == float("INF"):
    print(-1)

Submission status: Accepted

Solution code:
DESTINATION = [(1, 0), (0, 1), (-1, 0), (0, -1)]


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


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 = [input() for _ in range(H)]
    distance = [[float("inf")] * W for _ in range(H)]
    stack = [[Ch, Cw]]
    cost = 0
    while len(stack):
        visited = set()
        while len(stack):
            h, w = stack.pop()
            visited.add((h, w))
            for dh, dw in DESTINATION:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and distance[nh][nw] == float("inf"):
                    stack.append([nh, nw])
                    distance[nh][nw] = cost
        for h, w in visited:
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and distance[nh][nw] == float("inf"):
                        stack.append([nh, nw])
                        distance[nh][nw] = cost + 1
        cost += 1
    if distance[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(distance[Dh][Dw])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

grid = []
for _ in range(H):
	grid.append(list(c == "." for c in input().strip()))

m = H * W + 1
smallests = [[m] * W for _ in range(H)]

queue_move = [(0, Cw, Ch)]
queue_warp = [(0, Cw, Ch)]
smallests[Ch][Cw] = 0

def calc():
	while queue_move or queue_warp:
		if queue_move:
			d, x, y = heappop(queue_move)
			if d == smallests[y][x]:
				for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
					tx = x + dx
					ty = y + dy
					if tx >= 0 and tx < W and ty >= 0 and ty < H:
						if grid[ty][tx] and d < smallests[ty][tx]:
							smallests[ty][tx] = d
							heappush(queue_move, (d, tx, ty))
							heappush(queue_warp, (d, tx, ty))
		else:
			d, x, y = heappop(queue_warp)
			if d == smallests[y][x]:
				d += 1
				for tx in range(max(0, x - 2), min(W, x + 3)):
					for ty in range(max(0, y - 2), min(H, y + 3)):
						if grid[ty][tx] and d < smallests[ty][tx]:
							smallests[ty][tx] = d
							heappush(queue_move, (d, tx, ty))
							heappush(queue_warp, (d, tx, ty))
	return smallests[Dh][Dw]

result = calc()
if result == m:
	print(-1)
else:
	print(result)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)
#print(seen)
now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
seen[s[0]][s[1]] = 1
from collections import deque
now = deque([s])
while now:
  for i in range(10**6):
    try:
      a,b = now[i]
      check(a-1,b)
      check(a+1,b)
      check(a,b-1)
      check(a,b+1)
    except:
      break
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  #print(now)
  ans += 1
  last = now
  now = deque()
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
  #print(now)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    qn = deque([[sy,sx]])

    while q:
        # print('---q')
        while q:
            y, x = q.popleft()
            qn.append([y,x])
            if [y, x] == [gy, gx]:
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x]
                    q.append([ny,nx])
                    qn.append([ny,nx])
        #     print(q)
        #     print(qn)
        #     print()
            
        # print('---------qn')
        next_qnl = []
        while qn:
            y, x = qn.popleft()
            # q.append([y,x])
            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        # qn.append([ny,nx])
                        q.append([ny,nx])
            # print(q)
            # print(qn)
            # print()

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ch, Cw = (map(lambda x:int(x)-1, input().split()))
Dh, Dw = (map(lambda x:int(x)-1, input().split()))
# Ch, Cw
# Dh, Dw
dist = []
for _ in range(H):
  dist.append(list(map(lambda x:-1 if x=='.' else 10**30, input())))

#dist = [[-1] * W for _ in range(H)]
#dist[Ch][Cw] = 0
C = set([(Ch, Cw)])
N = set()
ans = 0
while C or N:
  if C:
    #print(ans, '##', C, '##', N)
    xh, xw = C.pop()
    if dist[xh][xw] >=0:
      continue
    else:
      dist[xh][xw] = ans

    if (xh, xw) == (Dh, Dw):
      print(ans)
      exit()
    
    if xh > 0 and dist[xh-1][xw] < 0:
      C.add((xh-1,xw))
    if xh < H-1 and dist[xh+1][xw] < 0:
      C.add((xh+1,xw))
    if xw > 0 and dist[xh][xw-1] < 0:
      C.add((xh,xw-1))
    if xw < W-1 and dist[xh][xw+1] < 0:
      C.add((xh,xw+1))
    for dh in [-2, -1, 0, 1, 2]:
      for dw in [-2, -1, 0, 1, 2]:
        if 0 <= xh + dh < H and 0 <= xw + dw < W and dist[xh+dh][xw+dw] < 0:
          N.add((xh+dh, xw+dw))
  else:
    C = N
    N = set()
    ans += 1
      
      
print(-1)

Submission status: Accepted

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

H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
Board = [input().rstrip() for _ in range(H)]







Cy -= 1
Cx -= 1
Dy -= 1
Dx -= 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
vst = [[-1] * W for _ in range(H)]

def BFS(y, x, C):
    vst[y][x] = C
    q = [(x, y)]
    for x1, y1 in q:
        for i in range(4):
            x2 = x1 + dx[i]
            y2 = y1 + dy[i]
            if 0 <= x2 < W and 0 <= y2 < H and vst[y2][x2] < 0 and Board[y2][x2] == '.':
                vst[y2][x2] = C
                q.append((x2, y2))

count = 0
for i in range(H):
    for j in range(W):
        if vst[i][j] < 0 and Board[i][j] == '.':
            BFS(i, j, count)
            count += 1




adj = [set() for _ in range(count)]
vst_g = [False] * count

for i in range(H):
    for j in range(W):
        if Board[i][j] == '.':
            cur = vst[i][j]
            for x in [-2, -1, 0, 1, 2]:
                for y in [-2, -1, 0, 1, 2]:
                    x1 = x + j
                    y1 = y + i
                    if 0 <= x1 < W and 0 <= y1 < H and Board[y1][x1] == '.':
                        if vst[y1][x1] != cur:
                            adj[cur].add(vst[y1][x1])



vst_g = [-1] * count
vst_g[vst[Cy][Cx]] = 0
q = [vst[Cy][Cx]]


for u in q:
    for v in adj[u]:
        if vst_g[v] < 0:
            vst_g[v] = vst_g[u] + 1
            q.append(v)

print(vst_g[vst[Dy][Dx]])

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
todo=[[0,Ch,Cw]]
ntodo=[]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[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 todo or ntodo:
  if not todo:
    todo=ntodo
    ntodo=[]
  cnt,nh,nw=todo.pop()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.append([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        ntodo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

def main():
    direction=[[1,0],[0,1],[-1,0],[0,-1]]


    h,w=map(int,input().split())
    c=tuple(map(int,input().split()))
    d=tuple(map(int,input().split()))
    s=[input() for i in range(h)]

    itta=[[-1]*w for i in range(h)]
    itta[c[0]-1][c[1]-1]=0
    de=deque([(c[0]-1,c[1]-1)])
    # print(d)
    cnt=0
    while de:
        lst=[]
        while de:
            now=de.popleft()
            flag=0
            for i in range(4):
                nh,nw=now[0]+direction[i][0],now[1]+direction[i][1]
                if 0<=nh<h and 0<=nw<w:
                    if itta[nh][nw]==-1 and s[nh][nw]==".":
                        itta[nh][nw]=cnt
                        de.append((nh,nw))
                    elif s[nh][nw]=="#" and flag==0:
                        flag=1
                        lst.append(now)
        # print(lst)
        for i in range(len(lst)):
            for j in range(5):
                for k in range(5):
                    nh,nw=lst[i][0]-2+j,lst[i][1]-2+k
                    if 0<=nh<h and 0<=nw<w and s[nh][nw]=="." and itta[nh][nw]==-1:
                        itta[nh][nw]=cnt+1
                        de.append((nh,nw,cnt+1))
        cnt+=1
    print(itta[d[0]-1][d[1]-1])

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

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
field = []
block_num = 0
for _ in range(h):
    line = input().rstrip()
    field.append(line)
    block_num += line.count("#")
if h * w == 10**6 and block_num < 1000:
    print(0)
    exit()

edge = [[] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            continue
        frm = i * w + j
        for dx in range(-2, 3):
            nx = i + dx
            if nx < 0 or nx > h - 1:
                continue
            for dy in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue
                ny = j + dy
                if ny < 0 or ny > w - 1:
                    continue
                if field[nx][ny] == "#":
                    continue
                dist = abs(dx) + abs(dy)
                if dist == 1:
                    edge[frm].append((nx*w + ny, 0))
                else:
                    edge[frm].append((nx*w + ny, 1))
        
DIJK = Dijkstra(edge)
dist = DIJK.calc(ch * w + cw)
if dist[dh * w + dw] == INF:
    print(-1)
else:
    print(dist[dh * w + dw])

Submission status: Accepted

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 = [False] * (H * W)

    M = {C}
    Q = [C]
    F[C[0] * W + C[1]] = 0
    c = 0
    while len(M) > 0:
        M.clear()
        while Q:
            h, w = Q.pop()
            M.add((h, w))
            if (h, w) == D:
                print(c)
                return

            for d in (1, -1):
                if 0 <= w + d < W and S[h][w + d] == "." and not F[h * W + w + d]:
                    F[h * W + w + d] = True
                    Q.append((h, w + d))
                if 0 <= h + d < H and S[h + d][w] == "." and not F[(h + d) * W + w]:
                    F[(h + d) * W + w] = True
                    Q.append((h + d, w))
        for h, w in M:
            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 not F[hh * W + ww]:
                        F[hh * W + ww] = True
                        Q.append((hh, ww))
        c += 1
    print(-1)
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = [int(hoge) for hoge in input().split()]
curh,curw = [int(hoge)-1 for hoge in input().split()]
gh,gw = [int(hoge)-1 for hoge in input().split()]
S = [input() for _ in range(H)]
#01BFS典型
Dist = [[999999 for w in range(W)] for h in range(H)]
Dist[curh][curw] = 0
BFS = deque()#取り出しは左からpopleft
BFS.append((curh,curw))
while BFS:
    curh,curw = BFS.popleft()
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
        if 0<=curh+dx<H and 0<=curw+dy<W and S[curh+dx][curw+dy]==".":
            if Dist[curh+dx][curw+dy] > Dist[curh][curw]:
                Dist[curh+dx][curw+dy] = Dist[curh][curw]
                BFS.appendleft((curh+dx,curw+dy))

  

    for dx in range(-2,3):
        for dy in range(-2,3):
            if 0<=curh+dx<H and 0<=curw+dy<W and  S[curh+dx][curw+dy]==".":
                if Dist[curh+dx][curw+dy] > Dist[curh][curw] + 1:
                    Dist[curh+dx][curw+dy] = Dist[curh][curw]+1
                    BFS.append((curh+dx,curw+dy))
ans = Dist[gh][gw]
if ans == 999999:
    ans = -1
print(ans)

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

def newv(y,x):
  return y*w+x

e = [[] for _ in range(h*w)]
for y in range(h):
  for x in range(w):
    if s[y][x] == '#':
      continue
    for dy in range(-2,3):
      for dx in range(-2,3):
        if not(0 <= y+dy < h) or not(0 <= x+dx < w):
          continue
        if dy == 0 and dx == 0:
          continue
        if abs(dy)+abs(dx) == 1:
          if s[y+dy][x+dx] == '.':
            e[newv(y,x)].append((newv(y+dy,x+dx),0))
        else:
          if s[y+dy][x+dx] == '.':
            e[newv(y,x)].append((newv(y+dy,x+dx),1))

from heapq import heappop, heappush
INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

ans = dijkstra(newv(ch,cw),h*w,e)[newv(dh,dw)]
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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


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

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

    grid = [[-1] * W for _ in range(H)]
    n = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] != -1 or S[i][j] == '#':
                continue
            grid[i][j] = n
            queue = deque([(i, j)])
            while queue:
                x, y = queue.popleft()
                for dx, dy in dxdy4:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == -1 and S[nx][ny] == '.':
                        grid[nx][ny] = n
                        queue.append((nx, ny))
            n += 1

    if grid[Ch][Cw] == grid[Dh][Dw]:
        print(0)
        return

    G = [set() for _ in range(n)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1:
                continue
            this_num = grid[i][j]
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] not in (-1, this_num):
                        G[this_num].add(grid[nx][ny])
                        G[grid[nx][ny]].add(this_num)

    queue = deque([grid[Ch][Cw]])
    dist = [-1] * n
    dist[grid[Ch][Cw]] = 0
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                queue.append(nv)

    print(dist[grid[Dh][Dw]])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
C = list(map(int, input().split()))
C = tuple([C[0]-1, C[1]-1])
D = tuple(map(int, input().split()))
D = tuple([D[0]-1, D[1]-1])
maze = [list(input()) for _ in range(h)]

visit = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            visit[i][j] = True

DQ = deque([C])
DQ_warp = deque([])

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

ans = 0

while DQ or DQ_warp:
    while DQ:
        now = DQ.popleft()
        if now == D:
            print(ans)
            exit()
        x, y = now[0], now[1]
        if visit[x][y]:
            continue
        visit[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                DQ.append(tuple([nx, ny]))

        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0: continue
                nx = x + i
                ny = y + j
                if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                    DQ_warp.append(tuple([nx, ny]))

    if DQ_warp:
        DQ = DQ_warp.copy()
        DQ_warp = deque([])
        ans += 1

print(-1)