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:
from sys import stdin
from collections import deque
input = stdin.readline

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input().rstrip()) for _ in range(H)]

dir_h = [0, 0, 1, -1]
dir_w = [1, -1, 0, 0]

seen = [[-1 for _ in range(W)] for _ in range(H)]
edge = []
nex = [[ch - 1, cw - 1]]
num = 0
group = [[-1 for _ in range(W)] for _ in range(H)]


def bfs():
    q = deque([])

    for h, w in nex:
        if seen[h][w] != -1:
            continue
        q.append([h, w])
        seen[h][w] = num
        while q:
            h, w = q.popleft()

            for dh, dw in zip(dir_h, dir_w):
                nh, nw = h + dh, w + dw

                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                elif S[nh][nw] == "#":
                    edge.append([h, w])
                    continue
                elif seen[nh][nw] != -1:
                    continue
                else:
                    seen[nh][nw] = num
                    q.append([nh, nw])


def dfs():
    d = deque([])
    for h, w in edge:
        d.append([h, w])

        while d:
            h, w = d.pop()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw

                    if nh < 0 or nh >= H or nw < 0 or nw >= W:
                        continue
                    elif S[nh][nw] == "#":
                        continue
                    elif seen[nh][nw] != -1:
                        continue
                    else:
                        nex.append([nh, nw])


while True:
    bfs()
    if not edge:
        break
    nex = []
    num += 1
    dfs()
    if not nex:
        break
    edge = []

# for s in seen:
#     print(s)

print(seen[dh - 1][dw - 1])

Submission status: Accepted

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

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

[Ch, Cw, Dh, Dw] = [Ch-1, Cw-1, Dh-1, Dw-1] 

cur = [[Ch, Cw]] # queue
walked = [[Ch, Cw]]
steps = 0
step = [[1, 0], [0, 1], [-1, 0], [0, -1]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if not i==j==0]

while True:
    current = cur.pop()
#    print('currently at', current, 'with', steps, 'steps')
    for i in range(len(step)):
        nxt = [ current[0]+step[i][0], current[1]+step[i][1] ]
        if nxt[0] == Dh and nxt[1] == Dw:
            print (steps)
            quit()
        if 0<=nxt[0] <H and 0<=nxt[1]<W:
            if mp[nxt[0]][nxt[1]] == '#': # wall
                pass
            elif mp[nxt[0]][nxt[1]] == '.': # floor
                mp[nxt[0]][nxt[1]] = 'X'
                cur.append([nxt[0], nxt[1]])
                walked.append([nxt[0], nxt[1]])
    if len(cur) > 0: continue

    # no more walkable area; warp
    steps += 1
    for j in range(len(walked)):
        current = walked.pop()
        for i in range(len(warp)):
            nxt = [ current[0]+warp[i][0], current[1]+warp[i][1] ]
            if nxt[0] == Dh and nxt[1] == Dw:
                print (steps)
                quit()
            if 0<=nxt[0]<H and 0<=nxt[1]<W:
                if mp[nxt[0]][nxt[1]] == '#': # wall
                    pass
                elif mp[nxt[0]][nxt[1]] == '.': # floor
                    mp[nxt[0]][nxt[1]] = 'X'
                    cur.append([nxt[0], nxt[1]])
    if len(cur) == 0:
        print('-1')
        quit()
    walked = cur.copy()

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


ncolors = 0
def paint(grid, colors):
    global ncolors
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.' and colors[y][x] == UNDEF:
                q = collections.deque()
                colors[y][x] = ncolors
                q.append((y, x))
                while q:
                    i, j = q.popleft()

                    for ii, jj in (
                        (i - 1, j),
                        (i, j - 1),
                        (i, j + 1),
                        (i + 1, j)
                    ):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                            colors[ii][jj] = ncolors
                            q.append((ii, jj))
                ncolors += 1

paint(grid, colors)


def build(grid, colors, ncolors):
    g = [set() for _ in range(ncolors)]
    for i in range(h):
        for j in range(w):
            if colors[i][j] != UNDEF:
                for ii in range(i - 2, i + 3):
                    for jj in range(j - 2, j + 3):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                            c1 = colors[ii][jj]
                            c2 = colors[i][j]
                            assert c1 != UNDEF and c2 != UNDEF
                            g[c1].add(c2)
                            g[c2].add(c1)
    return g

