Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

T = list(input() for _ in range(H))
S = [[False]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if T[h][w] == ".":
            S[h][w] = True
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] and c < d[h-1][w]:
            d[h-1][w] = c
            deque.append(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] and c < d[h+1][w]:
            d[h+1][w] = c
            deque.append(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] and c < d[h][w-1]:
            d[h][w-1] = c
            deque.append(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] and c < d[h][w+1]:
            d[h][w+1] = c
            deque.append(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = list(input() for _ in range(H))
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] == "." and c < d[h-1][w]:
            d[h-1][w] = c
            deque.append(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] == "." and c < d[h+1][w]:
            d[h+1][w] = c
            deque.append(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] == "." and c < d[h][w-1]:
            d[h][w-1] = c
            deque.append(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] == "." and c < d[h][w+1]:
            d[h][w+1] = c
            deque.append(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] == "." and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = list(input() for _ in range(H))
d = [[10**9]*W for _ in range(H)]
# d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c >= d[h][w]:
        continue
    d[h][w] = c
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] == "." and c < d[h-1][w]:
            deque.append(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] == "." and c < d[h+1][w]:
            deque.append(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] == "." and c < d[h][w-1]:
            deque.append(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] == "." and c < d[h][w+1]:
            deque.append(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] == "." and d[hh][ww] > c+1:
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def solve():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=[]
  for i in range(2):
    M.append("#"*(w+4))
  for i in range(h):
    M.append("##"+input()+"##")
  for i in range(2):
    M.append("#"*(w+4))

  INF=10**6
  C=[[INF for _ in range(w+4)] for _ in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if M[dh][dw]=="." and c<C[dh][dw]:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if M[dh][dw]=="." and -~c<C[dh][dw]:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx] if C[-~dy][-~dx]!=INF else -1)

if __name__ == "__main__":
  solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = list(input() for _ in range(H))
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] == "." and c < d[h-1][w]:
            d[h-1][w] = c
            deque.append(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] == "." and c < d[h+1][w]:
            d[h+1][w] = c
            deque.append(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] == "." and c < d[h][w-1]:
            d[h][w-1] = c
            deque.append(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] == "." and c < d[h][w+1]:
            d[h][w+1] = c
            deque.append(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] == "." and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env PyPy
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "#":
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "#":
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

# 入力
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))

# コストをまとめる表
cost = [[float("inf")] * W for i in range(H)]

def bfs(que, c):
    # 幅優先探索を用いて、位置(init_x, init_y)から追加コストなしで辿り着けるマスを列挙

    next_que = deque([])

    while que:

        # キューの先頭を取り出す
        x, y = que.popleft()
        cost[x][y] = c

        # next_que に含まれる点なら除く（これで1つTLEが消えた）
        if (x,y) in next_que:
            next_que.remove((x,y))

        # 取り出してきたキューがゴールなら探索をやめる
        if (x, y) == (D_h-1, D_w-1):
            return True, next_que

        moveA_vector = [(1,0),(-1,0),(0,1),(0,-1)]

        # 現在地から移動Aで到達可能で未探索の点をキューに追加
        # 移動4方向をループ
        for dx, dy in moveA_vector:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf"):
                que.append((nx, ny))
                # cost[nx][ny] = c この処理は先頭でやる

        # 現在地から移動Bで到達可能で未探索の点を次のコストのキューに追加
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) not in moveA_vector:  # 5*5の範囲内でかつ移動Aで到達できない点 = 現在地から移動Bで到達可能な点
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf") and (nx, ny) not in next_que:  # 到達可能で未探索の点
                        next_que.append((nx, ny))

    return False, next_que

c = 0
que = deque([])
que.append((C_h-1, C_w-1))

while True:

    f, que = bfs(que, c)
    if f:  # ゴールが見つかった
        print(c)
        sys.exit()
    if not que:  # queが空のとき、これ以上移動不可能（dequeなのでque==[]は誤り）
        break
    c += 1
print("-1")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def same_cost(i, j):
    now = cnts[i][j]

    for I, J in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
        if 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
            cnts[I][J] = cnts[i][j]
            a.append([I, J, now])
            same_cost(I, J)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

inf = 10**10
cnts = [[inf for _ in range(w)] for _ in range(h)]

a = deque()
b = deque()

a.append([ch-1, cw-1, 0])
now = 0
while True:
    visits = []
    visited_set = set()
    while len(a):
        i, j, now = a.popleft()
        if (i, j) == (dh-1, dw-1):
            print(now)
            exit()
        if str(i) + '+' + str(j) in visited_set:
            continue
        visits.append([i, j])
        cnts[i][j] = now
        same_cost(i, j)
        visited_set.add(str(i) + '+' + str(j))

    a = deque()
    visited_set = set()
    for i, j in visits:
        for I in range(i-2, i+3):
            for J in range(j-2, j+3):
                if not str(I) + '+' + str(J) in visited_set and 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
                    cnts[I][J] = cnts[i][j] + 1
                    a.append([I, J, now+1])
                visited_set.add(str(I) + '+' + str(J))
    if not len(a):
        break

