Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                visited[i][j] = -2
    visited[ch][cw] = 0
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    telpo = [[i,j] for i in range(-2, 3) for j in range(-2, 3)]

    q_walk = deque([[ch, cw]])
    q_telpo = deque([])
    while q_walk:
        yw, xw = q_walk.popleft()
        # 行った場所を管理
        q_telpo.append([yw, xw])
        for i, j in walk:
            ny, nx = yw + i, xw + j
            if ny < 0 or h <= ny or nx < 0 or w <= nx:
                continue
            if visited[ny][nx] == -1:
                # 行ったことあれば0にしていく
                visited[ny][nx] = visited[yw][xw]
                q_walk.append([ny, nx])
        # 歩ける場所なくなったらワープ
        if len(q_walk) == 0:
            while q_telpo:
                yt, xt = q_telpo.popleft()
                for i, j in telpo:
                    my, mx = yt + i, xt + j
                    if my < 0 or h <= my or mx < 0 or w <= mx:
                        continue
                    if visited[my][mx] == -1:
                        visited[my][mx] = visited[yt][xt] + 1
                        q_walk.append([my, mx])
    print(visited[dh][dw])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from ctypes import *

class edge(Structure):
    _fields_ = [("cost", c_int32), ("to", c_int32)]

    def __init__(self, x, y):
        self.to = x
        self.cost = y

    def __lt__(self, r):
        return self.cost < r.cost

class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost):
        self.G[X].append(edge(Y, cost))

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, edge(st, 0))
        self.dist[st] = 0
        while len(q):
            p = heapq.heappop(q)
            cost = p.cost
            node = p.to
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to.cost
                to_node = to.to
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, edge(to_node, to_cost))

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INF = 10**10
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

costs = [[INF for _ in range(w)] for _ in range(h)]
costs[ch-1][cw-1] = 0
queue = deque()
queue.append((ch-1, cw-1))
while len(queue) > 0:
    x, y = queue.popleft()
    for i in range(4):
        dx = [-1, 0, 1, 0][i]
        dy = [0, -1, 0, 1][i]
        nx = x+dx
        ny = y+dy
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if mat[nx][ny] == "#":
            continue
        if costs[nx][ny] > costs[x][y]:
            costs[nx][ny] = costs[x][y]
            queue.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x+i
            ny = y+j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if mat[nx][ny] == "#":
                continue
            if costs[nx][ny] > costs[x][y] + 1:
                costs[nx][ny] = costs[x][y] + 1
                queue.append((nx, ny))
if costs[dh-1][dw-1] == INF:
    print(-1)
else:
    print(costs[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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
    S = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > cnt[h][w]:
                    cnt[nh][nw] = cnt[h][w]
                    Q.append([nh,nw])
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w] + 1
                        visited[nh][nw] = True
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
from collections import deque 
INF = float('INF') #INFの宣言
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
mymap = []
for h in range(H):
    mymap += [list(input())]
 
 
d = [ [INF for w in range(W)] for h in range(H) ] #各地点までの最短距離の配列,INFで初期化
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  #移動4方向のベクトル
 
def bfs(h, w, res):
    #warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = res            #スタート地点のwarp回数をresにする
    # dequeが空になるまでループ
    while mydeque:
        #dequeの先頭を取り出す
        y, x = mydeque.popleft()
        #取り出してきた状態がGoalなら探索をやめる
        #if y == Dh and x == Dw:
            #print(res)
            #sys.exit()
            #break
        #移動4方向をループ
        for i in range(4):
            #移動後の点を(nx, ny) とする
            nx, ny = x + dx[i], y + dy[i]
            #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
            if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] >  d[y][x]:
                #print(ny, nx, d[ny][nx], mymap[ny][nx])
                if  mymap[ny][nx] != '#' : 
                #移動できるならdequeに入れ、その点の距離をresで確定する
                    mydeque.appendleft([ny, nx])
                    d[ny][nx] = d[y][x]
                    #if ny == Dh and nx == Dw:
                    #            print(res)
                elif mymap[ny][nx] == '#' :
                    #warpの可能性を探索する                
                        for aa in range(-2,3):
                            for bb in range(-2,3):
                                nny, nnx = y + aa, x + bb
                                if 0 <= nnx and nnx < W and 0 <= nny and nny < H and d[nny][nnx] ==  INF and mymap[nny][nnx] != '#':
                                    d[nny][nnx] = d[y][x] + 1
                                    mydeque.append([nny, nnx])

    return
 

bfs(Ch,Cw,0)
#for dd in d:
#    print(dd)
if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import heapq
from array import array