g = build(grid, colors, ncolors)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * ncolors
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(lambda x: int(x)-1, input().split()))
    Dh, Dw = list(map(lambda x: int(x)-1, input().split()))
    S = [list(input()) for _ in range(H)]
    warps = [[-1 for _ in range(W)] for __ in range(H)]
    warpcnt = 0
    import collections
    warp_to = set()
    q = collections.deque([(Ch, Cw)])
    while q:
        while q:
            h, w = q.pop()
            if warps[h][w] != -1:
                continue
            warps[h][w] = warpcnt
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    q.appendleft((nh, nw))
            for dh, dw in [(-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)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    warp_to.add((nh, nw))
        q = collections.deque(list(warp_to))
        warp_to = set()
        warpcnt += 1
    print(warps[Dh][Dw])

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

    return T, k


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

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

G = gridMan(S)
G.makeWall()

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]

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

u = UnionFind(H*W)
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=='#':
            continue
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                    u.union(sh*W+sw,(sh+dx)*W+sw+dy)
d = {}
n = 0
for sh in range(H):
    for sw in range(W):
        f = u.find(sh*W+sw)
        if f not in d:
            d[f] = n
            n += 1

graph = [[] for _ in range(len(d))]
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=='#':
            continue
        f1 = u.find(sh*W+sw)
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                        f2 = u.find((sh+dx)*W+sw+dy)
                        graph[d[f1]].append((1,d[f2]))

dist = dijkstra(graph, len(d), d[u.find(Ch*W+Cw)])
ans = dist[d[u.find(Dh*W+Dw)]]
if ans == inf:
    ans = -1
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())
grid = ""
for i in range(H):
    grid += input()
grid = list(grid)

def convert_1d_to_2d(l, cols):
    return [l[i:i + cols] for i in range(0, len(l), cols)]

grid = convert_1d_to_2d(grid, W)

ans = [[1000000]*W for i in range(H)]
ans[Ch-1][Cw-1]=0

from collections import deque
ans = [[1000000]*W for i in range(H)]
ans[Ch-1][Cw-1]=0

from collections import deque

que = deque([[Ch-1,Cw-1]])
que2 = deque([[Ch-1,Cw-1]])

while que or que2:
    if que:
        x,y=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='#':
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que.append([nextx,nexty])

        for i,j in [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,2),(-1,1),(-1,-1),(-1,-2)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]+1

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='#':
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que2.append([nextx,nexty])
            
    else:
        x,y=que2.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='#':
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que.append([nextx,nexty])

        for i,j in [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,2),(-1,1),(-1,-1),(-1,-2)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]+1

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='#':
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que2.append([nextx,nexty])
        
                    
if ans[Dh-1][Dw-1]==1000000:
    print("-1")
else:
    print(ans[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
# D - Wizard in Maze
from collections import deque
import sys
INF = 10000000

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]
C = [[INF]*W for _ in range(H)]
C[Ch-1][Cw-1] = 0
que = deque([(Ch,Cw)])
now = set()
tmp = 0

while True:
    while len(que)>0:
        i,j = que.popleft()
        now.add((i,j))
        for (h,w) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 1<=h<=H and 1<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp:
                C[h-1][w-1] = tmp
                que.append((h,w))
    for i,j in now:
        for h in range(i-2,i+3):
            for w in range(j-2,j+3):
                if 1<=h<=H and 1<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp+1:
                    C[h-1][w-1] = tmp+1
                    que.append((h,w))
    now = set()
    tmp += 1
    if C[Dh-1][Dw-1]!=INF:
        print(C[Dh-1][Dw-1])
        break
    if len(que)==0:
        print(-1)
        break

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(2 * H * W + 100, np.int64)
    dist[S] = 0
    deq[H * W], l, r = S, H * W, H * W + 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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
g = ['#' * (w + 4)] * 2 
for _ in range(h):
    g.append('##' + input() + '##')
g.append('#' * (w + 4))
g.append('#' * (w + 4))

d1 = [(-1, 0), (0, -1), (0, 1), (1, 0)]
d2 = [(-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)]

from collections import deque
# BFS BFS
seen = [[-1] * (w+2) for _ in range(h+2)]
todo = deque([(0, ch, cw)])
while len(todo) > 0:
    history = []
    while len(todo) > 0:
        cost, x, y = todo.popleft()
        if seen[x][y] == -1:
            if x == dh and y == dw:
                print(cost)
                exit()
            seen[x][y] = cost
            history.append((cost, x, y))
        else:
            continue

        for i in range(4):
            dx, dy = d1[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost, x+dx, y+dy))

    for j in history:
        cost, x, y = j
        for i in range(20):
            dx, dy = d2[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost+1, x+dx, y+dy))

