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:
def main():
    import heapq
    from collections import deque


    def normal_bfs():
        queue = deque([(C_h, C_w)])
        seen = {(C_h, C_w)}
        while queue:
            i, j = queue.popleft()
            if (i, j) == (D_h, D_w):
                return 0
            for offset in (1, -1):
                i_next = i + offset
                j_next = j + offset
                if ok(i_next, j) and (i_next, j) not in seen:
                    queue.append((i_next, j))
                    seen.add((i_next, j))
                if ok(i, j_next) and (i, j_next) not in seen:
                    queue.append((i, j_next))
                    seen.add((i, j_next))
        return -1



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

    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    C_h -= 1
    C_w -= 1
    D_h, D_w = map(int, input().split())
    D_h -= 1
    D_w -= 1
    S = [[None] * W for _ in range(H)]
    for i in range(H):
        for j, c in enumerate(input()):
            S[i][j] = c

    if normal_bfs() == 0:
        print(0)
        exit()

    queue = [(0, (C_h, C_w))]
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

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


main()

Submission status: Time Limit Exceeded

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

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    else:
        wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


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


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data = [[0]*W for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


def trans(h, w):
    return W*(h) + w


P = [(0, -1), (0, 1), (1, 0), (-1, 0)]
DXY = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
G = [[] for i in range(H*W)]
H_L = [i for i in range(H)]
W_L = [i for i in range(W)]
for i in H_L:
    for j in W_L:
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H:
                    if 0 <= dy+j < W:
                        if data[dx+i][dy+j] == 1:
                            u, v = trans(i, j), trans(dx+i, dy+j)
                            G[u].append((v, 0))
                            G[v].append((u, 0))
            for dx, dy in DXY:
                if 0 <= dx+i < H:
                    if 0 <= dy+j < W:
                        if data[dx+i][dy+j] == 1:
                            u, v = trans(i, j), trans(dx+i, dy+j)
                            G[u].append((v, 1))
                            G[v].append((u, 1))


D = [10**6+100 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**6+100:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    xy=[(1,0),(-1,0),(0,1),(0,-1)]
    #wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]
    wp1=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1)]
    wp2=[(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

    h,w=map(int,input().split())
    c1,c2=map(int,input().split())
    d1,d2=map(int,input().split())
    d=[list(input()) for i in range(h)]
    d[c1-1][c2-1]=0
    p=set([(c1-1,c2-1)])
    while len(p):
        a,b=p.pop()
        for x,y in xy:
            x+=a
            y+=b
            if 0<=x<h and 0<=y<w and d[x][y]!="#":
                if d[x][y]=="." or d[x][y]>d[a][b]:
                    d[x][y]=d[a][b]
                    p.add((x,y))
        for x,y in wp1:
            x+=a
            y+=b
            if 0<=x<h and 0<=y<w and d[x][y]!="#":
                if d[x][y]=="." or d[x][y]>d[a][b]+1:
                    d[x][y]=d[a][b]+1
                    p.add((x,y))
        for x,y in wp2:
            x+=a
            y+=b
            if 0<=x<h and 0<=y<w and d[x][y]!="#":
                if d[x][y]=="." or d[x][y]>d[a][b]+1:
                    d[x][y]=d[a][b]+1
                    p.add((x,y))
    #    print(p)
    #    print(d)

    print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import time
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
t1 = time.time()
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
    if time.time()-t1 >= 1.90:
        print(-1)
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from functools import reduce
from queue import Queue

H, W = list(map(int, input().split(" ")))
current_h, current_w = list(map(int, input().split(" ")))
current_h -= 1
current_w -= 1
goal_h, goal_w = list(map(int, input().split(" ")))
goal_h -= 1
goal_w -= 1

table = [list(input()) for _ in range(H)]


class DFS:

    def __init__(self, table, current_h, current_w):
        self.table = table
        self.current_h = current_h
        self.current_w = current_w
        self.islands = []
        self.start_island_index = -1
        self.end_island_index = -1

    def delta(self, h, w):
        return [(h+1, w), (h, w-1), (h, w), (h, w+1), (h-1, w)]

    def dfs(self, start_h, start_w):
        next = self.delta(start_h, start_w)
        island = [(start_h, start_w)]
        if start_h == self.current_h and start_w == self.current_w:
            self.start_island_index = len(self.islands)

        for h, w in next:
            if h == self.current_h and w == self.current_w:
                self.start_island_index = len(self.islands)
            if h == goal_h and w == goal_w:
                self.end_island_index = len(self.islands)
            if not(0 <= h < H and 0 <= w < W):
                continue
            elif self.table[h][w] == "#":
                continue
            else:
                island.append((h, w))
                self.table[h][w] = "#"
                next.extend(self.delta(h, w))
        self.islands.append(island)

    def make_islands(self):
        for h in range(H):
            for w in range(W):
                if self.table[h][w] == ".":
                    self.dfs(h, w)

    def delta_five(self, pos):
        delta = []
        h = pos[0]
        w = pos[1]
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                delta.append((h+dh, w+dw))
        return delta

    def make_islands_graph(self):
        islands_graph = []
        for start_island_index in range(len(self.islands)):
            for end_island_index in range(len(self.islands)):
                if start_island_index == end_island_index:
                    continue
                if self.is_connect(self.islands[start_island_index], self.islands[end_island_index]):
                    islands_graph.append((start_island_index, end_island_index))
        return islands_graph

    def is_connect(self, islands_a, islands_b):
        a = set(reduce(lambda a, b: a + b, map(self.delta_five, islands_a)))
        for h, w in islands_b:
            if (h, w) in a:
                return True
        return False

class BFS:

    def __init__(self, length_of_islands, graph, start_island_index, end_island_index):
        self.islands = [0 for i in range(0, length_of_islands)]
        self.graph = graph
        self.start = start_island_index
        self.end = end_island_index

    def bfs(self, start, end):
        q = Queue()
        q.put(start)
        count = 0
        while not q.empty():
            now = q.get()

            if now == end:
                return count
            if self.islands[now] == -1:
                continue
            for s, e in self.graph:
                if self.islands[s] == -1:
                    continue
                if s == now:
                    q.put(e)
            self.islands[now] = -1
            count += 1
        return -1

dfs = DFS(table, current_h, current_w)
dfs.make_islands()
graph = dfs.make_islands_graph()
bfs = BFS(len(dfs.islands), graph, dfs.start_island_index, dfs.end_island_index)
print(bfs.bfs(dfs.start_island_index, dfs.end_island_index))

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()
mi=inf
while(stack):
    cost,xx,yy=heappop(stack)
    if xx==x and yy==y:
        mi=min(mi,cost)
        break
    vis[xx][yy] = 1
    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    heappush(stack,[cost,xx+i,yy+j])
                else:
                    heappush(stack, [cost+1, xx + i, yy + j])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]

    ncon_num = 0
    nodes = []
    idx = {}
    groups = {}
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                idx[(h, w)] = len(nodes)
                groups[h, w] = None
                nodes.append((h, w))
    N = len(nodes)
    uf = UnionFind(N)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            for i in range(4):
                nnh, nnw = h + dh[i], w + dw[i]
                if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                    J = idx[nnh, nnw]
                    uf.unite(I, J)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            # print(I, uf.members(I))
            if groups[nodes[I]] is None:
                groups[nodes[I]] = ncon_num
                for k in uf.members(I):
                    groups[nodes[k]] = ncon_num
                ncon_num += 1

    if ncon_num == 1:
        print(0)
        exit()

    ncon = len(set(groups.values()))
    start_con, goal_con = groups[Ch, Cw], groups[Dh, Dw]
    # print(ncon, start_con, goal_con)
    # print(groups)
    
    dist_mat = [[float("inf")] * ncon for _ in range(ncon)]
    for k in range(ncon):
        dist_mat[k][k] = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nnh, nnw = h + ddh, w + ddw
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        J = idx[nnh, nnw]
                        if I != J:
                            # print(I, J, groups[nodes[I]], groups[nodes[J]], uf.same(I, J))
                            if not uf.same(I, J):
                                di = groups[nodes[I]]
                                dj = groups[nodes[J]]
                                dist_mat[di][dj] = 1

    # 作成したグラフでDijkstra
    dist = [float("inf")] * ncon
    dist[start_con] = 0
    queue = [(0, start_con)]
    while queue:
        dc, c = heappop(queue)
        if dist[c] < dc:
            continue

        for cc in range(ncon):
            cost = dist_mat[c][cc]
            if dist != float("inf") and dist[cc] > dist[c] + cost:
                dist[cc] = dist[c] + cost
                heappush(queue, (dist[cc], cc))

    if dist[goal_con] == float("inf"):
        print(-1)
    else:
        print(dist[goal_con])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[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)

#ワープで行けるほかの部屋をpathに入れる
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])
    
