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: Wrong Answer

Solution code:
from copy import deepcopy

H, W = map(int,input().split())
Ch1, Cw1 = map(int,input().split())
Dh1, Dw1 = map(int,input().split())

Ch = Ch1 -1
Cw = Cw1 -1

Dh = Dh1 - 1
Dw = Dw1 - 1


def finding(a,b): #(a,b)から5マス以内に数字マスがあるか索敵
    if type(T[a][b]) == int:
        return T[a][b]
    else:
        V = []
        for i in range(-5,6):
            for j in range(-(5 - abs(i)), 6 - abs(i)):
                if type(T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]) == int:
                    V += [T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]]
        if V != []:
            return min(n + 1 for n in V)
        else:
            return T[a][b]
            


i = 0
S = []
while i < H:
    s= map(list,input().split())
    li = list(s)
    S += li
    i += 1

T = deepcopy(S)
T[Ch][Cw] = 0
U = []
while T!= U:
    while T != U:
        U = deepcopy(T)
        for i in range(H):
            for j in range(W):
                if T[i][j] != '#':
                    if type(T[max(i-1,0)][max(j-1,0)]) == int:
                        T[i][j] = T[max(i-1,0)][max(j-1,0)]
                    if type(T[max(i-1,0)][min(j+1,W-1)]) == int:
                        T[i][j] = T[max(i-1,0)][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][min(j+1,W-1)]) == int:
                        T[i][j] = T[min(i+1,H-1)][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][max(j-1,0)]) == int:
                        T[i][j] = T[min(i+1,H-1)][max(j-1,0)]
    for a in range(H):
        for b in range(W):
            if T[a][b] != '#':
                T[a][b] = finding(a,b)


if T[Dh][Dw] == '.':
    print(-1)
else:
    print(T[Dh][Dw])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c1,c2 = map(int,input().split())
import sys
sys.setrecursionlimit(200000)
c1 -= 1
c2 -= 1
d1,d2 = map(int,input().split())
d1 -= 1
d2 -= 1
INF = 10**7
s = [list(input()) for _ in range(h)]
num = list([INF for i in range(w)] for _ in range(h))
bit = list( [0 for _ in range(w)] for _ in range(h))
num[c1][c2] = 0
bit[c1][c2] = 1


def dfs(j,k):
    tate = [0,1,0,-1]
    yoko = [1,0,-1,0]
    for i in range(4):
        if 0<= j+tate[i] and j+tate[i]<=h-1 and 0<=k +yoko[i] and k +yoko[i] <= w-1:
            if s[j+tate[i]][k+yoko[i]]== "." and bit[j+tate[i]][k+yoko[i]]==0:
                bit[j+tate[i]][k+yoko[i]] = 1
                num[j+tate[i]][k+yoko[i]]= min(num[j+tate[i]][k+yoko[i]], num[j][k])

                dfs(j+tate[i],k+yoko[i])


    for a in range(-2,3):
        for b in range(-2,3):
            if 0<= j+a and j+a<=h-1 and 0<=k+b and k+b <= w-1:
                if s[j+a][k+b]== "." and bit[j+a][k+b]==0:
                    bit[j+a][k+b]= 1
                    num[j+a][k+b]= min( num[j+a][k+b] , num[j][k]+1)
                    
                    dfs(j+a,k+b)

dfs(c1,c2)
if num[d1][d2]== 10**7:
    print(-1)
else:
    print(num[d1][d2])

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
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)]
# print(S)
C[0]-=1
C[1]-=1
D[0]-=1
D[1]-=1

a=[-2,-1,0,1,2]
wk={(1,0),(-1,0),(0,1),(0,-1)}
wp=set(product(a,a)).difference(wk)
wp-={(0,0)}
# print(wp)

ans=[[float('inf')]*W for _ in range(H)]
seen=[[False]*W for _ in range(H)]
ct=-1


def DFS_walk(ct):
    while len(stk_walk)>0:
        l=stk_walk.pop()
        # print(l)
        i=l[0]
        j=l[1]
        if ans[i][j]<=ct:
            return
        if i == D[0] and j == D[1]:
            ans[i][j]=min(ans[i][j], ct)
        ans[i][j] = ct
        S[i][j] = '#'
        for mv in wk:
            x = i+mv[0]
            y = j+mv[1]
            if 0 <= x < H and 0 <= y < W and S[x][y] == '.':
                stk_walk.append([x,y])
        for mv in wp:
            x = i+mv[0]
            y = j+mv[1]
            if 0 <= x < H and 0 <= y < W and S[x][y] == '.':
                stk_warp.append([x,y,ct])
        # print(stk_walk)
    return

stk_walk=deque([])
stk_warp=deque([[C[0], C[1], ct]])

# test
# stk_walk.append(C)
# DFS_walk(0)
# print(ans)

while len(stk_warp)>0:
    k=stk_warp.popleft()
    # print(k)
    if ans[D[0]][D[1]]<float('inf'):
        print(ans[D[0]][D[1]])
        exit()
    k[2]+=1
    stk_walk.append([k[0], k[1]])
    DFS_walk(k[2])
    # print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