print(-1)

Submission status: Accepted

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

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

c = cx*w + cy
d = dx*w + dy


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

a = [10**6]*(h*w)
a[c] = 0

tank = deque([c])
used = [False]*(h*w)

while tank:
    now = tank.popleft()
    if used[now]:
        continue
    used[now] = True

    x,y = divmod(now,w)

    cost = a[now]

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            if (0 <= x+i < h) and (0 <= y+j < w) and (not used[(x+i)*w + y+j]) and s[x+i][y+j] == 46:
                if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
                    tank.appendleft((x+i)*w + y+j)
                    a[(x+i)*w + y+j] = min(a[(x+i)*w + y+j],cost)
                else:
                    tank.append((x+i)*w + y+j)
                    a[(x+i)*w + y+j] = min(a[(x+i)*w + y+j],cost + 1)

if a[d] == 10**6:
    print(-1)
else:
    print(a[d])

Submission status: Accepted

Solution code:
##import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

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)]
seen=[[0]*w for _ in range(h)]
d=deque()
ch-=1
cw-=1
dh-=1
dw-=1
res=[]
p=[[0,1],[0,-1],[1,0],[-1,0]]

seen[ch][cw]=1
d.append(ch*w+cw)
ans=0
while True:
    z=d.pop()
    x=z//w #縦
    y=z%w
    res.append([x,y])
    for v in p:
        i,j=v
        if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0:
            if s[x+i][y+j]==".":
                d.append((x+i)*w+(y+j))
                seen[x+i][y+j]=1
    if seen[dh][dw]==1:
        break
    if not d:
        ans+=1
        for z in res:
            x,y=z
            for i in range(3):
                for j in range(3):
                    if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0 and s[x+i][y+j]==".":
                        z=(x+i)*w+(y+j)
                        d.append(z)
                        seen[x+i][y+j]=1
                    if 0<=x-i<h and 0<=y-j<w and seen[x-i][y-j]==0 and s[x-i][y-j]==".":
                        z=(x-i)*w+(y-j)
                        d.append(z)
                        seen[x-i][y-j]=1
                    if 0<=x+i<h and 0<=y-j<w and seen[x+i][y-j]==0 and s[x+i][y-j]==".":
                        z=(x+i)*w+(y-j)
                        d.append(z)
                        seen[x+i][y-j]=1
                    if 0<=x-i<h and 0<=y+j<w and seen[x-i][y+j]==0 and s[x-i][y+j]==".":
                        z=(x-i)*w+(y+j)
                        d.append(z)
                        seen[x-i][y+j]=1
        res=[]
    if not d:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
cmd = [[-1,0],[1,0],[0,1],[0,-1]]
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
Map = [["#"]*(W+2)]
for _ in range(H):
    Map.append(["#"]+list(input())[:-1] + ["#"])