# path = [[False]*n_rooms 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:
#             path[v][c]=True
#             path[c][v]=True
#     #print(v,cango)

# #pathをtreeに
# tree=[[] for _ in range(n_rooms)]
# for i in range(n_rooms):
#     for j in range(i+1,n_rooms):
#         if path[i][j]:
#             tree[i].append(j)
#             tree[j].append(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)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

from collections import deque
maze = []
for i in range(H):
    maze.append(list(input()))
times = [[10000000]*W for i in range(H)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
que = deque([])
que.append((Ch, Cw))
times[Ch][Cw] = 0
cnt = 0
flag = 0
while flag==0:
    loc = deque([])
    while que:
        p = que.popleft()
        wallflag = 0
        if p[0] == Dh and p[1] == Dw:
            times[Dh][Dw] = cnt
            flag = 1
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==10000000):
                que.append((nh, nw))
                times[nh][nw] = cnt
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]=="#"):
                wallflag = 1
        if wallflag ==1:
            loc.append(p)
    que = deque([])
    while loc:
        p = loc.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                nh = p[0] + i
                nw = p[1] + j
                if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==10000000):
                    que.append((nh, nw))
    if len(que)==0:
        break
    cnt += 1

if times[Dh][Dw] == 10000000:
    print(-1)
else:
    print(times[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = []
for h in range(H):
    S.append(list(input()))
H -= 1;W -= 1;CH -= 1;CW -= 1;DH -= 1;DW -= 1
from collections import deque
Q = deque([[CH,CW,0]])
ans = 9999999999999999999999
able = False
while Q:
    q = Q.popleft()
    for w in range(-2,3):
        for h in range(-2,3):
            # 場外判定
            # from IPython.core.debugger import Pdb; Pdb().set_trace()
            if q[0] + h >= 0 and q[0] + h <= H and q[1] + w >= 0 and q[1] + w <= W:
                # 壁判定
                if S[q[0]+h][q[1]+w] != '#':
                    # 動かないのは処理しない
                    if w == 0 and h == 0:
                        pass
                    # 徒歩判定(4パターン)
                    elif (w == -1 and h == 0) or (w == 0 and h == -1) or (w == 1 and h == 0) or (w == 0 and h == 1):
                            # ゴールの場合
                            if q[0]+h == DH and q[1]+w == DW:
                                ans = min(ans,q[2])
                                able = True
                                if ans == 0:
                                  print(ans)
                                  exit()
                            # 未処理の場合
                            elif S[q[0]+h][q[1]+w] == '.':
                                S[q[0]+h][q[1]+w] = str(q[2])
                                Q.append([q[0]+h,q[1]+w,q[2]])
                            # 処理済の場合
                            else:
                                if int(S[q[0]+h][q[1]+w]) > q[2]:
                                    S[q[0]+h][q[1]+w] = str(q[2])
                                    Q.append([q[0]+h,q[1]+w,q[2]])
                    # ワープの場合
                    else:
                        if q[0]+h == DH and q[1]+w == DW:
                            ans = min(ans,q[2]+1)
                            able = True
                        elif S[q[0]+h][q[1]+w] == '.':
                            S[q[0]+h][q[1]+w] = str(q[2]+1)
                            Q.append([q[0]+h,q[1]+w,q[2]+1])
                        else:
                            if int(S[q[0]+h][q[1]+w]) > q[2]+1:
                                S[q[0]+h][q[1]+w] = str(q[2]+1)
                                Q.append([q[0]+h,q[1]+w,q[2]+1])
                            
print(ans) if able else 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())
maze_ini = []
for h in range(H):
    maze_ini.append(list(input()))
    
maze = maze_ini
maze[CH-1][CW-1] = "s"
maze[DH-1][DW-1] = "g"

INF = 10**8

d = [[INF for w in range(W)] for h in range(H)] # 各点までの最短距離配列
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#     →,↑,←,↓

ddx = [0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1]
ddy = [2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]

from collections import deque
queue = deque([])

queue.append((DW-1, DH-1))

d[DH-1][DW-1] = 0

while len(queue):
    p = queue.popleft()
    if p == (CW-1, CH-1):
        break

    # 4方向を探索
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#':
            queue.append((nx, ny))
            d[ny][nx] = min(d[ny][nx], d[p[1]][p[0]])

    # ワープ
    for i in range(16):
        nx = p[0] + ddx[i]
        ny = p[1] + ddy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#' and d[ny][nx] > d[p[1]][p[0]]:
            queue.append((nx, ny))
            d[ny][nx] = d[p[1]][p[0]] + 1
            
if d[CH-1][CW-1] == INF:
    print(-1)
else:
    print(d[CH-1][CW-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
  if reach[x][y] < score:
    #print(z,score)
    continue
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.append([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])