Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Accepted

Solution code:
import collections

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze = [list(input()) for i in range(h)]

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

field = [[False for i in range(w)] for j in range(h)]
field[sy][sx] = True
dx = [1,0,-1,0]
dy = [0,1,0,-1]

q = collections.deque()
q2 = collections.deque()
q.append((sy,sx))
count = 0
maze[sy][sx] = 0

def f(count):
    while q:
        s = q.popleft()
        y,x = s[0],s[1]
        count = maze[y][x]
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<=newy<h and 0<=newx<w:
                if newy == gy and newx == gx:
                    print(count)
                    exit()
                if maze[newy][newx] == ".":
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                elif maze[newy][newx] != "#" and field[newy][newx] == False:
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                field[newy][newx] = True
        for ddy in range(-2,3):
            for ddx in range(-2,3):
                newy = y+ddy
                newx = x+ddx
                if  0<=newy<h and 0<=newx<w:
                    if maze[newy][newx] == "." and field[newy][newx] == False:
                        maze[newy][newx] = count+1
                        q.append((newy,newx))

f(count)
if maze[gy][gx] != ".":
    print(maze[gy][gx])
else:
    print(-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
a = 0
while(1):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > a+1):
        a += 1
        c = stc1[a][0]
        d = stc1[a][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            a = 0
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
                magic.append([1, 1])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
                magic.append([1, -1])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
                magic.append([-1, 1])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
                magic.append([-1, -1])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
A = [input() for i in range(h)]

tree = Uf(h*w)
for i in range(h):
    for j in range(w):
        if A[i][j] == "#":
            continue
        if i > 0 and A[i-1][j] == ".":
            tree.unite(w*i+j, w*(i-1)+j)
        if i < h-1 and A[i+1][j] == ".":
            tree.unite(w*i+j, w*(i+1)+j)
        if j > 0 and A[i][j-1] == ".":
            tree.unite(w*i+j, w*i+(j-1))
        if j < w-1 and A[i][j+1] == ".":
            tree.unite(w*i+j, w*i+(j+1))

# print(tree.p)

par_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            par_list.add(tree.root(w*i+j))

# print(par_list)

node = dict()
for i, e in enumerate(par_list):
    node[e] = i

# print(node)

edge_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            for a in range(max(0, i - 2), min(h, i+3)):
                for b in range(max(0, j - 2), min(w, j + 3)):
                    if A[a][b] == "." and tree.root(w*i+j) != tree.root(w*a+b):
                        edge_list.add((node[tree.root(w*i+j)], node[tree.root(w*a+b)]))
                        edge_list.add((node[tree.root(w*a + b)], node[tree.root(w*i + j)]))

start = node[tree.root(w*(ch-1) + cw-1)]
goal = node[tree.root(w*(dh-1) + dw-1)]

g = [[] for i in range(len(node))]
for e in edge_list:
    g[e[0]].append(e[1])

# print(g, start, goal)

que = deque([(start, 0)])
seen = set()
seen.add(start)
while que:
    cur, time = que.popleft()
    if cur == goal:
        print(time)
        exit()
    for nxt in g[cur]:
        if nxt not in seen:
            seen.add(nxt)
            que.append((nxt, time+1))

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
cy, cx = map(lambda x:int(x)-1, input().split())
gy, gx = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(h)]
seen = [[-1]*w for _ in range(h)]
def f(sy, sx, cnt):
    que = []
    que.append((sy, sx))
    seen[sy][sx] = cnt
    while que:
        y, x = que.pop()
        for dy, dx in ((-1,0),(0,-1),(1,0),(0,1)):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if seen[ny][nx] != -1:
                    continue
                if S[ny][nx] == "#":
                    continue
                seen[ny][nx] = cnt
                que.append((ny, nx))
cnt = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == "." and seen[i][j] == -1:
      f(i, j, cnt)
      cnt += 1