ans = cnts[dh-1][dw-1]
if ans == inf:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import pprint
import time

h,w = map(int, stdin.readline().split())
sh,sw = map(int, stdin.readline().split())
gh,gw = map(int, stdin.readline().split())
dist = [[-2] * (w+4) for _ in range(h+4)] 

for i in range(h):
    ix = i+2
    iy = 1
    for v in list(stdin.readline()):
        iy += 1
        if v == ".":
            dist[ix][iy] = -1

sh+=1
sw+=1
gh+=1
gw+=1

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1], [-1, 2], [0, -2], [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

def solve():
    queue = []
    queue.append([sh,sw])
    dist[sh][sw] = 0
    check_list = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        check_list.append([x,y])
        for p, q in move:
            nx = x + p
            ny = y + q
            if dist[nx][ny] == -1:
                queue.append([nx,ny])
                dist[nx][ny] = dist[x][y]
                check_list.append([nx,ny])
                if [nx, ny] == [gh, gw]:
                    return True
        
        if len(queue) == 0:
            while len(check_list) > 0:
                x2, y2 = check_list.pop(0) 
                for p2, q2 in magic:
                    nx2 = x2 + p2
                    ny2 = y2 + q2
                    if dist[nx2][ny2] == -1:
                        dist[nx2][ny2] = dist[x2][y2]+1
                        queue.append([nx2, ny2])

solve()
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import pprint
import time
h,w = map(int, stdin.readline().split())
sh,sw = map(int, stdin.readline().split())
gh,gw = map(int, stdin.readline().split())
dist = [[-2] * (w+4) for _ in range(h+4)] 

for i in range(h):
    ix = i+2
    iy = 1
    for v in list(stdin.readline()):
        iy += 1
        if v == ".":
            dist[ix][iy] = -1

sh+=1
sw+=1
gh+=1
gw+=1

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1], [-1, 2], [0, -2], [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

def solve():
    queue = []
    queue.append([sh,sw])
    dist[sh][sw] = 0
    check_list = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        check_list.append([x,y])
        for p, q in move:
            nx = x + p
            ny = y + q
            if dist[nx][ny] == -1:
                queue.append([nx,ny])
                dist[nx][ny] = dist[x][y]
                check_list.append([nx,ny])
                if [nx, ny] == [gh, gw]:
                    return True
        
        if len(queue) == 0:
            while len(check_list) > 0:
                x2, y2 = check_list.pop(0) 
                for p2, q2 in magic:
                    nx2 = x2 + p2
                    ny2 = y2 + q2
                    if dist[nx2][ny2] == -1:
                        dist[nx2][ny2] = dist[x2][y2]+1
                        queue.append([nx2, ny2])

solve()
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import pprint
import time
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
dist = [[-2] * (w+4) for _ in range(h+4)] 

for i in range(h):
    ix = i+2
    iy = 1
    for v in list(input()):
        iy += 1
        if v == ".":
            dist[ix][iy] = -1

sh+=1
sw+=1
gh+=1
gw+=1

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1], [-1, 2], [0, -2], [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

def solve():
    queue = []
    queue.append([sh,sw])
    dist[sh][sw] = 0
    check_list = []
    while len(queue) > 0:
        x, y = queue.pop(0)
        check_list.append([x,y])
        for p, q in move:
            nx = x + p
            ny = y + q
            if dist[nx][ny] == -1:
                queue.append([nx,ny])
                dist[nx][ny] = dist[x][y]
                check_list.append([nx,ny])
                if [nx, ny] == [gh, gw]:
                    return True
        
        if len(queue) == 0:
            while len(check_list) > 0:
                x2, y2 = check_list.pop(0) 
                for p2, q2 in magic:
                    nx2 = x2 + p2
                    ny2 = y2 + q2
                    if dist[nx2][ny2] == -1:
                        dist[nx2][ny2] = dist[x2][y2]+1
                        queue.append([nx2, ny2])

solve()
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def same_cost(i, j):
    now = cnts[i][j]

    for I, J in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
        if 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
            cnts[I][J] = cnts[i][j]
            a.append([I, J, now])
            same_cost(I, J)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

inf = 10**10
cnts = [[inf for _ in range(w)] for _ in range(h)]

a = deque()
b = deque()

a.append([ch-1, cw-1, 0])
now = 0
while True:
    visits = []
    visited_set = set()
    while len(a):
        i, j, now = a.popleft()
        if str(i) + '+' + str(j) in visited_set:
            continue
        visits.append([i, j])
        cnts[i][j] = now
        same_cost(i, j)
        visited_set.add(str(i) + '+' + str(j))

    a = deque()
    visited_set = set()
    for i, j in visits:
        for I in range(i-2, i+3):
            for J in range(j-2, j+3):
                if not str(I) + '+' + str(J) in visited_set and 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
                    cnts[I][J] = cnts[i][j] + 1
                    a.append([I, J, now+1])
                visited_set.add(str(I) + '+' + str(J))
    if not len(a):
        break

ans = cnts[dh-1][dw-1]
if ans == inf:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
def same_cost(i, j):
    now = cnts[i][j]

    for I, J in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
        if 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
            cnts[I][J] = cnts[i][j]
            a.put([I, J, now])
            same_cost(I, J)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

inf = 10**10
cnts = [[inf for _ in range(w)] for _ in range(h)]

a = queue.Queue()
b = queue.Queue()

a.put([ch-1, cw-1, 0])
now = 0
while True:
    visits = []
    visited_set = set()
    while not a.empty():
        i, j, now = a.get()
        if str(i) + '+' + str(j) in visited_set:
            continue
        visits.append([i, j])
        cnts[i][j] = now
        same_cost(i, j)
        visited_set.add(str(i) + '+' + str(j))

    a = queue.Queue()
    visited_set = set()
    for i, j in visits:
        for I in range(i-2, i+3):
            for J in range(j-2, j+3):
                if not str(I) + '+' + str(J) in visited_set and 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
                    cnts[I][J] = cnts[i][j] + 1
                    a.put([I, J, now+1])
                visited_set.add(str(I) + '+' + str(J))
    if a.empty():
        break

ans = cnts[dh-1][dw-1]
if ans == inf:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
def same_cost(i, j):
    now = cnts[i][j]

    for I, J in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
        if 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
            cnts[I][J] = cnts[i][j]
            a.put([I, J, now])
            same_cost(I, J)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

inf = 10**10
cnts = [[inf for _ in range(w)] for _ in range(h)]

a = queue.Queue()
b = queue.Queue()

a.put([ch-1, cw-1, 0])
now = 0
while True:
    visits = []
    while not a.empty():
        i, j, now = a.get()
        visits.append([i, j])
        cnts[i][j] = now
        same_cost(i, j)

    a = queue.Queue()
    visited_set = set()
    for i, j in visits:
        for I in range(i-2, i+3):
            for J in range(j-2, j+3):
                if not str(I) + '+' + str(J) in visited_set and 0 <= I < len(s) and 0 <= J < len(s[I]) and s[I][J] == '.' and cnts[I][J] > cnts[i][j]:
                    cnts[I][J] = cnts[i][j] + 1
                    a.put([I, J, now+1])
                visited_set.add(str(I) + '+' + str(J))
    if a.empty():
        break

ans = cnts[dh-1][dw-1]
if ans == inf:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Wizard in Maze

import heapq

h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

queue = [(0, ch - 1, cw - 1)]  # (dist, y, x)

while len(queue) > 0:
    dist, y, x = heapq.heappop(queue)
    if s[y][x] != '.':
        continue
    s[y][x] = dist
    for vy in range(-2, 3):
        for vx in range(-2, 3):
            if 0 <= y + vy < h and 0 <= x + vx < w and \
               s[y + vy][x + vx] == '.':
                cost = 0 if abs(vx) + abs(vy) <= 1 else 1
                heapq.heappush(queue, (dist + cost, y + vy, x + vx))

dist = s[dh - 1][dw - 1]
print(dist if dist != '.' else -1)

Submission status: Time Limit Exceeded

Solution code:
# D - Wizard in Maze

import heapq

h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

queue = [(0, ch - 1, cw - 1)]  # (dist, y, x)

while len(queue) > 0:
    dist, y, x = heapq.heappop(queue)
    if s[y][x] != '.':
        continue
    s[y][x] = dist
    for vy in range(-2, 3):
        for vx in range(-2, 3):
            if 0 <= y + vy < h and 0 <= x + vx < w:
                cost = 0 if abs(vx) + abs(vy) <= 1 else 1
                heapq.heappush(queue, (dist + cost, y + vy, x + vx))

dist = s[dh - 1][dw - 1]
print(dist if dist != '.' else -1)

Submission status: Time Limit Exceeded

Solution code:

# 初期入力
import sys
from collections import deque
#input = sys.stdin.readline  #文字列では使わない
H,W = map(int, input().split())
S_h,S_w = map(int, input().split()) #スタート
G_h,G_w = map(int, input().split()) #ゴール

#迷路
mp =[["#"]*(W +4) for i in range(H +4)] #上下左右に２個分余分に壁を作る
for i in range(2,H+2):
    mp[i][2:-2] =input().strip() #迷路読み込み
    
S_h +=1 #壁を余分に作った分、スタートとゴールをずらす
S_w +=1
G_h +=1
G_w +=1
used =[[float('inf')]*(W +4) for i in range(H +4)] #既に通ったところを保存
used[S_h][S_w] =0
wap=[-2,-1,0,1,2] #ワープ移動できる縦横の範囲


dq =deque()
dq.append((0,S_h,S_w)) #キューには(コスト、x座標、y座標)を追加していく
arrive=False #ゴールに到着すればTrueに変更

while dq:
    k,i,j =dq.popleft()
    if k >used[i][j]: #既に通ったかどうか
        continue
    if i ==G_h and j ==G_w: #ゴール判定
        arrive =True
        break
    for di in wap:
        for dj in wap:
            if di ==0 and dj ==0: #その場から移動しない時
                continue
            ni,nj =i +di ,j +dj #移動後の座標(ni,nj)
            if mp[ni][nj] =="#": #移動先が壁の中
                continue
            if k <used[ni][nj]:
                if abs(di) +abs(dj) ==1: #歩行圏内(コスト:0)
                    nk =k
                    used[ni][nj] =nk
                    dq.appendleft((nk,ni,nj))
                else:                   #歩行圏外(コスト:１)
                    nk =k+1
                    used[ni][nj] =nk
                    dq.append((nk,ni,nj))
if arrive:
    ans =used[G_h][G_w]
else:
    ans =-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#写経 #16303645
#dequeはリストよりも高速に両端の値にアクセスできる
import sys
from collections import deque
h,w = map(int, input().split())#hは表の高さ、wは表の幅
ch, cw = map(int, input().split())#スタート地点のh座標,w座標
dh, dw = map(int, input().split())#ゴール地点のh座標、w座標

#s;迷路。枠外にワープしないよう周りを＃＃で囲む
s = ["#"*(w+4)]#上側の＃
s.append("#"*(w+4))#上側の＃
for i in range(h):
    s.append("##"+input()+"##")#左右の＃＃
s.append("#"*(w+4))#下側の＃
s.append("#"*(w+4))#下側の＃
#print(s)
"""
s
['######',
 '######', 
 '##..##', 
 '##..##', 
 '######', 
 '######']
"""  
ans = [[-1]*(w+4) for i in range(h+4)]#全要素−1
#print(ans)
"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""
#壁＃の部分を−2にする。移動可能位置は−1
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
        	ans[i][j] = -2
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
#壁で囲った表でスタート、ゴール位置を正しく指定出来るようcとsのh座標、w座標を1ずつ増やす
ch += 1
cw += 1
dh += 1
dw += 1
#ansのスタート位置を0にする。魔法を使った回数。
ans[ch][cw] = 0
#print(ans)
"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]#移動変位。下、上、右、左
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
magic = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

mylist = deque([[ch,cw]])#dequeの生成。移動元の座標リスト。初期値はスタート位置。
mylist2 = deque([])#徒歩で通った座標のリスト。

#徒歩、魔法両方で行ける場所を全て探す
while len(mylist) > 0:
    y,x = mylist.popleft()#mylistの左端の座標を取り出す。初期値はスタート位置。
    mylist2.append([y, x])#mylist2の右端に取り出した座標を追加。
    #これまで通ったことがなく、徒歩で移動できる座標を見つける。これまで魔法を使った回数をその座標の値にする。
    for p,q in move:#移動変位を一つずつ取り出す
        vy,vx = y+p, x+q#移動先のh座標、w座標移動可能な場合
        if ans[vy][vx]== -1:#まだ行ったことが無く、移動可能=移動先が−1の場合
            mylist.append([vy,vx])#移動元の座標リストに追加
            ans[vy][vx] =ans[y][x]#移動先の値を移動元の値と同じにする。これまで魔法を使った回数。
            #移動先がゴールなら終了
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    #print(ans)
    #徒歩で移動できなくなったら、魔法を使って移動出来る座標を探す。魔法を使った回数が+1になる。
    if len(mylist) == 0:#移動出来なくなった場合
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()#移動先リストから座標を取り出す
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2#取り出した座標にmagic移動変位を加える
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1#魔法を使って移動したので、移動先の値は移動元の値+1になる。
                    #移動先がゴールなら終了
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    #print(ans)
    #魔法を使って移動出来る座標がみつかったら、徒歩で移動可能な座標を探すループに戻る
#全て通った、もしくは徒歩でも魔法でも移動できない座標のみになったら終わり
print(ans[dh][dw])#全探索した表のゴール位置の値が答え。移動できなかったら−1