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: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = min(table[dx][dy], table[x][y])
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = min(table[dx][dy], table[x][y]+1)

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 縦H X 横W マス
C = list(map(int, input().split()))  #[Ch, Cw]　　*1多いことに注意
D = list(map(int, input().split()))  #[Dh, Dw]　　*1多いことに注意
S = [list(input()) for _ in range(H)]  #Sij = S[i][j]  

T = deque([[C[0]-1,C[1]-1]])
ans = 0

# 繰り返し
while T:
    K = deque([])
    while T:
        y,x = T.popleft()
        if 0 <= y < H and 0 <= x < W and S[y][x] =="." :
            K.append([y,x])
            S[y][x] = "#"
            for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
                T.append([y+i,x+j])
    if [D[0]-1,D[1]-1] in K:
        print(ans)
        break
    ans += 1
    for z,w in K:
        for s_y in [-2,-1,0,1,2]:
                for s_x in [-2,-1,0,1,2]:
                    if 0 <= z+s_y < H and 0 <= w+s_x < W and S[z+s_y][w+s_x] ==".":
                        if not S[z+s_y][w+s_x] in K and not [z+s_y,w+s_x] in T:
                            T.append([z+s_y, w+s_x])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

queue = deque([[Ch-1, Cw-1, 0]])
inf = float("inf")
table = [[inf for i in range(W)] for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft([dx, dy, cost])
      table[dx][dy] = min(table[dx][dy], table[x][y])
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append([dx, dy, cost+1])
      table[dx][dy] = min(table[dx][dy], table[x][y]+1)

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

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(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[] for i in range(H)]
for i in range(H):
  st = input()
  for j in range(W):
    maze[i].append(st[j])
queue = deque([[Ch-1, Cw-1, 0]])
inf = float("inf")
table = [[inf for i in range(W)] for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft([dx, dy, cost])
      table[dx][dy] = min(table[dx][dy], table[x][y])
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append([dx, dy, cost+1])
      table[dx][dy] = min(table[dx][dy], table[x][y]+1)

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([(ch-1, cw-1, 0)])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append((nh, nw, cnt))
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack_append((nh, nw, cnt+1))

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

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

count = [[float("inf")] * W for _ in range(H)]

start = (ch - 1, cw -1)

def judge(start):
    if start in global_visited:
        return False
    if start[0] < 0 or H <= start[0]:
        return False
    if start[1] < 0 or W <= start[1]:
        return False
    # print(start)
    if S[start[0]][start[1]] == '#':
        return False
    return True

que = [start]
now_count = 0
while que:
    local_visited = []
    while que:
        start = que.pop()
        global_visited.append(start)
        local_visited.append(start)
        count[start[0]][start[1]] = now_count
        next_list = [
            (start[0], start[1] + 1),
            (start[0], start[1] - 1),
            (start[0] + 1, start[1]),
            (start[0] - 1, start[1]),
        ]
        for next in next_list:
            if judge(next):
                que.append(next)

    now_count += 1

    while local_visited:
        start = local_visited.pop()
        next_list = [
            (start[0] + 2, start[1] + 2),
            (start[0] + 2, start[1] + 1),
            (start[0] + 2, start[1] + 0),
            (start[0] + 2, start[1] - 1),
            (start[0] + 2, start[1] - 2),
            (start[0] + 1, start[1] + 2),
            (start[0] + 1, start[1] + 1),
            (start[0] + 1, start[1] - 1),
            (start[0] + 1, start[1] - 2),
            (start[0] + 0, start[1] + 2),
            (start[0] + 0, start[1] - 2),
            (start[0] - 1, start[1] + 2),
            (start[0] - 1, start[1] + 1),
            (start[0] - 1, start[1] - 1),
            (start[0] - 1, start[1] - 2),
            (start[0] - 2, start[1] + 2),
            (start[0] - 2, start[1] + 1),
            (start[0] - 2, start[1] + 0),
            (start[0] - 2, start[1] - 1),
            (start[0] - 2, start[1] - 2),
        ]
        for next in next_list:
            if judge(next):
                count[next[0]][next[1]] = now_count
                global_visited.append(next)
                que.append(next)

if count[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(count[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
CH, CW = map(int,input().split())
DH, DW = map(int,input().split())

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

d = [[INF for i in range(W)] for j in range(H)]

Q = deque([[CH-1, CW-1, 0]])
d[CH - 1][CW - 1] = 0

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    d[x][y] = cnt
    
    if x == DH - 1 and y == DW - 1:
        print(cnt)
        sys.exit()
    
    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and d[nx][ny] == INF:
                if abs(tx)+abs(ty) == 1:
                    Q.appendleft([nx, ny, cnt])
                elif abs(tx)+abs(ty) >= 2:
                    Q.append([nx, ny, cnt + 1])

print(-1)

Submission status: Time Limit Exceeded

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

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend(Edge(b, 0))
                    else:
                        esappend(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
CH, CW = map(int,input().split())
DH, DW = map(int,input().split())

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

d = [[INF for i in range(W)] for j in range(H)]

Q = deque([[CH-1, CW-1, 0]])
d[CH - 1][CW - 1] = 0

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    d[x][y] = cnt
    
    if x == DH - 1 and y == DW - 1:
        print(cnt)
        sys.exit()
    
    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and d[nx][ny] == INF:
                if abs(tx)+abs(ty) == 1:
                    Q.appendleft([nx, ny, cnt])
                else:
                    Q.append([nx, ny, cnt + 1])

print(-1)

Submission status: Time Limit Exceeded

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

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    a = h*W+w
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        es[a].append(Edge(b, 0))
                    else:
                        es[a].append(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

Submission status: Time Limit Exceeded

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

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = {i:[] for i in range(N)}

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    a = h*W+w
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        es[a].append(Edge(b, 0))
                    else:
                        es[a].append(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])