G = [set() for _ in range(cnt+1)]
for i in range(h):
  for j in range(w):
    for dy in range(-2, 3):
      for dx in range(-2, 3):
        y, x = i+dy, j+dx
        if 0 <= y < h and 0 <= x < w:
          if S[i][j] == "#":
            continue
          if S[y][x] == "#":
            continue
          G[seen[i][j]].add(seen[y][x])
          G[seen[y][x]].add(seen[i][j])
s = seen[cy][cx]
g = seen[gy][gx]
dist = [-1]*(cnt+1)
dist[s] = 0
que = deque()
que.append(s)
while que:
  v = que.popleft()
  if g == v:
    print(dist[g])
    exit()
  for i in G[v]:
    if dist[i] != -1:
      continue
    dist[i] = dist[v]+1
    que.append(i)
print(-1)

Submission status: Accepted

Solution code:
h,w = list(map(int, input().split()))
# 初期位置
ch,cw = list(map(int, input().split()))
# ゴール位置
dh,dw = list(map(int, input().split()))
b = [['#']*(w+2)]
for _ in range(h):
    b.append(['#'] + list(input()) + ['#'])
b.append(['#']*(w+2))

from collections import deque
q = deque()
nq = deque()
q.append((ch, cw))

visit = [[False]*(w+2) for _ in range(h+2)]

warp = 0
while q or nq:
    while q:
        y,x = q.popleft()
        if (y,x) == (dh,dw):
            print(warp)
            exit()
        if visit[y][x]:
            continue
        visit[y][x] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            if b[y+dy][x+dx] == '.':
                if not visit[y+dy][x+dx]:
                    q.append((y+dy, x+dx))
            else:
                for dx in (-2,-1,0,1,2):
                    for dy in (-2,-1,0,1,2):
                        if y+dy > h or x + dx > w:
                            continue
                        if b[y+dy][x+dx] == '.':
                            if not visit[y+dy][x+dx]:
                                nq.append((y+dy, x+dx))
    q = nq
    nq = deque()
    warp += 1
    
print(-1)

Submission status: Accepted

Solution code:
import sys
import queue
import heapq

# input
H, W = map(int, sys.stdin.readline().strip().split())
Ch, Cw = map(int, sys.stdin.readline().strip().split())
Dh, Dw = map(int, sys.stdin.readline().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))


# solve
q = []
heapq.heappush(q, (0, (Ch, Cw)))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while q:
    count, coo = heapq.heappop(q)
    uh, uw = coo

    if count > fp[uh][uw]:
        continue

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        # 盤上にいるか確認
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        # 壁の確認
        if S[vh][vw] == "#":
            continue

        # 到達済みか確認
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        # 探索候補地に追加
        fp[vh][vw] = fp[uh][uw]
        heapq.heappush(q, (fp[vh][vw], (vh, vw)))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                continue

            vh = uh + dh
            vw = uw + dw

            # 盤上にいるか確認
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            # 壁の確認
            if S[vh][vw] == "#":
                continue

            # 到達済みか確認
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            # 探索候補地に追加
            fp[vh][vw] = fp[uh][uw] + 1
            heapq.heappush(q, (fp[uh][uw] + 1, (vh, vw)))


