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:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)
# G = nx.Graph()
path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    path[h*W + w].append((0, new_h*W + new_w))
                    path[new_h*W + new_w].append((0, h*W + w))
                    # G.add_edge(h*W + w, new_h*W + new_w, weight=0)
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        path[h*W + w].append((1, new_h*W + new_w))
                        path[new_h*W + new_w].append((1, h*W + w))
                        # G.add_edge(h*W + w, new_h*W + new_w, weight=1)
            for dy, dx in MAGIC:
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    path[h*W + w].append((1, new_h*W + new_w))
                    path[new_h*W + new_w].append((1, h*W + w))
                    # G.add_edge(h*W + w, new_h*W + new_w, weight=1)

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
dist = dijkstra(path, N, c_h * W + c_w)
# length = nx.dijkstra_path_length(G, c_h * W + c_w, d_h*W+d_w)
print(dist[d_h*W+d_w])
# print(length)

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

dist = [[-1 for _ in range(W)] for _ in range(H)]
q = collections.deque([(Ch, Cw, 0)])
while q:
    y, x, c = q.pop()
    dist[y][x] = c
    if y == Dh and x == Dw:
        break

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny = y + dy
        nx = x + dx
        if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
            if S[ny][nx] == '.':
                q.append((ny, nx, c))

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                if S[ny][nx] == '.':
                    q.appendleft((ny, nx, c + 1))

print(dist[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
#from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
#from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
#from operator import itemgetter, mul
#from copy import deepcopy
#from string import ascii_lowercase, ascii_uppercase, digits
#from bisect import bisect, bisect_left, insort, insort_left
#from heapq import heappush, heappop
#from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


def main():
	H, W = MAP()
	Ch, Cw = MAP()
	Dh, Dw = MAP()
	S = [input() for _ in range(H)]

	cnt = [[INF]*W for _ in range(H)]
	cnt[Ch-1][Cw-1] = 0

	dy = [1, 0, -1, 0, 1, 1, -1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]
	dx = [0, -1, 0, 1, 1, -1, -1, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1]

	def wizard_cnt(start_y, start_x):
		q = deque([(start_y, start_x)])
		while q:
			y, x = q.pop()
			flg = True
			for i in range(24):
				if i == 4 and flg:
					break
				ny = y + dy[i]
				nx = x + dx[i]
				if ny < 0 or nx < 0 or H <= ny or W <= nx:
					continue
				elif i < 4:
					if S[ny][nx] == "." and cnt[y][x] < cnt[ny][nx]:
						cnt[ny][nx] = cnt[y][x]
						q.append((ny, nx))
					elif S[ny][nx] == "#":
						flg = False
				elif 4 <= i and S[ny][nx] == "." and cnt[y][x]+1 < cnt[ny][nx]:
					cnt[ny][nx] = cnt[y][x]+1
					q.append((ny, nx))

	wizard_cnt(Ch-1, Cw-1)

	if cnt[Dh-1][Dw-1] == INF:
		print(-1)
	else:
		print(cnt[Dh-1][Dw-1])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[float("inf")] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    stack = []
    warp_count[c_h][c_w] = 0
    stack.append((c_h, c_w, 0))

    while stack:
        _h, _w, warp = stack.pop()
        warp_count[_h][_w] = warp

        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                stack.append((_h + _a, _w + _b, warp))

        # warp
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x, y) in directions:
                    continue
                elif x == 0 and y == 0:
                    continue
                if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                    continue
                if grid[_h + x][_w + y] == "#":
                    continue
                if warp_count[_h + x][_w + y] > warp + 1:
                    stack.append((_h + x, _w + y, warp + 1))

    if warp_count[d_h][d_w] == float("inf"):
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch-1,cw-1)] = 0
    while q:
        nh, nw = q.popleft()
        now = c[(nh, nw)]
        for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            mh += nh
            mw += nw
            if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                c[(mh, mw)] = now
                q.appendleft((mh, mw))
        for i in range(-2, 3):
            i += nh
            for j in range(-2, 3):
                j += nw
                if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and s[i][j] == ".":
                    c[(i, j)] = now + 1
                    q.append((i, j))
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from itertools import product

H, W = map(int, input().split())
start = tuple(map(lambda x: int(x) - 1, input().split()))
goal = tuple(map(lambda x: int(x) - 1, input().split()))

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

serve = set()
visited = set()

Q = [(0, start)]
while Q:
    c, pos = heappop(Q)
    visited.add(pos)
    if pos == goal:
        print(c)
        exit()
    # A
    for move in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    heappush(Q, (c, (nx, ny)))
    # B
    for move in product(range(-2, 3), repeat=2):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in serve | visited:
                    heappush(Q, (c + 1, (nx, ny)))
                    serve.add((nx, ny))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
