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 heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [input() for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cnt = 0
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = list(map(int, input().split()))

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

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

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(10**5):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 3)
        W_que.append(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 1)
        W_que.append(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #移動Bパターン


    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, 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

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

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#" and (i, j) not in edges[cnt]:
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)])
# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[num]:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    readline = sys.stdin.readline

    H, W = map(int, readline().split())
    a, b = map(int, readline().split())
    c, d = map(int, readline().split())
    S = [readline().rstrip() for i in range(H)]

    a,b,c,d = (v - 1 for v in (a,b,c,d))

    INF = 10 ** 10

    groups = []

    visited = [[False] * W for i in range(H)]

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def dfs(x, y, group):
        if not (0 <= x < H and 0 <= y < W):
            return
        
        if visited[x][y]:
            return
        
        if S[x][y] == '#':
            return
        
        group.append((x,y))
        visited[x][y] = True

        for dx, dy in dirs:
            dfs(x + dx, y + dy, group)

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' and not visited[i][j]:
                group = []
                dfs(i, j, group)
                groups.append(group)
    
    
    p2g = [[-1] * W for i in range(H)]
    for i,group in enumerate(groups):
        for x,y in group:
            p2g[x][y] = i
    
    G = len(groups)
    g_adj = [set() for i in range(G)]
    for i in range(H):
        for j in range(W):
            src = p2g[i][j]
            if src == -1:
                continue
            for x in range(max(0, i - 2), min(H - 1, i + 2) + 1):
                for y in range(max(0, j - 2), min(W - 1, j + 2) + 1):
                    if x == i and y == j:
                        continue
                    if p2g[x][y] == -1:
                        continue
                    g_adj[src].add(p2g[x][y])
    
    
    src_g = p2g[a][b]
    dst_g = p2g[c][d]

    visited = [False] * G
    q = deque()
    q.append((src_g, 0))

    while q:
        node, depth = q.popleft()
        visited[node] = True

        if node == dst_g:
            print(depth)
            return

        for adj in g_adj[node]:
            if not visited[adj]:
                q.append((adj, depth + 1))
    
    print(-1)

solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import sys

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

seen = np.array([[0]*W for _ in range(H)])
que = deque()
que.append((Ch - 1, Cw - 1))

def DFS(que):
    while que:
        X, Y = que.popleft()
        seen[X][Y] = 1
        D = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dx, dy in D:
            if 0<= X + dx < H and 0 <= Y + dy < W:
                if M[X + dx][Y + dy] == "." and seen[X + dx][Y + dy] == 0:
                    que.append((X + dx, Y + dy))

ans = 0 
while que:
    x, y = que[-1]
    DFS(que)
    if seen[Dh-1][Dw-1]!=0:
        print(ans)
        sys.exit()
    add = []
    for i in range(H):
        for j in range(W):
            if seen[i][j]==1:
                seen[i][j]=2
                for dx in range(-2, 3):
                    for dy in range(-2, 3):
                        if 0<= i + dx < H and 0 <= j + dy < W:
                            if M[i+dx][j+dy] == '.' and seen[i+dx][j+dy] == 0 and (i+dx, j+dy) not in que : 
                                que.append((i+dx, j+dy))
    ans += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
grid = [input() for i in range(h)]
done = [[0]*w for _ in range(h)]
dxdy = [[0,1],[1,0],[-1,0],[0,-1]]
def ok(i,j):
    if i>-1 and j>-1 and i<h and j<w and grid[i][j]==".":
        return True
    else:
        return False
lis = []
ind = 0
def dfs(i,j):
    if(i==dh-1 and j==dw-1):
        lis.append([i,j])
        done[i][j]=1
        return True
    elif(not done[i][j]):
        lis.append([i,j])
        done[i][j]=1
        for dx,dy in dxdy:
            if(ok(i+dy,j+dx)):
                dfs(i+dy,j+dx)

    return False
vertex_set = []
res = 0
for i in range(h):
    for j in range(w):
        if(grid[i][j]=="." and done[i][j]==0):
            dfs(i,j)
            vertex_set.append(lis)
            lis = []