class G:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False
        self.range = 0

    
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [['.' for j in range(W)] for i in range(H) ]
for i in range(H):
    tmp = list(input())
    for j in range(W):
        S[i][j] = G(tmp[j])

def neighbors(y, x):
    s = []
    if x != 0:
        if S[y][x-1].reached == False and S[y][x-1].c == '.':
            s.append((y, x-1))
    if x != W-1:
        if S[y][x+1].reached == False and S[y][x-1].c == '.':
            s.append((y, x+1))
    if y != 0:
        if S[y-1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y-1, x))
    if y != H-1:
        if S[y+1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y+1, x))
    return s

def jump(x, y, d):
    S[y][x].searched = True
    for i in range(max(x-2, 0), min(x+3, W)):
        for j in range(max(y-2, 0), min(y+3, H)):
            if S[j][i].reached == False and S[j][i].c == '.':
                d.append((j, i))

def DFS(S, d):
    while True:
        if len(d) == 0:
            break
        q = d.popleft()
        S[q[0]][q[1]].reached = True
        for each in neighbors(q[0], q[1]):
            S[each[0]][each[1]].reached = True
            if S[each[0]][each[1]].c == '.':
                d.append(each)

counter = 0
d = deque([])
S[Ch][Cw].reached = True
d.append((Ch, Cw))
flag = False
while True:
    DFS(S, d)
    if S[Dh][Dw].reached:
        break
    counter += 1
    for i in range(H):
        for j in range(W):
            if S[i][j].reached and S[i][j].c == '.' and S[i][j].searched == False:
                jump(j, i, d)

    if len(d) == 0:
        flag = True
        break

if flag:
    print(-1)
else:
    print(counter)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
grid = [input() for i in range(h)]
done = [[0]*w for _ in range(h)]
dxdy = [[0,1],[1,0],[-1,0],[0,-1]]
def search5(i,j):#周辺にゴールがあるか
    if dw < i+2 and dw > i-2 and dh < i+2 and dh > i-2:
        return True
    else:
        return False

def ok(i,j):
    if i>-1 and j>-1 and i<h and j<w and grid[i][j]==".":
        return True
    else:
        return False
lis = []
ind = 0
def dfs(i,j):
    if(i==dh-1 and j==dw-1):
        lis.append([i,j])
        done[i][j]=1
        return True
    elif(not done[i][j]):
        lis.append([i,j])
        done[i][j]=1
        for dx,dy in dxdy:
            if(ok(i+dy,j+dx)):
                dfs(i+dy,j+dx)

    return False
vertex_set = []
res = 0
for i in range(h):
    for j in range(w):
        if(grid[i][j]=="." and done[i][j]==0):
            dfs(i,j)
            vertex_set.append(lis)
            lis = []

Submission status: Wrong Answer

Solution code:
[H,W]=[int(_) for _ in input().split()]
C=[int(_)-1 for _ in input().split()]
D=[int(_)-1 for _ in input().split()]
S=[]
for h in range(H):
  S.append(input())

#for h in range(H):
#  for w in range(W):
#    print(S[h][w])

def wA(c):
  x=c[0]
  y=c[1]
  ans=[]
  try:
    xx = x-1; yy = y; 
    if 0 <= xx < H and 0 <= yy < W:
      if S[xx][yy] == '.': ans.append([xx,yy])
    xx = x+1; yy = y; 
    if 0 <= xx < H and 0 <= yy < W:
      if S[xx][yy] == '.': ans.append([xx,yy])
    xx = x; yy = y-1; 
    if 0 <= xx < H and 0 <= yy < W:
      if S[xx][yy] == '.': ans.append([xx,yy])
    xx = x; yy = y+1; 
    if 0 <= xx < H and 0 <= yy < W:
      if S[xx][yy] == '.': ans.append([xx,yy])
  except:
    pass
  return ans

def wB(c):
  x=c[0]
  y=c[1]
  ans=[]
  try:
    for nh in [-2,-1,0,1,2]:
      for nw in [-2,-1,0,1,2]:
        if nh == 0 and nw == 0: continue
        xx = x+nh
        yy = y+nw
        if 0 <= xx < H and 0 <= yy < W:
          if S[xx][yy] == '.': ans.append([xx,yy])
  except:
    pass
  return ans

r = -1

#print(C)
#print(wA(C))
#print(wB(C))
#print(D)

if D in wB(C): r = 1
  
print(r)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ['#' * (H + 4)]
S.append('#' * (H + 4))
for _ in range(H):
    S.append('##' + input() + '##')
S.append('#' * (H + 4))
S.append('#' * (H + 4))

mapping = [[-1] * (W + 4) for _ in range(H + 4)]

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


def dfs_0(i, j):
    if S[i][j] == '#' or mapping[i][j] != -1:
        return
    mapping[i][j] = 0
    dfs_0(i - 1, j)
    dfs_0(i + 1, j)
    dfs_0(i, j - 1)
    dfs_0(i, j + 1)


dfs_0(Ch, Cw)