Sx,Sy=map(int,input().split())
Gx,Gy=map(int,input().split())
Sx-=1
Sy-=1
Gx-=1
Gy-=1
tmp=False
check=deque()
hit=set()

M=[[0 if j=='.' else 1 for j in input()]for i in range(H)]

# 0通路 1壁 2確認済み

ans=0
check.append([Sx,Sy])
while True:
    while check:
        x,y = check.pop()
        #goul
        if x==Gx and y==Gy:
            tmp=True
            break
        M[x][y]=2
        #壁があるか
        for dx,dy in [ [x+1,y],[x-1,y],[x,y-1],[x,y+1] ]:
            if not(0<=dx and dx<H and 0<=dy and dy<W):
                continue
            if M[dx][dy]==1:
                hit.add((x,y))
            if M[dx][dy]==0:
                check.append([dx,dy])
    if tmp:
        print(ans)
        break
    if len(hit)==0:
        print(-1)
        break
    for e in hit:
        x,y=e
        for i in range(-2,3):
            for j in range(-2,3):
                if 0<=x+i and x+i<H and 0<=y+j and y+j<W and M[x+i][y+j]==0:
                    check.append([x+i,y+j])
    if len(check)==0:
        print(-1)
        break

    ans+=1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
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 = list(data.reshape(-1))
    HEIGHT = H + 4
    WIDTH = W + 4
    N = HEIGHT * WIDTH
    visited = [0] * N
    distance = [0] * N
    jump = [0] * N
    from collections import deque

    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())
    D = [0] * ((H + 4) * (W + 4))
    for i in range(H):
        S = input().strip()
        for j in range(W):
            D[(i + 2) * (W + 4) + (j + 2)] = 1 if S[j] == ord(b".") else 0
    # print(D)
    # for i in range(H + 4):
    #     print(D[i * (H + 4): i * (H + 4) + (W + 4)])
    # data = np.array(list(read().strip()) + [0])
    # 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 collections import deque


def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1
S = []
for _ in range(H):
    row = list(input())
    S.append(row)
if S[D_h][D_w] == '#' or S[C_h][C_w] == '#':
    print(-1)
else:
    queue = deque([(0, (C_h, C_w))])
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = queue.popleft()
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                queue.append((score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                queue.append((score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                    queue.append((score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    if (D_h, D_w) not in dist:
        print(-1)
    else:
        print(dist[D_h, D_w])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys
    from collections import deque
    import heapq

    H, W = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = list(map(int, sys.stdin.readline().split()))
    Ch, Cw = Ch-1, Cw-1
    Dh, Dw = list(map(int, sys.stdin.readline().split()))
    Dh, Dw = Dh-1, Dw-1
    S = []
    for _ in range(H):
        s = input()
        S.append(list(s))

    que = []
    heapq.heapify(que)
    heapq.heappush(que, [0, Ch, Cw])  # [ワープ回数, h座標, w座標]
    visited = set()
    while len(que) != 0:
        n, y, x = heapq.heappop(que)
        visited.add((y, x))

        # ゴールか？
        if y == Dh and x == Dw:
            print(n)
            return

        # 上下左右移動可能ならばqueに入れる
        for ny, nx in ([y-1, x], [y+1, x], [y, x-1], [y, x+1]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n, ny, nx])
        # ワープ可能位置をqueに入れる
        for ny, nx in ([y-2, x-2], [y-2, x-1], [y-2, x], [y-2, x+1], [y-2, x+2],
                       [y-1, x-2], [y-1, x-1], [y-1, x+1], [y-1, x+2],
                       [y, x-2], [y, x+2],
                       [y+2, x-2], [y+2, x-1], [y+2, x], [y+2, x+1], [y+2, x+2],
                       [y+1, x-2], [y+1, x-1], [y+1, x+1], [y+1, x+2]):
            if 0 <= ny < H and 0 <= nx < W and not (ny, nx) in visited and S[ny][nx] == ".":
                heapq.heappush(que, [n+1, ny, nx])

    # ゴールはたどり着かなかったよ・・・
    print(-1)
    return


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1), \
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -1), (2, -2), \
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -1), (-2, -2), \
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh][nw] > dist[h][w]:
                    dist[nh][nw] = dist[h][w]
                    Q.append((nh,nw))
        for dh, dw in warp:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[h][w] + 1 < dist[nh][nw]:
                    dist[nh][nw] = dist[h][w] + 1
                    Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append([CY, CX])  # スタート地点
# 各頂点について2*2の幅優先する？
INF = float("inf")
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[INF]*W for _ in range(H)]
# print(distant)
# 更新されるなら追加
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == ".":
            # 道の場合はコスト0で移動できる
            if distant[ny][nx] > distant[cy][cx]:
                distant[ny][nx] = distant[cy][cx]
                q.append([ny, nx])
    # 周囲5*5の道に+1で到達する
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append([target_y, target_x])