edge_list = [[] for _ in range(len(vertex_set))]
start = -1
end = -1
for i in range(len(vertex_set)):
    for from_ in ((vertex_set[i])):
        for j in range(len(vertex_set)):
            if i!=j:
                for to in (vertex_set[j]):
                    if abs(to[0]-from_[0])<3 and abs(to[1]-from_[1])<3:
                        edge_list[i].append([j,1])
                        edge_list[j].append([i,1])
        if from_[0]==ch-1 and from_[1]==cw-1:
            start = i
        if from_[0]==dh-1 and from_[1]==dw-1:
            end = i
from heapq import heappush, heappop
def dijkstra(s,egde):
    n = len(edge_list)
    INF = float("INF")
    dist = [INF]*n
    hq = [(0,s)]
    dist[s] = 0
    seen = [False]*n

    while hq:
        v = heappop(hq)[1]
        seen[v] = True
        for to,cost in edge_list[v]:
            if not seen[to] and dist[v]+cost < dist[to]:
                dist[to] = dist[v]+cost
                heappush(hq, (dist[to],to))
    return dist
dist = dijkstra(start,edge_list)
if dist[end]==float("INF"):
    print(-1)
else:
    print(dist[end])

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の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
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] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.append((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            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] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Time Limit Exceeded

Solution code:
from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = [[CH+1,CW+1]]
Q = deque([[CH+1,CW+1]])
ans = 0

while P:
  P = []
  while Q:
    edge = 0
    y,x = Q.popleft()
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q.append([y+dy,x+dx])
      elif S[y+dy][x+dx]=="#":
        edge+=1
        if 2<=edge:
          edge = -1
          P.append([y,x])

  if S[DH+1][DW+1]!=".":
    print(S[DH+1][DW+1])
    exit()
  else:
    ans+=1
    for y,x in P:
      for dy,dx in [[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]]:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans
          Q.append([y+dy,x+dx])

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

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

while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.':
            stack_append([nh, nw, cnt])
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.':
            stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

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

H = 0
W = 0
table = None


def search(h, w, cnt):
    global H, W, table

    if(type(table[h][w]) is int and table[h][w] < cnt):
        return

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

    for k in range(len(move)):
        i, j = move[k]
        if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
            continue
        if table[h+i][w+j] == '.':
            table[h+i][w+j] = cnt
            search(h+i, w+j, cnt)
        elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt:
            table[h+i][w+j] = cnt
            search(h+i, w+j, cnt)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W or(i == 0 and j == 0):
                continue
            if table[h+i][w+j] == '.':
                table[h+i][w+j] = cnt+1
                search(h+i, w+j, cnt+1)
            elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt+1:
                table[h+i][w+j] = cnt+1
                search(h+i, w+j, cnt+1)


def main(input, print):
    global H, W, table
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [[] for _ in range(H)]
    for i in range(H):
        table[i] = list(input().strip())
    table[Ch-1][Cw-1] = 0
    search(Ch-1, Cw-1, 0)
    if(table[Dh-1][Dw-1] == '.'):
        print(-1)
    else:
        print(table[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import heapq
inf=10**4
H,W=map(int,input().split())
S=list(map(int,input().split()))
G=list(map(int,input().split()))
arr=[list(map(str,input())) for i in range(H)]
A=[(0,-1,0),(0,1,0),(-1,0,0),(1,0,0)]
B=[(0,-2,1),(0,2,1),(-2,0,1),(2,0,1),(-1,1,1),(-1,2,1),(-2,1,1),(-2,2,1),(-1,-1,1),(-1,-2,1),(-2,-1,1),(-2,-2,1),(1,1,1),(1,2,1),(2,1,1),(2,2,1),(1,-1,1),(1,-2,1),(2,-1,1),(2,-2,1)]
C=A+B
vist=[[0]*W for i in range(H)]
ans=[[inf]*W for i in range(H)]

d=[(0,S[0]-1,S[1]-1)]
ans[S[0]-1][S[1]-1]=0


while d:
    cost,x,y=heapq.heappop(d)
    vist[x][y]=1
    
    
    
    for dx,dy,c in C:
        if H>x+dx>=0 and W>y+dy>=0:
           if vist[x+dx][y+dy]==0 and arr[x+dx][y+dy]==".":
            
                ans[x+dx][y+dy]=min(cost+c,ans[x+dx][y+dy])
                heapq.heappush(d,(ans[x+dx][y+dy],x+dx,y+dy))


if ans[G[0]-1][G[1]-1]==inf:
    print(-1)
else:
    print(ans[G[0]-1][G[1]-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

CH -= 1
CW -= 1
DH -= 1
DW -= 1

def add(next, i, j, cost):
    if 0 <= i < H and 0 <= j < W and S[i][j] == ".":
        next.append((i, j, cost))

cost = [[10000] * W for _ in range(H)]
cost[CH][CW] = 0
prev = [[None] * W for _ in range(H)]
# Q = heapq.heapify([])
Q = []
for i in range(H):
    for j in range(W):
        heapq.heappush(Q, (cost[i][j], i, j))

while len(Q) > 0:
    _, i, j = heapq.heappop(Q)
    next = []
    add(next, i - 1, j, 0)
    add(next, i + 1, j, 0)
    add(next, i, j - 1, 0)
    add(next, i, j + 1, 0)
    for di in [-2, -1, 0, 1, 2]:
        for dj in [-2, -1, 0, 1, 2]:
            add(next, i + di, j + dj, 1)
    for i2, j2, c in next:
        alt = cost[i][j] + c
        if cost[i2][j2] > alt:
            cost[i2][j2] = alt
            prev[i2][j2] = (i, j)
            heapq.heappush(Q, (alt, i2, j2))

ans = cost[DH][DW]
if ans == 10000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import *
H, W = map(int, stdin.readline().split())
personY, personX = map(int, stdin.readline().split())
gH, gW = map(int, stdin.readline().split())

grid = [list(stdin.readline().strip()) for x in range(H)]
visited = [[10**10 for j in range(W)] for i in range(H)]
options = [(personY-1, personX-1)]

visited[personY-1][personX-1] = 0
while(options):
    y,x = options.pop()

    if y+1 < H and  grid[y+1][x] == ".":
        if visited[y+1][x] > visited[y][x]:
            options.append((y+1, x))
            visited[y+1][x] = visited[y][x]

    if  y-1 >= 0 and grid[y-1][x] == ".":
        if visited[y-1][x] > visited[y][x]:
            options.append((y-1, x))
            visited[y-1][x] = visited[y][x]

    if x+1 < W and grid[y][x+1] == ".":
        if visited[y][x+1] > visited[y][x]:
            options.append((y, x+1))
            visited[y][x+1] = visited[y][x]

    if x-1 >= 0 and grid[y][x-1] == ".":
        if visited[y][x-1] > visited[y][x]:
            options.append((y, x-1))
            visited[y][x-1] = visited[y][x]
   #-------------------------------------------
    for Y,X in [(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)]:
       if x+X >= 0 and x+X < W and y+Y >= 0 and y+Y < H and grid[y+Y][x+X] == ".":
           if visited[y+Y][x+X] > visited[y][x] +1:
               options.append((y+Y, x+X))
               visited[y+Y][x+X] = visited[y][x]+1

print(-1 if visited[gH-1][gW-1] == 10**10 else visited[gH-1][gW-1] )

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    m = abs(ni - i) + abs(nj - j)
                    nd = d if m <= 1 else d + 1
                    if dni[nj] > nd:
                        dni[nj] = nd
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    CH,CW = map(int,input().split())
    DH,DW = map(int,input().split())
    S=[None]*H
    for i in range(H):
        S[i] = input()
    
    from collections import deque
    def cango_step(x,y):
        cand =[]
        if x+1<=H-1:
            cand.append((x+1,y))
        if x-1>=0:
            cand.append((x-1,y))
        if y+1<=W-1:
            cand.append((x,y+1))
        if y-1>=0:
            cand.append((x,y-1))
        return cand
    def cango_warp(x,y):
        cand = [(i,j) 
                for i in range(x-2,x+3) for j in range(y-2,y+3) 
                if 0<=i and i<=H-1 and 0<=j and j<=W-1]
        return cand
    
    been = [[False]*W for _ in range(H)]
    rooms=dict()
    i_room=-1
    for x in range(H):
        for y in range(W):
            if S[x][y]=="." and not been[x][y]:
                i_room+=1
                been[x][y]=True
                q = deque([(-1,-1,x,y)]) 
    
                rooms[(x,y)]=i_room
                while q:
                    x_old,y_old,x_now,y_now = q.popleft()
                    
                    cand = cango_step(x_now,y_now)
                    #print(x_old,y_old,x_now,y_now,time)
                    
                    if x_now==CH-1 and y_now==CW-1:
                        start_warp = i_room
                    if x_now==DH-1 and y_now==DW-1:
                        end_warp = i_room
                    
                    for x_new,y_new in cand:
                        if not been[x_new][y_new] and S[x_new][y_new]==".":
                            q.append((x_now,y_now,x_new,y_new))
                            been[x_new][y_new]=True
    #                        room.append((x_new,y_new))
                            rooms[(x_new,y_new)]=i_room
    #            rooms.append(room)
    
    if start_warp==end_warp:
        print(0)
    else:
            
        #ワープで行けるほかの部屋をtree入れる
        n_rooms = i_room+1
        tree=[[] for _ in range(n_rooms)]
        for k,v in rooms.items():
            cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
            for c in cango:
                if c!=v:
                    tree[c].append(v)
                    tree[v].append(c)
            #print(v,cango)
        for i in range(len(tree)):
            tree[i] = set(tree[i])

        
        
        q = deque([(-1,start_warp,0)]) #これでもよい
        
        been=[False]*n_rooms
        been[start_warp]=True
        reach=False
        while q:
            parent,x,time = q.popleft()
            if x==end_warp:
                reach=True
                break
            
            for y in tree[x]:
                if not been[y]:
                    q.append((x,y,time+1))#子ノードを追加
                    been[y]=True
            #print(parent,x,q,time)
        if reach:
            print(time)
        else:
            print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
        
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

CH -= 1
CW -= 1
DH -= 1
DW -= 1

def add(next, i, j, cost):
    if 0 <= i < H and 0 <= j < W and S[i][j] == ".":
        next.append((i, j, cost))

cost = [[10000] * W for _ in range(H)]
cost[CH][CW] = 0
prev = [[None] * W for _ in range(H)]
# Q = heapq.heapify([])
Q = []
for i in range(H):
    for j in range(W):
        heapq.heappush(Q, (cost[i][j], i, j))

while len(Q) > 0:
    _, i, j = heapq.heappop(Q)
    next = []
    add(next, i - 1, j, 0)
    add(next, i + 1, j, 0)
    add(next, i, j - 1, 0)
    add(next, i, j + 1, 0)
    for di in [-2, -1, 0, 1, 2]:
        for dj in [-2, -1, 0, 1, 2]:
            add(next, i + di, j + dj, 1)
    for i2, j2, c in next:
        alt = cost[i][j] + c
        if cost[i2][j2] > alt:
            cost[i2][j2] = alt
            prev[i2][j2] = (i, j)
            heapq.heappush(Q, (alt, i2, j2))

ans = cost[DH][DW]
if ans == 10000:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny, nx = y+dy, x+dx
                if ny<0 or ny>=H or nx<0 or nx>=W:
                    continue
                if maze[ny][nx]=='#':
                    continue
                if (dy, dx) in dirc:
                    if dist[ny][nx]>dist[y][x]:
                        dist[ny][nx] = dist[y][x]
                        Q.append((ny, nx))
                else:
                    if dist[ny][nx]>dist[y][x]+1:
                        dist[ny][nx] = dist[y][x]+1
                        Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()