class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost):
        tmp = array('i')
        tmp.append(cost)
        tmp.append(Y)
        self.G[X].append(tmp)

    def dijkstra(self, st):
        q = []
        tmp = array('i')
        tmp.append(0)
        tmp.append(st)

        heapq.heappush(q, tmp)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p[0]
            node = p[1]
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to[0]
                to_node = to[1]
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    tmp = array('i')
                    tmp.append(to_cost)
                    tmp.append(to_node)
                    heapq.heappush(q, tmp)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy-=1
sx-=1
gy,gx = map(int,input().split())
gy,gx = gy-1,gx-1
grid = [0] * H
done = [[0]*W for _ in range(H)]
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done[sy][sx] =1
for i in range(H):
    grid[i] = input()

walk_q = deque()
magic_q = deque()
def walk_bfs(magic_count):
    y,x = walk_q.popleft()
    magic_q.append([y,x])
    for new_y,new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
            if not done[new_y][new_x]:
                done[new_y][new_x] = 1
                cost[new_y][new_x] = min(cost[new_y][new_x],magic_count)

                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])

def magic_bfs(magic_count):
    y,x = magic_q.popleft()
    for y_add in range(-2,3):
        for x_add in range(-2,3):
            if y_add == 0 and x_add == 0:
                continue
            new_y = y+y_add
            new_x = x+x_add

            if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
                if not done[new_y][new_x]:
                    done[new_y][new_x] = 1
                    cost[new_y][new_x] = min(cost[new_y][new_x],magic_count+1)

                    walk_q.append([new_y,new_x])

walk_q.append([sy,sx])
magic_q.append([sy,sx])
magic_count = 0
# 毎回、既にqueueにあるやつ（初回を除く）が、done、costの処理をされない？
# や、初回以外は常にどっかしらで「発見」される
while walk_q or magic_q:
    while walk_q:
        walk_bfs(magic_count)
    while magic_q:
        magic_bfs(magic_count)
    magic_count += 1
if done[gy][gx]:
    print(cost[gy][gx])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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
    S = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > cnt[h][w]:
                    cnt[nh][nw] = cnt[h][w]
                    Q.appendleft([nh,nw])
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w] + 1
                        visited[nh][nw] = True
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
Ch, Cw = (int(i) - 1 for i in input().split())
Dh, Dw = (int(i) - 1 for i in input().split())
G = [list(sys.stdin.readline().strip()) for _ in range(H)]

def bfs(start):
    zeroQ = deque()
    oneQ = deque()
    zeroQ.append(start)
    dist[start[1]][start[0]] = 0

    while zeroQ or oneQ:
        if zeroQ:
            x, y = zeroQ.popleft()
        else:
            x, y = oneQ.popleft()
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                
                if not(0 <= nx < W and 0 <= ny < H):
                    continue
                if G[ny][nx] == '#':
                    continue
                if abs(dx) + abs(dy) == 0:
                    continue
                
                cost = 0 if abs(dx) + abs(dy) == 1 else 1
                
                if dist[ny][nx] <= dist[y][x] + cost:
                    continue
                dist[ny][nx] = dist[y][x] + cost
                
                if cost == 0:
                    zeroQ.append((nx, ny))
                else:
                    oneQ.append((nx, ny))

dist = [[10 ** 9 for _ in range(W)] for _ in range(H)]

bfs((Cw, Ch))
# for g in dist:
#     print(g)
if dist[Dh][Dw] == 10 ** 9:
    print(-1)
