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 sys, math
from collections import deque

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    H, W = mi()
    Ch, Cw = mi()
    Dh, Dw = mi()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [input() for _ in range(H)]
    inf = 1e18
    

    d = deque([(Ch, Cw)])
    visited = [[inf]*W for _ in range(H)]
    visited[Ch][Cw] = 0

    check = set()

    while d:
        now_h, now_w = d.pop()
        check.add((now_h, now_w))

        # 行けるとこリスト
        nexts = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0:
                    continue
                if 0 <= now_h+i < H and 0 <= now_w+j < W and S[now_h+i][now_w+j] == '.':
                        nexts.append((now_h+i, now_w+j))


        for next in nexts:
            next_h, next_w = next
            ne = visited[next_h][next_w]
            no = visited[now_h][now_w]

            if abs(now_h-next_h)+abs(now_w-next_w) == 1:
                if ne > no:
                    visited[next_h][next_w] = no

                if not (next_h, next_w) in check:
                    d.append(next)
            else:
                if ne > no+1:
                    visited[next_h][next_w] = no+1
                
                if not (next_h, next_w) in check:
                    d.appendleft(next)

    ans = visited[Dh][Dw]
    if ans != inf:
        print(ans)
    else:
        print(-1)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (h*w) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
maze = [list(input()) for i in range(h)]
# eのインデックスはi*w+j
e = [[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if j<w-1 and maze[i][j] == "." and maze[i][j+1] == ".":
            e[i*w+j].append((0, i*w+j+1))
            e[i*w+j+1].append((0, i*w+j)) # 有向グラフでは削除
        if i<h-1 and maze[i][j] == "." and maze[i+1][j] == ".":
            e[i*w+j].append((0, (i+1)*w+j))
            e[(i+1)*w+j].append((0, i*w+j)) # 有向グラフでは削除
        for x in range(-2,3):
            for y in range(-2,3):
                if 0<=i+x<h and 0<=j+y<w and maze[i+x][j+y] == ".":
                    e[i*w+j].append((1, (i+x)*w+j+y))

# print(dijkstra(1))
ans = dijkstra((c[0]-1)*w+(c[1]-1))[(d[0]-1)*w+(d[1]-1)]
if ans == float("inf"):
    print(-1)
    exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

dist[Ch][Cw] = 0
q = deque()
q.append((Ch, Cw))
cost = 0

def p_dist():
    print('---')
    for row in dist:
        print(row)

while q:
    jump_list = []
    while q:
        v = q.popleft()
        jump_list.append(v)
        # print('n', v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    cost += 1
    q = deque(jump_list)
    jump_list = []
    while q:
        v = q.popleft()
        # print('j', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    pass
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    pass
                elif i == v[0] and j == v[1]:
                    pass
                elif i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                    # print(i, j, dist[i][j])
                    dist[i][j] = cost

    for i in range(H):
        for j in range(W):
            if dist[i][j] == cost:
                jump_list.append((i, j))

    q = deque(jump_list)

# p_dist()
print(dist[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W = mi()
    Ch, Cw = mi()
    Dh, Dw = mi()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [input() for _ in range(H)]
    inf = math.inf
    

    d = deque([(Ch, Cw)])
    visited = [inf]*(H*W)
    visited[Ch*W+Cw] = 0

    check = [False]*(H*W)

    while d:
        now_h, now_w = d.pop()
        check[now_h*W+now_w] = True

        # 行けるとこリスト
        nexts = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0:
                    continue
                if 0 <= now_h+i < H and 0 <= now_w+j < W and S[now_h+i][now_w+j] == '.':
                        nexts.append((now_h+i, now_w+j))


        for next in nexts:
            next_h, next_w = next

            if abs(now_h-next_h)+abs(now_w-next_w) == 1:
                if visited[next_h*W+next_w] > visited[now_h*W+now_w]:
                    visited[next_h*W+next_w] = visited[now_h*W+now_w]

                if not check[next_h*W+next_w]:
                    d.append(next)
            else:
                if visited[next_h*W+next_w] > visited[now_h*W+now_w]+1:
                    visited[next_h*W+next_w] = visited[now_h*W+now_w]+1
                
                if not check[next_h*W+next_w]:
                    d.appendleft(next)

    ans = visited[Dh*W+Dw]
    if ans != inf:
        print(ans)
    else:
        print(-1)
        

if __name__ == '__main__':
    main()

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*(10**4)])  # [ワープ回数, 座標]
    visited = set()
    while len(que) != 0:
        n, yx = heapq.heappop(que)
        y, x = yx%(10**4), yx//(10**4)
        if (y, x) in visited: continue
        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*(10**4)])
        # ワープ可能位置を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*(10**4)])

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


def solve2():
    """TLE"""
    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:
from collections import deque
H, W = [int(a) for a in input().split()]
Ch, Cw = [int(a)-1 for a in input().split()]
Dh, Dw = [int(a)-1 for a in input().split()]

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

dist[Ch][Cw] = 0
q = deque()
q.append((Ch, Cw))
cost = 0

def p_dist():
    print('---')
    for row in dist:
        print(row)