if fp[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(fp[Dh][Dw])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = LIST()
D = LIST()
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
dist = [[INF] * W for i in range(H)]
q = deque([(C[0]-1, C[1]-1)])

dist[C[0]-1][C[1]-1] = 0
visited[C[0]-1][C[1]-1] = True
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
warp = [[-1] * W for i in range(H)]
warp[C[0]-1][C[1]-1] = 0
warp_time = 0
warp_stock = deque([[C[0]-1, C[1]-1]])

while q or warp_stock:
    while q:
        ch, cw = q.popleft()
        warp_stock.append([ch, cw])
        dh = [0, 1, 0, -1]
        dw = [1, 0, -1, 0]
        for i in range(4):
            nh = ch + dh[i]
            nw = cw + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == False and S[nh][nw] != "#":
                    # dist[nh][nw] = dist[ch][cw] + 1
                    visited[nh][nw] = True
                    warp[nh][nw] = warp_time
                    # warp_stock.append([nh, nw])
                    q.append([nh, nw])
        # print(warp_stock)
    while warp_stock:
        ch, cw = warp_stock.popleft()
        for dh in [-2, -1, 0, 1, 2]:
            for dw in [-2, -1, 0, 1, 2]:
                nh = ch + dh
                nw = cw + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == False and S[nh][nw] != "#":
                        # dist[nh][nw] = dist[ch][cw]
                        visited[nh][nw] = True
                        q.append([nh, nw])
                        warp[nh][nw] = warp_time + 1
    warp_time += 1
print(warp[D[0]-1][D[1]-1]) 
# print(warp)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    sr, sc = map(int, readline().split())
    gr, gc = map(int, readline().split())

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

    ans = 0
    que1 = deque()
    que2 = deque()
    que1.append((sr, sc))
    grid[sr][sc] = "!"

    while que1 or que2:
        while que1:
            cr, cc = que1.popleft()
            que2.append((cr, cc))

            if cr == gr and cc == gc:
                return print(ans)

            if grid[cr + 1][cc] == ".":
                que1.appendleft((cr + 1, cc))
                grid[cr + 1][cc] = "!"
            if grid[cr - 1][cc] == ".":
                que1.appendleft((cr - 1, cc))
                grid[cr - 1][cc] = "!"
            if grid[cr][cc + 1] == ".":
                que1.appendleft((cr, cc + 1))
                grid[cr][cc + 1] = "!"
            if grid[cr][cc - 1] == ".":
                que1.appendleft((cr, cc - 1))
                grid[cr][cc - 1] = "!"

        ans += 1

        while que2:
            cr, cc = que2.popleft()
            for mr in range(-2, 3):
                for mc in range(-2, 3):
                    nr = cr + mr
                    nc = cc + mc
                    if 1 <= nr <= h and 1 <= nc <= w:
                        if grid[nr][nc] == ".":
                            que1.append((nr, nc))
                            grid[nr][nc] = "!"

    return print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
H,W = map(int,input().split())
C_pos=list(map(lambda x:int(x)-1,input().split()))
D_pos=list(map(lambda x:int(x)-1,input().split()))
Grid=[[c for c in input()] for _ in range(H)]
Dist=[[float("inf")]*W for _ in range(H)]

DX=[0,0,1,-1]
DY=[1,-1,0,0]

Q=deque()
Q.append((C_pos[0],C_pos[1]))
DX=[-1,1,0,0]
visited=set()
prev_visited=set()

dist=0
while True:
    prev_visited=set(v for v in Q)
    if len(Q)==0:
        print(-1)
        exit()

    #できる限りbfs
    while Q:
        cx,cy=Q.pop()
        if cx==D_pos[0] and cy==D_pos[1]:
            print(dist)
            exit()

        visited.add((cx,cy))
        for dx,dy in zip(DX,reversed(DX)):
            nx = cx+dx
            ny=cy+dy
            if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and (nx,ny) not in visited:
                visited.add((nx,ny))
                prev_visited.add((nx,ny))
                Dist[nx][ny]=dist
                Q.append((nx,ny))
                if nx==D_pos[0] and ny==D_pos[1]:
                    print(dist)
                    exit()

    Q=deque()
    for cx,cy in prev_visited:
        for dx in range(-2,3):
            for dy in range(-2,3):
                if dx==0 and dy==0:
                    continue
                nx = cx+dx
                ny=cy+dy
                if (nx,ny) in visited:
                    continue
                if 0<=nx<H and 0<=ny<W and Grid[nx][ny]==".":
                    Q.append((nx,ny))
    dist+=1

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch - 1][Cw - 1] = 1