else:
    print(dist[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
from collections import deque 
INF = float('INF') #INFの宣言
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
mymap = []
for h in range(H):
    mymap += [list(input())]
 
 
d = [ [INF for w in range(W)] for h in range(H) ] #各地点までの最短距離の配列,INFで初期化
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  #移動4方向のベクトル
 
def bfs(h, w, res):
    #warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = res            #スタート地点のwarp回数をresにする
    # dequeが空になるまでループ
    while mydeque:
        #dequeの先頭を取り出す
        y, x = mydeque.popleft()
        #取り出してきた状態がGoalなら探索をやめる
        if y == Dh and x == Dw:
            print(res)
            #break
            sys.exit()
            #break
        #移動4方向をループ
        for i in range(4):
            #移動後の点を(nx, ny) とする
            nx, ny = x + dx[i], y + dy[i]
            #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
            if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] ==  INF:
                #print(ny, nx, d[ny][nx], mymap[ny][nx])
                if  mymap[ny][nx] != '#' : 
                #移動できるならdequeに入れ、その点の距離をresで確定する
                    mydeque.appendleft([ny, nx])
                    d[ny][nx] = res
                    if ny == Dh and nx == Dw:
                                print(res)
                                sys.exit()
                            
        #for dd in d:
        #    print(dd)
        #print()           
                    
    #warpの可能性を探索する                
    for a in range(H):
        for b in range(W):
            if d[a][b] == res:
                for aa in range(-2,3):
                    for bb in range(-2,3):
                        nny, nnx = a + aa, b + bb
                        if 0 <= nnx and nnx < W and 0 <= nny and nny < H and d[nny][nnx] ==  INF and mymap[nny][nnx] != '#':
                            d[nny][nnx] = d[y][x] + 1
                            mydeque.append([nny, nnx])
                            if nny == Dh and nnx == Dw:
                                print(res+1)
                                #break
                                sys.exit()
    res += 1
    if not mydeque:
        return
    else:
        ay, ax = mydeque.popleft()
    #print(ay, ax)
    bfs(ay,ax,res)
        #for dd in d:
        #    print(dd)
        #x
    return
 

bfs(Ch,Cw,0)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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
    S = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if visited[nh][nw] == False:
                    cnt[nh][nw] = cnt[h][w]
                    visited[nh][nw] = True
                    Q.appendleft([nh,nw])
                else:
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w]
                        Q.appendleft([nh,nw])
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w] + 1
                        visited[nh][nw] = True
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
   


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def flatten(l):
        return list(itertools.chain.from_iterable(l))

    def list_unique(arr):
        return list(map(list, set(map(tuple, arr))))

    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        # n_yx_s = list(map(list, set(map(tuple, n_yx))))
        n_yx_s = n_yx
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        # '一発目ワープ不要'
        print(telepo_cnt)
        exit()
    else:
        q = deque([telepo(maze, _visited, _yx, h, w)])
        while len(q[0]) > 0:
            p = list()
            r = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                # print(maze)
                # print(_visited)
                # print(nyx[0])
                # print(nyx[1])
                ans, _visted, _yx = maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    # 'ワープからのゴール'
                    print(telepo_cnt)
                    exit()
                else:
            #         for i in telepo(maze, visited, _yx, h, w):
            #             p.append(i)
            # print(p)
            # q.append(p)
                    #     print('p', p)
                    # #     p = list(map(list, set(map(tuple, p))))
                    # #     print('p#', p)
                    # # print(telepo(maze, visited, _yx, h, w))
                    # print('_yx', _yx)
                    r.append(telepo(maze, _visited, _yx, h, w))
                    # print(r)
            r = flatten(r)
            # print(r)
            r = list_unique(r)
            # print(r)
            q.append(r)
        # 'ワープしても無理'
        print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
   


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def flatten(l):
        return list(itertools.chain.from_iterable(l))

    def list_unique(arr):
        return list(map(list, set(map(tuple, arr))))

    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        # n_yx_s = list(map(list, set(map(tuple, n_yx))))
        n_yx_s = n_yx
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        # '一発目ワープ不要'
        print(telepo_cnt)
        exit()
    else:
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            p = list()
            r = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                # print(maze)
                # print(_visited)
                # print(nyx[0])
                # print(nyx[1])
                ans, _visted, _yx = maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    # 'ワープからのゴール'
                    print(telepo_cnt)
                    exit()
                else:
            #         for i in telepo(maze, visited, _yx, h, w):
            #             p.append(i)
            # print(p)
            # q.append(p)
                    #     print('p', p)
                    # #     p = list(map(list, set(map(tuple, p))))
                    # #     print('p#', p)
                    # # print(telepo(maze, visited, _yx, h, w))
                    # print('_yx', _yx)
                    r.append(telepo(maze, visited, _yx, h, w))
                    # print(r)
            r = flatten(r)
            # print(r)
            r = list_unique(r)
            # print(r)
            q.append(r)
        # 'ワープしても無理'
        print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    dist[i][j]=k
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            heappush(hp,(nk,ni,nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
   


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def flatten(l):
        return list(itertools.chain.from_iterable(l))

    def list_unique(arr):
        return list(map(list, set(map(tuple, arr))))

    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        # n_yx_s = list(map(list, set(map(tuple, n_yx))))
        n_yx_s = n_yx
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        # '一発目ワープ不要'
        print(telepo_cnt)
        exit()
    else:
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            p = list()
            r = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                # print(maze)
                # print(_visited)
                # print(nyx[0])
                # print(nyx[1])
                ans, _visted, _yx = maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    # 'ワープからのゴール'
                    print(telepo_cnt)
                    exit()
                else:
                    # for i in telepo(maze, visited, _yx, h, w):
                    #     p.append(i)
                    #     print('p', p)
                    # #     p = list(map(list, set(map(tuple, p))))
                    # #     print('p#', p)
                    # # print(telepo(maze, visited, _yx, h, w))
                    # print('_yx', _yx)
                    r.append(telepo(maze, visited, _yx, h, w))
                    # print(r)
            r = flatten(r)
            # r = list_unique(flatten(r))
            # print('r', r)           
            q.append(r)
        # 'ワープしても無理'
        print(-1)
if __name__ == '__main__':
    main()