while q:
    while q:
        v = q.popleft()
        # print('n', v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    jump_list = []
    for i in range(H):
        for j in range(W):
            if dist[i][j] == cost:
                jump_list.append((i, j))

    cost += 1
    q = deque(list(jump_list))
    while q:
        v = q.popleft()
        # print('j', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == 0:
                    continue
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == 0:
                    continue
                # print(i, j, S[i][j])
                if i >= 0 and j >= 0 and i < H and j < W and (i != v[0] or j != v[1]) and S[i][j]=='.' and dist[i][j] == -1:
                    # print(i, j, dist[i][j])
                    dist[i][j] = cost
    
    jump_list = []
    for i in range(H):
        for j in range(W):
            if dist[i][j] == cost:
                jump_list.append((i, j))
    q = deque(jump_list)

# p_dist()
print(dist[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())
S = [" "]
for _ in range(H):
    S.append(" " + input())
INF = 100000
warp_min = [[INF] * (W + 1) for _ in range(H + 1)]
warp_min[Ch][Cw] = 0
d = deque()
d.append((Ch, Cw))
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
ndx_0 = (0, -1, -2, -1, -2)
ndy_0 = (1, 0, 0, 1, 1)
ndx_1 = (1, 0, 0, 1, 1)
ndy_1 = (1, 2, 1, 2, 0)
ndx_2 = (1, 0, 2, 1, 2)
ndy_2 = (0, -1, 0, -1, -1)
ndx_3 = (0, 0, -1, -1, -1)
ndy_3 = (-2, -1, 0, -1, -2)

cnt = 0

#while warp_min[Dh][Dw] == INF:
while d:
    wall_pos = []
    pos = d.popleft()
    #next_pos = []
    for i in range(4):
        next_y = pos[0] + dy[i]
        next_x = pos[1] + dx[i]
        if next_x <= 0 or next_x > W or next_y <= 0 or next_y > H:
            continue
        if warp_min[next_y][next_x] != INF and warp_min[pos[0]][pos[1]] >= warp_min[next_y][next_x]:
            continue
        if S[next_y][next_x] == ".":
            warp_min[next_y][next_x] = min(warp_min[pos[0]][pos[1]], warp_min[next_y][next_x])
            d.append((next_y, next_x))
        else:
            for j in range(5):
                if i == 0:
                    warp_to_y = next_y + ndy_0[j]
                    warp_to_x = next_x + ndx_0[j]
                elif i == 1:
                    warp_to_y = next_y + ndy_1[j]
                    warp_to_x = next_x + ndx_1[j]
                elif i == 2:
                    warp_to_y = next_y + ndy_2[j]
                    warp_to_x = next_x + ndx_2[j]
                elif i == 3:
                    warp_to_y = next_y + ndy_3[j]
                    warp_to_x = next_x + ndx_3[j]
                if warp_to_x <= 0 or warp_to_x > W or warp_to_y <= 0 or warp_to_y > H:
                    continue
                if warp_min[warp_to_y][warp_to_x] != INF and warp_min[pos[0]][pos[1]] >= warp_min[warp_to_y][warp_to_x]:
                    continue
                if S[warp_to_y][warp_to_x] == ".":
                    warp_min[warp_to_y][warp_to_x] = min(warp_min[pos[0]][pos[1]] + 1, warp_min[warp_to_y][warp_to_x])
                    d.append((warp_to_y, warp_to_x))

#for i in warp_min:
#    print(i)
if warp_min[Dh][Dw] == INF:
    warp_min[Dh][Dw] = -1
print(warp_min[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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0 and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = ((1,0),(-1,0),(0,1),(0,-1))

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = []
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
import heapq

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10**10
D = [[inf] * w for i in range(h)]
D[i0][j0] = 0
Q = [(0, (i0, j0))]
heapq.heapify(Q)
while Q:
    _, (i, j) = heapq.heappop(Q)
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ii, jj = i + di, j + dj
            if 0 <= ii < h and 0 <= jj < w and S[ii][jj] == ".":
                nex = int(abs(di) + abs(dj) != 1)
                if D[i][j] + nex < D[ii][jj]:
                    D[ii][jj] = D[i][j] + nex
                    heapq.heappush(Q, (D[ii][jj], (ii, jj)))
if D[i1][j1] >= inf:
    print(-1)
else:
    print(D[i1][j1])

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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])  # 陸路で行くところ
d2 = deque([(Ch, Cw)]) # 直前のワープ後に陸路でいった場所のメモ
s = set() # いったところ
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    d2.append((Th, Tw))
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if _p == (Dh, Dw):
        print(ans)
        exit()
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if _p == (Dh, Dw):
          print(ans)
          exit()
        if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

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


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    s = set()
    
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        
        for y, x in a:
            o = 0
            for d in range(4):
                px = x + dx[d]
                py = y + dy[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 2:
                    o += 1
            if o == 4 : continue
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
d2 = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    neighbor = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
    warp = tuple((i, j) for i in range(-2, 3) for j in range(-2, 3))  # ワープで移動できる範囲

    def is_inside(row, col):
        return 0 <= row < H and 0 <= col < W

    # dist[r][c]: スタートから (r, c) に到達するために必要なワープ回数の最小値
    dist = [[float('inf')] * W for _ in range(H)]
    queue = deque([(Start_row, Start_col, 0)])
    while queue:
        row, col, time = queue.pop()
        dist[row][col] = time
        for dr, dc in neighbor:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Grid[nr][nc] == '.' and time < dist[nr][nc]:
                queue.append((nr, nc, time))
        for dr, dc in warp:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Grid[nr][nc] == '.' and time < dist[nr][nc]:
                queue.append((nr, nc, time + 1))
    return -1 if dist[Goal_row][Goal_col] == float('inf') else dist[Goal_row][Goal_col]

print(d_wizard_in_maze())

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

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


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    s = set()
    
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()