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
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) - 1, input().split()))
    G = list(map(lambda x: int(x) - 1, input().split()))
    A = [list(input()) for _ in range(h)]
    INF = 100000000
    score = [[INF] * w for _ in range(h)]
    score[S[0]][S[1]] = 0
    visited = [[False] * w for _ in range(h)]
    stack = deque([S])
    dxy = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    while stack:
        y, x = stack.popleft()
        if visited[y][x]:
            continue
        else:
            visited[y][x] = True
        count = 0
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if Y < 0 or Y >= h or X < 0 or X >= w:
                continue
            elif A[Y][X] == '.':
                stack.appendleft([Y, X])
                score[Y][X] = min(score[Y][X], score[y][x])
        if count == 0 and A[y][x] == '.':
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + j
                    Y = y + i
                    if Y < 0 or Y >= h or X < 0 or X >= w:
                        continue
                    if A[Y][X] == '.':
                        stack.append([Y, X])
                        score[Y][X] = min(score[Y][X], score[y][x] + 1)
    print(s) if (s := score[G[0]][G[1]]) != INF else print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]

  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.append([u,score])
  #print(reach)

  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

for i in range(H):
    list1 = list(input())
    maze.append(list1)

for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                maze[y][x] = math.inf

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

while que:
    y, x = que.popleft()
    for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
        nexty, nextx = y + i , x + j
        if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
            dist = maze[nexty][nextx]
            if dist != '#':
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x]
                    que.append([nexty,nextx])
            else:
                for k in range(-2, 3):
                    if y + k >= 0 and y + k < H:
                        for l in range(-2, 3):
                            if x + l >= 0 and x + l < W and maze[y + k][x + l] != '#':
                                if maze[y + k][x + l] > maze[y][x] + 1:
                                    maze[y + k][x + l] = maze[y][x] + 1
                                    que.append([y + k,x + l])