def water(x, y):
    if floor[y][x] != 0:
        kouho.append([x, y])
        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H - 1) + 1):
        for X in range(max(x - 2, 0), min(x + 2, W - 1) + 1):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1
                water(X, Y)

kouho = deque()
# スタート地点に水を流す
water(Cw - 1, Ch - 1)
# print(floor)

# ワープ回数
for i in range(1, 1000000):
    flag = False
    new_kouho = kouho.copy()
    kouho.clear()
    for n in new_kouho:
        x = n[0]
        y = n[1]
        if floor[y][x] == i:
            warp(x, y, i)
            flag = True

    if floor[Dh - 1][Dw - 1] != 0:
        print(floor[Dh - 1][Dw - 1] - 1)
        # print(floor)
        sys.exit()

    if flag == False:
        print("-1")
        sys.exit()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

def search(cost, sx, sy):
    # ある地点からジャンプ無しで行ける範囲を探索

    que = deque()
    que.append((sx,sy))

    reached = []

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

        # 訪れた場所リスト
        reached.append((x,y))

        if cost_map[y][x] <= cost:
            continue
        cost_map[y][x] = cost

        for x2, y2 in neighbors4(x,y):
            if x2<0 or x2>=w or y2<0 or y2>=h:
                continue
            if grid_s[y2][x2] == ".":
                que.append((x2, y2))
    
    return reached

def jump(cost, x, y):
    if cost >= cost_map[y][x]:
        return
    reached = search(cost, x, y)
    
    # ゴールに到達したらおわり
    if cost_map[dh][dw] != INF:
        print(cost_map[dh][dw])
        exit()
    
    # 1回ジャンプする
    for x,y in reached:
        for y2 in range(max(0, y-2), min(h, y+3)):
            for x2 in range(max(0, x-2), min(w, x+3)):
                if abs(x-x2) + abs(y-y2) < 2:
                    continue
                if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                    heappush(jump_que, (cost+1, x2, y2))

def main():
    global h,w,dh,dw,grid_s,cost_map, jump_que,INF
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w = get_nums_l()
    ch,cw = get_nums_l()
    dh,dw = get_nums_l()

    # 0-originに変換
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1

    grid_s = []
    for i in range(h):
        grid_s.append(input())
    
    cost_map = [[INF] * w for _ in range(h) ]

    jump_que = deque()
    jump_que.append((0, cw, ch))

    while jump_que:
        cost, x, y = jump_que.popleft()
        
        if cost >= cost_map[y][x]:
            continue
        reached = search(cost, x, y)
        
        # ゴールに到達したらおわり
        if cost_map[dh][dw] != INF:
            print(cost_map[dh][dw])
            exit()
        
        # 1回ジャンプする
        for x,y in reached:
            for y2 in range(max(0, y-2), min(h, y+3)):
                for x2 in range(max(0, x-2), min(w, x+3)):
                    if abs(x-x2) + abs(y-y2) < 2:
                        continue
                    if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                        jump_que.append((cost+1, x2, y2))
    
    print(-1)

main()

Submission status: Accepted

Solution code:
from collections import deque
import time


def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

            
            
def f2(x,y,xa,ya):
    if 0 <= xa <= h and 0 <= ya <= w:
    
        if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

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

t0 = time.time()

c = ["#"]*(h+2)
for i in range(1,h+1):
    c[i] = ["#"] + list(input()) + ["#"]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:
    
    if time.time() - t0 >= 1.5:
        break
    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)


print(reach[dx][dy])

Submission status: Accepted

Solution code:
from collections import deque

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