Map.append(["#"]*(W+2))
Q = deque([[ch,cw]])
Next = deque([])
visidat = [[10**6]*(W+2) for _ in range(H+2)]
num = 0
flag = 0
fl = 0
visidat[ch][cw] = 0
while flag == 0:
    while len(Q) != 0:
        h,w = Q.popleft()
        if h == dh and w == dw:
            print(num)
            flag = 1
            break
        if visidat[h][w] >= num:
            for i in range(-2,3):
                for j in range(-2,3):
                    p,q = h+i,w+j
                    if p < 0 or q < 0 or p > H+1 or q > W+1 or ((abs(i)+abs(j))<=1):
                        continue
                    if Map[p][q] == ".":
                        if visidat[p][q] > num + 1:
                            Next.append([p,q])
                            visidat[p][q] = num + 1
            for cx,cy in cmd:
                newh = cy + h
                neww = cx + w
                if Map[newh][neww] == "#":
                    continue
                else:
                    if visidat[newh][neww] > num :
                        visidat[newh][neww] = num
                        Q.append([newh,neww])
        else:
            continue
        
    Q = Next
    if len(Q) == 0:
        if flag == 0:
            fl = 1
        break
    Next = deque([])
    num += 1
if fl == 1:
    print(-1)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
import collections
from heapq import *
#RRR...WWW...にしたい
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)]
#print(S)
dp=[[float("inf") for _ in range(W)] for _ in range(H)]
st=[Ch-1,Cw-1]
d2=deque()
d = deque()
d2=deque()
d.append(st)
cnt=0
dp[Ch-1][Cw-1]=0
while True:
    while len(d)>0:
        x,y=d.popleft()
        d2.append([x,y])
        #print(dp[x][y],dp[x+1][y],dp[x][y+1])
        if x!=0:
            if S[x-1][y]==".":
                if dp[x-1][y]>dp[x][y]:
                    dp[x - 1][y]=dp[x][y]
                    d.append([x-1,y])
        if x!=H-1:
            if S[x+1][y]==".":
                if dp[x+1][y]>dp[x][y]:
                    dp[x + 1][y]=dp[x][y]
                    d.append([x+1,y])
        if y!=0:
            if S[x][y-1]==".":
                if dp[x][y-1]>dp[x][y]:
                    dp[x][y-1]=dp[x][y]
                    d.append([x,y-1])
        if y!=W-1:
            if S[x][y+1]==".":
                if dp[x][y+1]>dp[x][y]:
                    dp[x][y+1]=dp[x][y]
                    d.append([x,y+1])
        #print(dp,d,d2)
        #input()
    while len(d2)>0:
        x,y=d2.popleft()
        for i in range(max(0,x-2),min(x+3,H)):
            for j in range(max(0,y-2),min(y+3,W)):
                if S[i][j]==".":
                    if dp[i][j] > dp[x][y]+1:
                        dp[i][j]=dp[x][y]+1
                        d.append([i,j])
    #print(dp)
    #input()
    cnt=cnt+1
    if len(d)==0:
        break
if dp[Dh-1][Dw-1]==float("inf"):
    print(-1)
else:
    print(dp[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': continue
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    if S[y][x] == '.':
                        adj[W*i + j].append(W*y + x)

    # ワープ可能な場所もadjに加える
    worp = [[] for _ in range(W*H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': continue
            for kx in [-2,-1,0,1,2]:
                for ky in [-2,-1,0,1,2]:
                    if kx == ky == 0: continue
                    y = i + ky
                    x = j + kx
                    if W*y + x in adj[W*i + j]: continue
                    if 0 <= y < H and 0 <= x < W:
                        if S[y][x] == '.':
                            worp[W*i + j].append(W*y + x)
    
    start = W*Ch + Cw
    goal = W*Dh + Dw
    queue = deque([start])
    visit = [-1] * (W*H)
    visit[start] = 0
    
    while queue:
        nextq = queue.copy()
        while queue:
            now = queue.popleft()
            for u in adj[now]:
                if visit[u] < 0:
                    queue.append(u)
                    nextq.append(u)
                    visit[u] = visit[now]
        # print(nextq)
        while nextq:
            now = nextq.popleft()
            for u in worp[now]:
                if visit[u] < 0:
                    queue.append(u)
                    visit[u] = visit[now]+1
    
    print(visit[goal])

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()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
added = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
added[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if not reach[x][y]:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
                    added[xx][y] = True

        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
                    added[x][yy] = True 
    for i in d1:
        for j in d1:
            s,t = x+i,y+j
            if 0<=s<h and 0<=t<w:
                if S[s][t] == '.' and not added[s][t]:
                    que2.append([s,t]) 
                    added[s][t] = True

    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)