if maze[Dh - 1][Dw - 1] != math.inf:
    print(maze[Dh - 1][Dw - 1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

sy-=1
sx-=1
gy-=1
gx-=1

C = [list(input()) for i in range(H)]

from collections import deque
task_list = deque([])

def bfs(y,x,count):#関数にしない方がわかりやすいかも

    if x<0 or y<0 or x>=W or y>=H:
        return#何もしない

    if C[y][x]=="#":
        return#何もしない
    elif C[y][x]==".":
        C[y][x]=str(count)#既に訪れたことを把握する必要あり
        task_list.append([y+1,x,count])
        task_list.append([y-1,x,count])
        task_list.append([y,x-1,count])
        task_list.append([y,x+1,count])
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                if x+i<0 or y+j<0 or x+i>=W or y+j>=H:
                    continue#何もしない
                if C[y+j][x+i]=="#":
                    continue
                elif C[y+j][x+i]=="." or int(C[y+j][x+i])>count+1:
                    task_list.append([y+j,x+i,count+1])
    elif int(C[y][x]) > count:
        C[y][x]=str(count)#既に訪れたことを把握する必要あり
        task_list.append([y+1,x,count])
        task_list.append([y-1,x,count])
        task_list.append([y,x-1,count])
        task_list.append([y,x+1,count])
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                if x+i<0 or y+j<0 or x+i>=W or y+j>=H:
                    continue#何もしない
                if C[y+j][x+i]=="#":
                    continue
                elif C[y+j][x+i]=="." or int(C[y+j][x+i])>count+1:
                    task_list.append([y+j,x+i,count+1])
    
y=sy
x=sx
count=0
C[y][x]=str(count)#既に訪れたことを把握する必要あり
task_list.append([y+1,x,count])
task_list.append([y-1,x,count])
task_list.append([y,x-1,count])
task_list.append([y,x+1,count])
for i in range(-2,3,1):
    for j in range(-2,3,1):
        if x+i<0 or y+j<0 or x+i>=W or y+j>=H:
            continue#何もしない
        if C[y+j][x+i]=="#":
            continue
        elif C[y+j][x+i]=="." or int(C[y+j][x+i])>count+1:
            task_list.append([y+j,x+i,count+1])

while(len(task_list)):
    y,x,t = task_list.popleft()
    bfs(y,x,t)

if C[gy][gx]==".":
    print(-1)
else:
    print(C[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    data = data.reshape(-1)
    visited = np.zeros(data.shape)
    distance = np.zeros(data.shape, dtype=np.int16)
    jump = np.zeros(data.shape, dtype=np.int16)
    from collections import deque

    HEIGHT = H + 4
    WIDTH = W + 4
    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = deque()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if visited[p]:
                continue
            if p == goal:
                return currentDistance
            distance[p] = currentDistance
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    jump[p + dx + dy] = currentDistance + 1
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d]:
                    q.append(p + d)

        # no continuous cell
        for i in range(HEIGHT * WIDTH):
            if not data[i]:
                continue
            if visited[i]:
                continue
            # not visited vacant cell
            if jump[i] > 0:
                q.append(i)
        currentDistance += 1
        if not q:
            return -1

    # print(distance)
    # print(visited.reshape((H+4, -1)))


def main():
    global data
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    data = np.array(list(read()))
    data = np.equal(data, 46).reshape((H, W + 1))
    D = np.zeros((H + 4, W + 4), dtype=np.int8)
    D[2:2+H, 2:2+W+1] = data
    # print(data)
    # print(D)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = [(0, Si-1, Sj-1, 0)]
heapify(que)
visited = set()

while que:
    priority, r, c, count = heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    elif (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        heappush(que, (priority+1, r+td, c+lr, count))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            heappush(que, (priority+5, r+ud, c+lr, count+1))

print('-1')

Submission status: Time Limit Exceeded

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = [(2,0),(2,1),(2,2),(1,2),(0,2),(-1,2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(2,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh, dw in self.move2:
                            r = (h + dh, w + dw)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set != deque([]):
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

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

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(1000)]
memo[0][Ch-1][Cw-1] = True

ans = -1

while d:
    h, w, c = d.popleft()

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[c][h+i][w+j]:
                    memo[c][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[c][h+i][w+j] and not memo[c+1][h+i][w+j]:
                        memo[c+1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)

Submission status: Time Limit Exceeded

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
    count = 0
    
    while queue:
        while queue:
            now = queue.popleft()
            for u in adj[now]:
                if visit[u] < 0:
                    queue.append(u)
                    visit[u] = visit[now]
        # print(count, visit)
        for i in range(W*H):
            if visit[i] == count:
                queue.append(i)
        
        while queue:
            now = queue.popleft()
            for u in worp[now]:
                if visit[u] < 0:
                    # queue.append(u)
                    visit[u] = visit[now]+1
        # print(count, visit)
        count += 1

        for i in range(W*H):
            if visit[i] == count:
                queue.append(i)
    
    print(visit[goal])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0
pool = [tuple(C)]

while(pool):
    y, x = pool.pop()
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.append((y+dy, x+dx))
            if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((y+dy, x+dx))

print(V[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))

heap = [(0,s)]
r = [[+float('inf') for i in range(w)] for _ in range(h)]
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0]+i,u[1]+j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u:
					ret.append(v)
	return ret


while(heap):
	d,u = heapq.heappop(heap)
	if d > r[u[0]][u[1]]: continue
	r[u[0]][u[1]] = min(r[u[0]][u[1]], d)
	if u == t:
		break

	for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
		if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
			if r[v[0]][v[1]] > d:
				heapq.heappush(heap,(d,v))
				r[v[0]][v[1]] = d
	for v in neighbors(u,mat):
		
		if 0 <= v[0] < h and 0 <= v[1] < w:
			if r[v[0]][v[1]] > d:
				heapq.heappush(heap,(d+1,v))
				r[v[0]][v[1]] = d + 1

print (r[t[0]][t[1]] if r[t[0]][t[1]]  < float('inf') else -1)

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

que = deque([[Ch-1,Cw-1]])
while 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
                    que.append([nextx,nexty])
                    
if ans[Dh-1][Dw-1]==1000000:
    print("-1")
else:
    print(ans[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    G = [[H*W]*W for i in range(H)]
    # q.append((Ch, Cw))
    G[Ch][Cw] = 0
    flag = True
    # while(q):
    #     x, y = q.popleft()
    #     # for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
    #     #     if 0 <= i <= H and 0 <= j <= W and S[i][j] != '#' and G[i][j] == -1:
    #     if x == Dh and y == Dw:
    #         print(G[x][y])
    #         flag = False
    #         break
    #     for i in range(x-2, x+3):
    #         if 0 <= i <= H-1:
    #             for j in range(y-2, y+3):
    #                 if 0 <= j <= W-1:
    #                     if S[i][j] != '#':
    #                         if abs(i-x) + abs(j-y) == 1 and G[i][j] > G[x][y]:
    #                             q.append((i, j))
    #                             G[i][j] = G[x][y]
    #                         elif G[i][j] > G[x][y] + 1:
    #                             q.append((i, j))
    #                             G[i][j] = G[x][y] + 1

    #     # for i in range(H):
    #     #     print(G[i])
    #     # print()
    r = set()
    ss = []
    start = -1
    goal = -1
    # D = collections.defaultdict(int)
    D = dict()
    for i in range(H):
        for j in range(W):
            if (i, j) in r or S[i][j] == '#':
                continue
            q.append((i, j))
            ss.append(set([(i, j)]))
            r.add((i, j))
            L = len(ss)
            D[(i, j)] = L-1
            while(q):
                x, y = q.popleft()
                for k, l in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                    if 0 <= k <= H-1 and 0 <= l <= W-1 and S[k][l] != '#' and (k, l) not in r:
                        r.add((k, l))
                        D[(k, l)] = L - 1
                        q.append((k, l))
                        ss[-1].add((k, l))
            if start == -1 and (Ch, Cw) in ss[-1]:
                start = L - 1
            if goal == -1 and (Dh, Dw) in ss[-1]:
                goal = L - 1

    if D[Ch, Cw] == D[(Dh, Dw)]:
        print(0)
        exit(0)

    G = [set() for i in range(L)]
    for id, X in enumerate(ss):
        for x, y in X:
            for i in range(x-2, x+3):
                if 0 <= i <= H-1:
                    for j in range(y-2, y+3):
                        if 0 <= j <= W-1:
                            if S[i][j] != '#' and D[(i, j)] != id:
                                G[id].add(D[(i, j)])

    r = set()
    r.add(start)
    q.append((start, 0))
    while(q):
        x, c = q.popleft()
        if x == goal:
            print(c)
            flag = False
            break
        for y in G[x]:
            if y in r:
                continue
            else:
                r.add(y)
                q.append((y, c+1))
    # print(G)
    if flag:
        print(-1)


main()

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

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
while queue:
    y, x,wapu = queue.popleft()
    dist[y][x] = wapu
    for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue       
            else:
                 new_wapu= wapu +1
            if new_wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = new_wapu
                queue.append([new_y, new_x,new_wapu])
ans = dist[dh-1][dw-1]
if ans == inf:
  print(-1)
else:
  print(dist[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())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
dist = [[-1]*w for i in range(h)]

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

def Dijkstra(ch, cw):
    """
    Dijkstra法を用いて単一始点終点の最短コストを算出する
    0オリジンとする。
    es: 辺を表す配列。
        es[start]: [cost, en]
    n: 頂点数
    source: 始点
    return: dist　最短距離距離配列。
    """
    import heapq
    used = [[False] * w for i in range(h)] # Falseならば計算対象
    edgelist = []
    # 始点の辺を追加
    for e in d:
        c, y, x = e
        if 0<=ch+y<h and 0<=cw+x<w:
            if used[ch+y][cw+x]: continue
            if area[ch+y][cw+x]=='#': continue
            heapq.heappush(edgelist, (c, ch+y, cw+x))
    used[ch][cw] = True
    dist[ch][cw] = 0
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        cost, y, x = minedge
        if used[y][x]:
            continue
        dist[y][x] = cost
        used[y][x] = True
        for e in d:
            next_cost, next_y, next_x = e
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if used[y+next_y][x+next_x]: continue
                if area[y+next_y][x+next_x]=='#': continue
                heapq.heappush(edgelist, (dist[y][x]+next_cost, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
print(dist[dh][dw])

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())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop()
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    if not (dot[1] - 1 < 0):
        queue.append([dot[0],dot[1]-1,dot[2]])
    if not (dot[1] + 1 >= w):
        queue.append([dot[0],dot[1]+1,dot[2]])
    if not (dot[0]+1 >= h):
        queue.append([dot[0]+1,dot[1],dot[2]])
    if not (dot[0]-1 < 0):
        queue.append([dot[0]-1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            if not(dot[0]+ x < 0 or dot[1]+y < 0 or dot[0]+x >= h or dot[1]+y >= w):
                if not(used_map[dot[0]+x][dot[1]+y] > -1 and used_map[dot[0]+x][dot[1]+y] <= dot[2]+1):
                    queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])