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 collections import deque
import sys

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

cost = [[0] * W for _ in range(H)]


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(ch-1, cw-1, 0)])
used = {(ch-1, cw-1)}
warp = [(ch-1, cw-1, 0)]
ddd = []
for i in range(-2,3):
    for j in range(-2,3):
        if (i,j) in dd or i == j == 0:
            continue
        ddd.append((i,j))    

idx = 0
while que:
    while que:
        s, t, cost = que.popleft()
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
            break
        for di, dj in dd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost))
            warp.append((xi,yj, cost)) 
            
    while idx <= len(warp) - 1:
        s, t, cost = warp[idx]
        for di, dj in ddd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost+1))
            warp.append((xi,yj, cost+1))
        idx += 1
        if que:
            break

print(-1)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]

  DD =  [(-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 que:
    y,x = que.popleft()
    flag = 0
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "#"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
        elif(dist>G[y][x]):
          G[y+j][x+i] = G[y][x]
          que.appendleft([y+j,x+i])
      else:
        flag = 1
      if(flag == 1):
          flag = 0
          for k,l in DD:
              if(x+k<0 or y+l<0 or x+k>W-1 or y+l>H-1):
                  continue
              dist = G[y+l][x+k]
              #print(G[y][x])
              if(G[y+l][x+k] != "#"):
                  if(type(G[y+l][x+k]) is str):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])
                  elif(dist>G[y][x]+1):
                      G[y+l][x+k] = G[y][x]+1
                      que.append([y+l,x+k])

sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H, W = map(int, input().split())
magicY, magicX = map(int, input().split())
goalY, goalX = map(int, input().split())
G = [list(input()) for i in range(H)]
G[magicY-1][magicX-1] = 0
ans = 0

#print(G[magicX-1][magicY-1])

bfs(magicX-1, magicY-1)

if(G[goalY-1][goalX-1]=="."):
    print(-1)
else:
    print(G[goalY-1][goalX-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)

Submission status: Accepted

Solution code:
import collections

R, C = map(int, input().split())
sy, sx = map(lambda n: int(n) - 1, input().split())
gy, gx = map(lambda n: int(n) - 1, input().split())
c = [input() for _ in range(R)]

dist = [[-1 for _ in range(C)] for _ in range(R)]

q = collections.deque([(sy, sx, -1)])


G =     [(-2, -2),
 (-2, -1),
 (-2, 0),
 (-2, 1),
 (-2, 2),
 (-1, -2),
 (-1, -1),
 (-1, 1),
 (-1, 2),
 (0, -2),
 (0, 2),
 (1, -2),
 (1, -1),
 (1, 1),
 (1, 2),
 (2, -2),
 (2, -1),
 (2, 0),
 (2, 1),
 (2, 2)] 

while q:
    y, x, d = q.popleft()

    if y < 0 or R <= y or x < 0 or C <= x:  # out of range
        continue

    if c[y][x] == '#':  # unable to visit
        continue

    if dist[y][x] != -1:  # not the first time to visit
        continue

    dist[y][x] = d + 1
    
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        q.appendleft((y + i, x + j, d ))
    for i,j in G:
        q.append((y+i,x+j,d+1))
print(dist[gy][gx])

Submission status: Accepted

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

    while q:
        while q:
            y, x = q.popleft()
            q_warp.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])

        while q_warp:
            y, x = q_warp.popleft()
            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
                        q.append([ny,nx])

    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(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

cost = [[-1]*w for i in range(h)]

from collections import deque
q = [[0,ch,cw]]
q = deque(q)

ans = -1
while q:
    cnt,cx,cy = q.popleft()
    if cost[cx][cy]<0:
        cost[cx][cy]=cnt
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=cx+dx<h and 0<=cy+dy<w and s[cx+dx][cy+dy]=='.':
                    if cost[cx+dx][cy+dy]<0:
                        if [dx,dy] in [[1,0],[-1,0],[0,1],[0,-1]]:
                            q.appendleft([cnt,cx+dx,cy+dy])
                        else:
                            q.append([cnt+1,cx+dx,cy+dy])

print(cost[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

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



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    m_queue = deque([])
    while queue or m_queue:
        if queue:
            y, x = queue.popleft()
        else:
            n_y, n_x, y, x = m_queue.popleft()
            if visited[n_y][n_x] != -1:
                continue
            visited[n_y][n_x] = visited[y][x] + 1
            y, x = n_y, n_x
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x]
                queue.append([n_y, n_x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                        m_queue.append([n_y, n_x, y, x])
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

visited = [[0 for j in range(W)] for i in range(H)]
seen = [[0 for j in range(W)] for i in range(H)]
done = set()

def bfs(u, done):
    stack = deque([u])
    seen[u[0]][u[1]] = 1

    while len(stack) > 0:
        v = stack.popleft()
        done.add(v)
        visited[v[0]][v[1]] = 1
        ###
        w1 = (v[0] + 1, v[1])
        w2 = (v[0] , v[1] + 1)
        w3 = (v[0] - 1, v[1])
        w4 = (v[0] , v[1] -1)
        ###

        ws = [w1,w2,w3,w4]

        for w in ws:
            if w[0] >= 0 and w[0] < H and w[1] >= 0 and w[1] < W:
                if S[w[0]][w[1]] == ".":
                    if seen[w[0]][w[1]] == 0:
                        stack.append(w)
                        seen[w[0]][w[1]] = 1

bfs((Ch-1,Cw-1), done)

count = 0
# print("d",done)
# for i in range(H):
#     print(visited[i])

while True:
    if visited[Dh-1][Dw-1] == 1:
        print(count)
        sys.exit()
    else:
        count += 1
        pp = deque([])
        for d in list(done):
            i = d[0]
            j = d[1]
            for k in range(-2,3):
                for l in range(-2,3):
                    if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
                        if S[i+k][j+l] == ".":
                            if visited[i+k][j+l] == 0:
                                pp.append((i+k,j+l))

        if len(pp) == 0:
            print(-1)
            break

        done = set()
        for ppp in pp:
            bfs(ppp, done)

Submission status: Accepted

Solution code:
from collections import deque

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

group=[[-1 for j in range(W)] for i in range(H)]

g=0

def bfs(x,y):
    global g
    group[x][y]=g
    deq=deque([(x,y)])
    while deq:
        h,w=deq.popleft()
        for i in range(-1,2):
            for j in range(-1,2):
                if i*j==0 and (i,j)!=(0,0) and 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=="." and group[h+i][w+j]==-1:
                    group[h+i][w+j]=g
                    deq.append((h+i,w+j))
    g+=1

for i in range(H):
    for j in range(W):
        if group[i][j]==-1 and S[i][j]==".":
            bfs(i,j)

edge=[[] for i in range(g)]

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            for k in range(-2,3):
                for l in range(-2,3):
                    if 0<=i+k<H and 0<=j+l<W and group[i+k][j+l]!=-1:
                        edge[group[i][j]].append(group[i+k][j+l])

dist=[10**18 for i in range(g)]
dist[group[Ch][Cw]]=0
deq=deque([group[Ch][Cw]])
while deq:
    v=deq.popleft()
    for nv in edge[v]:
        if dist[nv]>dist[v]+1 and nv!=-1:
            dist[nv]=dist[v]+1
            deq.append(nv)

if dist[group[Dh][Dw]]!=10**18:
    print(dist[group[Dh][Dw]])
else:
    print(-1)