if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque 
inf = 10**9+1
def do():
    dyx = [(-1,0),(1,0),(0,1),(0,-1)]
    h,w=INTM()
    sh,sw=INTM()
    sh-=1
    sw-=1
    gh,gw=INTM()
    gh-=1
    gw-=1
    dist=[[inf]*w for i in range(h)]
    dist[sh][sw]=0
    s=[]
    for i in range(h):
        s.append(STR())
    
    que=deque()
    que.append(sh*w+sw)
    while que:
        q=que.popleft()
        th=q//w
        tw=q%w
        for dy,dx in dyx:
            if (0 <= th+dy <h) and (0 <= tw+dx <w):
                if s[th+dy][tw+dx]=="#":
                    for ddy in range(-2,3,1):
                        for ddx in range(-2,3,1):
                            
                            if (ddy,ddx) in dyx or ((ddy,ddx) == (0,0)):
                                continue
                            if (0 <= th+ddy <h) and (0 <= tw+ddx <w):
                                if  s[th+ddy][tw+ddx]==".":
                                    if dist[th+ddy][tw+ddx] >dist[th][tw]+1:
                                        que.append((th+ddy)*w+(tw+ddx))
                                        dist[th+ddy][tw+ddx] =dist[th][tw]+1
                                    
                else:
                    if dist[th+dy][tw+dx] >dist[th][tw]:
                        que.append((th+dy)*w+(tw+dx))
                        dist[th+dy][tw+dx] =dist[th][tw]
        
    if dist[gh][gw]==inf:
        print(-1)
    else:
        print(dist[gh][gw])
        
    # print(dist)
                                
                                
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])
    is_found = False

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.append([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
                elif grid[ny][nx] == '#':
                    for dy, dx in w_goto:
                        nwy = temp[0] + dy
                        nwx = temp[1] + dx
                        nw = w_num +1

                        if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                            if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                                que.append([nwy, nwx, nw])
                                fp[nwy][nwx] = nw

    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

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)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

a = [(-1, 0), (1, 0), (0, -1), (0, 1)]
b = [(i % 5 - 2, i // 5 - 2) for i in range(25) if (i % 5 - 2, i // 5 - 2) not in a]

d = [[H * W] * W for _ in range(H)]
d[Ch][Cw] = 0
Q = {(Ch, Cw)}
while Q:
    h, w = Q.pop()
    for ah, aw in a:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w]:
                d[nh][nw] = d[h][w]
                Q.add((nh, nw))
    for ah, aw in b:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w] + 1:
                d[nh][nw] = d[h][w] + 1
                Q.add((nh, nw))

if d[Dh][Dw] == H * W:
    ans = -1
else:
    ans = d[Dh][Dw]
print(ans)

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 i in range(H)]

from collections import deque

dist = [[100000000 for i in range(W)] for j in range(H)]
dist[Ch-1][Cw-1] = 0

que = deque()
que.append((Ch-1, Cw-1))

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

while que:
    vh, vw = que.popleft()
    for step in walk:
        vh_next = vh+step[0]
        vw_next = vw+step[1]
        if vh_next in range(H) and vw_next in range(W):
            if S[vh_next][vw_next] == '.' and dist[vh_next][vw_next] > dist[vh][vw]:
                dist[vh_next][vw_next] = dist[vh][vw]
                que.append((vh_next, vw_next))
            elif S[vh_next][vw_next] == '#':
                for warp_step in warp:
                    vh_warp = vh+warp_step[0]
                    vw_warp = vw+warp_step[1]
                    if vh_warp in range(H) and vw_warp in range(W) and S[vh_warp][vw_warp] == '.' and dist[vh_warp][vw_warp] > dist[vh][vw]+1:
                        dist[vh_warp][vw_warp] = dist[vh][vw]+1
                        que.append((vh_warp, vw_warp))

#for d in dist:
#    print(d)

if dist[Dh-1][Dw-1] < 100000000:
    print(dist[Dh-1][Dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch - 1][Cw - 1] = 1


def water(x, y):
    if floor[y][x] != 0:

        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H - 1) + 1):
        for X in range(max(x - 2, 0), min(x + 2, W - 1) + 1):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1
                water(X, Y)


# スタート地点に水を流す
water(Cw - 1, Ch - 1)
# print(floor)

# ワープ回数
for i in range(1, 1000):
    flag = False
    for y in range(H):
        for x in range(W):
            if floor[y][x] == i:
                warp(x, y, i)
                flag = True

    if floor[Dh - 1][Dw - 1] != 0:
        print(floor[Dh - 1][Dw - 1] - 1)
        # print(floor)
        sys.exit()

    if flag == False:
        print("-1")
        sys.exit()