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:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
    [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
    [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
    [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
q = deque([[ch, cw]])
one_time = deque()
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dd = [(1,0),(0,1),(-1,0),(0,-1)]
h,w = inpl()
cy,cx = inpl()
gy,gx = inpl()
cy,cx,gy,gx = cy-1,cx-1,gy-1,gx-1
s = [input() for _ in range(h)]
res = [[INF] * w for _ in range(h)]
q = deque([(cy,cx)])
res[cy][cx] = 0
while q:
    oy,ox = q.popleft()
    for dy in range(-2,3):
        for dx in range(-2,3):
            ny = dy + oy
            nx = dx + ox
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == '.':
                f = False
                if (dy,dx) in dd:
                    if res[ny][nx] > res[oy][ox]:
                        f = True
                        res[ny][nx] = min(res[ny][nx], res[oy][ox])
                else:
                    if res[ny][nx] > res[oy][ox] + 1:
                        f = True
                        res[ny][nx] = min(res[ny][nx], res[oy][ox] + 1)
                if f: q.append((ny,nx))
print(res[gy][gx] if res[gy][gx] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

def add_magic_move(enable_to_move_list):
  ret = list(enable_to_move_list)
  for h, w in enable_to_move_list:
    for target_h, target_w in product([h-1, h, h+1], [w-1, w, w+1]):
      if -1 < target_h < H and -1 < target_w < W and (target_h, target_w) not in enable_to_move_list:
        s[target_h][target_w] = '.'
        ret += [(target_h, target_w)]
  return ret
    

def get_enable_to_move_list(h, w, enable_to_move_list):
  if (h, w) in enable_to_move_list:
    return enable_to_move_list
  enable_to_move_list += [(h, w)]
  targets = ((h+1, w), (h-1, w), (h, w+1), (h, w-1))
  for h, w in targets:
    if -1 < h < H and -1 < w < W and s[h][w] == '.':
      enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  return enable_to_move_list

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]

enable_to_move_list = get_enable_to_move_list(s_h, s_w, [])
i = 0
while True:
  if (d_h, d_w) in enable_to_move_list:
    break
  tmp = add_magic_move(enable_to_move_list)
  i += 1
  for h, w in list(set(tmp) - set(enable_to_move_list)):
  	enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  if not set(tmp) ^ set(enable_to_move_list):
    i = -1
    break

print(i)

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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
    [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
    [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
    [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
    [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
    [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
    [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append((start,0))
dist[start] = 0

while dq:
    p,d = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    if d>dist[p]:
        continue
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dist[q] = dist[p]
                        dq.appendleft((q,dist[q]))
                else:
                    if dist[q]>dist[p]+1:
                        dist[q] = dist[p] + 1
                        dq.append((q,dist[q]))

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = [
    (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
    (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
    (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
    (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
    (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
q = deque()
one_time = deque()
q.append([ch, cw])
while len(q) > 0:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while len(one_time) > 0:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1


print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Time Limit Exceeded

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                warping = True
                if h == 0 == w:
                    continue
                if (h, w) in can_walk:
                    warping = False
                yield (h, w, warping)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        grid[h][w] = 'R'  # reached

        for h_delta, w_delta, warping in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if warping:
                        qu.append((new_h, new_w, warps + 1))
                    else:
                        qu.appendleft((new_h, new_w, warps))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

def add_magic_move(enable_to_move_list):
  ret = list(enable_to_move_list)
  for h, w in enable_to_move_list:
    for target_h, target_w in product([h-1, h, h+1], [w-1, w, w+1]):
      if -1 < target_h < H and -1 < target_w < W and (target_h, target_w) not in enable_to_move_list:
        s[target_h][target_w] = '.'
        ret += [(target_h, target_w)]
  return ret
    

def get_enable_to_move_list(h, w, enable_to_move_list):
  if (h, w) in enable_to_move_list:
    return enable_to_move_list
  enable_to_move_list += [(h, w)]
  targets = ((h+1, w), (h-1, w), (h, w+1), (h, w-1))
  for h, w in targets:
    if -1 < h < H and -1 < w < W and s[h][w] == '.':
      enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  return enable_to_move_list

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]

enable_to_move_list = get_enable_to_move_list(s_h, s_w, [])
i = 0
while True:
  if (d_h, d_w) in enable_to_move_list:
    break
  tmp = add_magic_move(enable_to_move_list)
  i += 1
  for h, w in tmp:
  	enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  if not set(tmp) ^ set(enable_to_move_list):
    i = -1
    break

print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    
    mylist = [input().rstrip() for i in range(H)]
    dist = Init(H, W, float('inf'))
    #dist2 = Init(H, W, float('inf'))
    dq = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    while dq:
        x, y = dq.pop()
        #コスト1の移動
        for x2, y2 in move2:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]+1:
                dist[x2][y2] = dist[x][y]+1
                dq.append((x2,y2))
                
        #コスト0の移動
        for x2, y2 in move1:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]:
                dist[x2][y2] = dist[x][y]
                dq.append((x2,y2))
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1
cw+=1
dh+=1
dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        move2.append((i, j))
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = []
base.append(["#" for _ in range(w+4)])
base.append(["#" for _ in range(w+4)])
for n in range(h):
    s = list(input())
    s.append("#")
    s.append("#")
    s.insert(0, "#")
    s.insert(0, "#")
    base.append(s)
base.append(["#" for _ in range(w+4)])
base.append(["#" for _ in range(w+4)])
base = np.array(base)
ans = np.full_like(base, -1, dtype = int)
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1
cw+=1
dh+=1
dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        move2.append((i, j))
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
elif icase==1:
    h,w=4,4
    ch,cw=1,1
    dh,dw=4,4
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['..#.', '..#.', '.#..', '.#..']   
elif icase==2:
    h,w=4,4
    ch,cw=1,4
    dh,dw=4,1
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['.##.', '####', '####', '.##.']  
elif icase==3:
    h,w=4,5
    ch,cw=1,2
    dh,dw=2,5
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['#.###', '####.', '#..##', '#..##'] 
elif icase==4:
    h,w=4,4
    ch,cw=2,2
    dh,dw=3,3
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['....', '....', '....', '....']
        
icnt=-1
pair=[-1]*(h*w)
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            idx=i*w+j
#            pair.append(idx)
            pair[idx]=idx
#print("A",pair)
               
def root(x):
    if x==-1:
        return -1
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x
        
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                pair[idx1]=idx
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                pair[idx1]=idx

for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                unite(idx,idx1)
            if i>0 and s[i-1][j]==".":
                idx1=(i-1)*w+j
                unite(idx,idx1)
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                unite(idx,idx1)
            if j>0 and s[i][j-1]==".":
                idx1=i*w+j-1
                unite(idx,idx1)

#print("B:",pair)
l=[root(ii) for ii in range(len(pair))]
#print("l:",l)
ll=list(set(l))    
ll.sort()
ll=ll[1:]
if len(ll)<1:
    print(0)
    sys.exit()

gg=[[] for i in range(max(ll)+1)]
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if root(idx)!=-1:
            gg[root(idx)].append((i,j))        

ggg=[[] for i in range(max(ll)+1)]
for gi in gg:
    for gi2 in gg:
        if gi==gi2:
            continue
        yn=""
        for i,j in gi:
            idx=i*w+j
            for i2,j2 in gi2:
                idx2=i2*w+j2
                if root(idx2) in ggg[root(idx)]:
                    continue
                if abs(i-i2)<=2 and abs(j-j2)<=2:
                    ggg[root(idx)].append(root(idx2))
                    ggg[root(idx2)].append(root(idx))
                    yn="yes"
                    break
            if yn=="yes":
                break
            
#print("ll:",ll)
lenpair=len(ll)    
lenpair=max(ll)+1

qst=root(ch*w+cw)
qed=root(dh*w+dw)
q=deque([qst])

stack=[qst]
parent=[-1]*lenpair
parent[qst]=0
dist=[-1]*lenpair
dist[qst]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in ggg[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            if v==qed:
                print(dist[qed])   
                sys.exit()
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def chk():
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    
    for i,j in ((a+1,b),(a,b+1),(a-1,b),(a,b-1)):
        if s[i,j]=='.': 
            q.append([i,j])
            s[i,j]=int(s[a,b])
        elif [a,b] not in wq:
            wq.append([a,b])
    chk()
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    chk()
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)
bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    color[X][Y]="gray"
                    queue.appendleft([X,Y])

        for i in range(max(0,x-2),min(h,x+3)):
            for j in range(max(0,y-2),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black":
                        D[X][Y]=min(D[X][Y],D[x][y]+1)
                        color[X][Y]="gray"
                        queue.append([X,Y])
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)