N = [[1000000007] * W for i in range(H)]
visited = [[False] * W for i in range(H)]
q = deque([(Ch, Cw)])
N[Ch][Cw] = 0
while len(q) > 0:
    Ph, Pw = q.popleft()
    if visited[Ph][Pw]:
        continue
    visited[Ph][Pw] = True
    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh = Ph + dh
        nw = Pw + dw
        if not 0 <= nh < H or not 0 <= nw < W or S[nh][nw] == '#':
            continue
        N[nh][nw] = min(N[nh][nw], N[Ph][Pw])
        if not visited[nh][nw]:
            q.appendleft((nh, nw))
    for dh in range(-2, 3):
        nh = Ph + dh
        if not 0 <= nh < H:
            continue
        for dw in range(-2, 3):
            nw = Pw + dw
            if not 0 <= nw < W or S[nh][nw] == '#':
                continue
            N[nh][nw] = min(N[nh][nw], N[Ph][Pw] + 1)
            if not visited[nh][nw]:
                q.append((nh, nw))

print(N[Dh][Dw] if visited[Dh][Dw] else -1)

Submission status: Accepted

Solution code:
def abc176_d():
    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 = [[x for x in str(input())] for _ in range(h)]
    #print(*grid, sep='\n')
    area = [[-1]*w for _ in range(h)]
    aid = -1
    graph = []

    def dfs(i, j):
        nonlocal aid
        if area[i][j] > -1: return
        if grid[i][j] == '#': return
        area[i][j] = aid
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if 0 <= i+dx and i+dx < h and 0 <= j+dy and j+dy < w:
                    v = area[i+dx][j+dy]
                    if v > -1 and v != aid:
                        graph[aid].add(v)
                        graph[v].add(aid)
        for dx, dy in [(-1,0),(0,-1),(0,1),(1,0)]:
            if 0 <= i+dx and i+dx < h and 0 <= j+dy and j+dy < w:
                dfs(i+dx, j+dy)

    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.' and area[i][j] == -1:
                aid += 1
                graph.append(set())
                dfs(i, j)

    #print(*area, sep='\n')
    #print(graph)

    from collections import deque
    s = area[ch][cw]
    que = deque([s])
    dist = [-1] * (aid+1)
    dist[s] = 0
    while que:
        u = que.popleft()
        for i in graph[u]:
            if dist[i] == -1:
                dist[i] = dist[u] + 1
                que.append(i)
    #print(dist)
    ans = dist[area[dh][dw]]
    print(ans)

if __name__ == '__main__':
    abc176_d()

Submission status: Accepted

Solution code:
import sys
import heapq
INF=10**9
def Dijkstra(graph, start):
  dist={}
  for i in graph:
    dist[i]=INF
  queue=[(0, start)]
  while queue:
    path_len, v=heapq.heappop(queue)
    if dist[v]==INF: 
      dist[v]=path_len
      for w in graph[v]:
        if dist[w]==INF:
          heapq.heappush(queue, (dist[v]+1, w))         
  return dist
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
m=[]
for i in range(h):
  s=input()
  m.append(s)
uf=UnionFind(h*w)
for i in range(h):
  for j in range(w):
    if j+1<w and m[i][j]=='.' and m[i][j+1]=='.':
      uf.union(i+h*j,i+h*(j+1))
    if i+1<h and m[i][j]=='.' and m[i+1][j]=='.':
      uf.union(i+h*j,i+1+h*j)
if uf.same((ch-1)+(cw-1)*h,(dh-1)+(dw-1)*h):
  print(0)
  sys.exit()
graph={}
for i in uf.roots():
  graph[i]=set()
for i in range(h):
  for j in range(w):
    if m[i][j]!='.':
      continue
    for k in range(-2,3):
      for l in range(3):
        if i+k<0 or i+k>=h or j+l>=w:
          continue
        if m[i+k][j+l]!='.' or uf.same(i+k+(j+l)*h,i+j*h):
          continue
        graph[uf.find(i+k+(j+l)*h)].add(uf.find(i+j*h))
        graph[uf.find(i+j*h)].add(uf.find(i+k+(j+l)*h))
dist=Dijkstra(graph,uf.find(ch-1+(cw-1)*h))
if dist[uf.find(dh-1+(dw-1)*h)]==INF:
  print(-1)
else:
  print(dist[uf.find(dh-1+(dw-1)*h)])