near = [[1, 0], [-1, 0], [0, 1], [0, -1]]
warp = [[-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]]
flag = [0]
count = 0


def dfs(i, j):
    if S[i][j] == '#' or mapping[i][j] != -1:
        return
    mapping[i][j] = count + 1
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)


while mapping[Dh][Dw] == -1 and flag[0] == 0:
    flag[0] = 1
    for i in range(2, H + 2):
        for j in range(2, W + 2):
            if S[i][j] == '.' and mapping[i][j] == -1:
                for n in range(20):
                    if mapping[i + warp[n][0]][j + warp[n][1]] == count:
                        mapping[i][j] = count + 1
                        flag[0] = 0
                        break
            if mapping[i][j] == count + 1:
                dfs(i, j)
    count += 1

print(mapping[Dh][Dw])

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  while len(q):
    y,x=q.popleft()
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
ch-=1
cw-=1
dh,dw=nii()
dh-=1
dw-=1
s=[list(input()) for i in range(h)]

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

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

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    t_cnt=0
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.append((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]
        t_cnt+=1
    if t_cnt==0:
      for dy,dx 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]]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
#          s[ny][nx]='#'
          dist[ny][nx]=dist[y][x]+1

dist[ch][cw]=0

que=deque()
que.append((ch,cw))

BFS(que)

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-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)]
 
M = []
for i in range(H):
    M.append([10**3] * W)
M[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] == ".":
            if M[h+dh][w+dw] > M[h][w]:
                M[h+dh][w+dw] = M[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] == ".":
            if M[h+wh][w+ww] > M[h][w] + 1:
                M[h+wh][w+ww] = M[h][w] + 1
                q.append((h+wh, w+ww))
 
if M[DH-1][DW-1] == 10**3:
    print(-1)
else:
    print(M[DH-1][DW-1])

Submission status: Wrong Answer

Solution code:
import collections

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

g = {}

def dump():
    print('map')
    for row in s:
        print(''.join(row))
    print('graph')
    print(g)
    print()

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

deq = collections.deque()
ident = 0
def reveal_cluster():
    global ident
    while len(deq):
        x, y, no = deq.popleft()
        if not check_range(x, y):
            continue
        if s[x][y] != '.':
            continue
        
        if no is None:
            ident += 1
            g[ident] = set()

        s[x][y] = str(ident)

        # 移動A
        for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
            nx, ny = x + dx, y + dy
            if check_range(nx, ny) and s[nx][ny] == '.':
                deq.append((nx, ny, ident))

deq.append((ch - 1, cw - 1, None))
reveal_cluster()

deq.append((dh - 1, dw - 1, None))
reveal_cluster()

for i in range(h):
    for j in range(w):
        deq.append((i, j, None))
        reveal_cluster()
#dump()

def check_cluster_connectivity():
    while len(deq):
        x, y, prev = deq.popleft()

        if not (0 <= x < h) or not (0 <= y < w):
            continue
        if s[x][y] == '#':
            continue

        curr = s[x][y]
        curr = int(curr)
        if prev is not None and curr != prev:
            # warpできる
            k = int(s[x][y])
            g[prev].add(k)

        _prev = int(s[x][y])

        s[x][y] = '#'

        # 移動B
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if check_range(nx, ny) and s[nx][ny] != '#' and s[nx][ny] != s[x][y]:
                    v = (nx, ny, _prev)
                    deq.append(v)

for i in range(h):
    for j in range(w):
        v = (i, j, None)
        deq.append(v)
        check_cluster_connectivity()

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[pos] is not None:
        return
    dist[pos] = d
    for e in g[pos]:
        bfs(e, d + 1)

if len(g) == 1:
    # スタート = ゴール
    print(0)
elif len(g[1]) == 0:
    bfs(1, 0)
    
    a = dist[2]
    if a is None:
        # 経路なし
        print(-1)
    else:
        # 経路あり
        print(a)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

maze = [["#"] * 1100 for _ in range(1100)]
dist = [[-1] * 1100 for _ in range(1100)]
h, w = 0, 0


def dfs(x, y, cnt):
    global h, w
    global maze, dist
    dist[x][y] = cnt
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 1 <= nx <= h and 1 <= ny <= w and maze[nx][ny] == "." and dist[nx][ny] == -1:
            dfs(nx, ny, cnt)


def main():
    global h, w
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    global maze, dist
    for i in range(1, h + 1):
        line = input()
        for j in range(1, w + 1):
            if line[j - 1] == ".":
                maze[i][j] = "."
    dfs(ch, cw, 0)

    cnt = 1
    fin = False
    while not fin:
        fin = True
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if dist[i][j] == cnt - 1:
                    for di, dj in permutations([-2, -1, 0, 1, 2], 2):
                        if abs(di) + abs(dj) <= 1:
                            continue
                        ni = i + di
                        nj = j + dj
                        if 1 <= ni <= h and 1 <= nj <= w:
                            if dist[ni][nj] == -1 and maze[ni][nj] == ".":
                                dfs(ni, nj, cnt)
                                fin = False
        cnt += 1
    print(dist[dh][dw])


if __name__ == "__main__":
    main()