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
import sys

H, W = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
maze = []

for i in range(H):
    maze.append(list(input()))

check = [[-1 for i in range(W)] for j in range(H)]
number = 0

def bfs(sy, sx):
    global number
    check[sy][sx] = number
    d = deque([[sy, sx]])
    
    while d:
        y, x = d.popleft()
        
        for k, l in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + k, x + l
            
            if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
                continue
            
            if check[new_y][new_x] != -1:
                continue
            
            if maze[new_y][new_x] == '#':
                continue
            
            d.append([new_y, new_x])
            check[new_y][new_x] = number
    
    number += 1
    
for i in range(H):
    for j in range(W):
        if check[i][j] == -1 and maze[i][j] == '.':
            bfs(i, j)


load = [[] for i in range(number)]
for i in range(H):
    for j in range(W):
        
        if check[i][j] != -1:
            
            for k in range(-2, 3):
                for l in range(-2, 3):
                    new_y, new_x = i + k, j + l
                    
                    if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
                        continue
                    
                    f_num = check[i][j]
                    to_num = check[new_y][new_x]
                    
                    if to_num != -1 and to_num != f_num:
                        if not to_num in load[f_num]:
                            load[f_num].append(to_num)
                            load[to_num].append(f_num)

s_num = check[c_h][c_w]
g_num = check[d_h][d_w]

if s_num == g_num:
    print(0)
    sys.exit()

dp = [-1] * number
dp[s_num] = 0

d = deque([s_num])
ans = -1
flg = False
while d:
    if flg:
        break
    
    num = d.popleft()
    
    for i in load[num]:
        if i == g_num:
            ans = dp[num] + 1
            flg = True
            break
        
        if dp[i] != -1:
            continue
            
        dp[i] = dp[num] + 1
        d.append(i)
        
print(ans)

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(0, 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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
from copy import deepcopy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    # print(GW)

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    d = deque([(0, ch, cw)])

    used = deepcopy(GW)
    used[ch][cw] = '#'
    mp = 0
    WP = deque([d])

    # for _ in range(5):
    while d:
        # print(d)
        tmp2 = []
        while d:
            m, h, w = d.popleft()

            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = dh+h, dw+w
                    if not 0 <= nh <= H or not 0 <= nw <= W:
                        continue
                    if used[nh][nw] == '#':
                        continue
                    if (dh, dw) in move:
                        # print(nh, nw)
                        if used[nh][nw] == '#':
                            continue
                        elif used[nh][nw] == 'G':
                            print(mp)
                            return
                        d.append((m, nh, nw))
                        used[nh][nw] = '#'
                        continue

                    if used[nh][nw] == '#':
                        continue
                    # elif used[nh][nw] == 'G':
                    #     print(mp)
                    #     return
                    tmp2.append((m+1, nh, nw))

        # print(tmp2)
        # mp = mp + 1
        for mm, nh, nw in tmp2:
            if used[nh][nw] == '#':
                continue
            elif used[nh][nw] == 'G':
                print(mm)
                return
            d.append((mm, nh, nw))

    print(-1)

if __name__ == '__main__':
    solve()

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 =  s + 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 * w + 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 * w + 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
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

h,w = mp()
ch, cw = mp()
dh,dw = mp()
ch += 1
cw += 1
dh += 1
dw += 1
grid = []
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))
ans_grid = []
for i in range(h):
    u = ["#", "#"]
    a = list(input())
    for j in range(w):
        u.append(a[j])
    u.append("#")
    u.append("#")
    grid.append(u)
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))

for i in range(h+4):
    ans_grid.append([int(1e8)]*(w+4))
# print(grid)
# print(ans_grid)

from collections import deque
def bfs(x,y):
    q = deque([])
    used = set()
    q.append((x,y))
    used.add((x,y))
    ans_grid[x][y] = 0
    while q:
        here = q.popleft()
        move = [(here[0]-1, here[1]),
                (here[0], here[1]-1),
                (here[0], here[1]+1),
                (here[0]+1, here[1])]
        warp = [(here[0]-2, here[1]-2), (here[0]-2, here[1]-1), (here[0]-2, here[1]), (here[0]-2, here[1]+1), (here[0]-2, here[1]+2),
                (here[0]-1, here[1]-2), (here[0]-1, here[1]-1), (here[0]-1, here[1]+1), (here[0]-1, here[1]+2),
                (here[0], here[1]-2), (here[0], here[1]+2),
                (here[0]+1, here[1]-2), (here[0]+1, here[1]-1), (here[0]+1, here[1]+1), (here[0]+1, here[1]+2),
                (here[0]+2, here[1]-2), (here[0]+2, here[1]-1), (here[0]+2, here[1]), (here[0]+2, here[1]+1), (here[0]+2, here[1]+2)]
        for i in range(len(warp)):
            u = warp[i][0]
            v = warp[i][1]
            if grid[u][v] == "." and ans_grid[u][v] > ans_grid[here[0]][here[1]]+1:
                ans_grid[u][v] = min(ans_grid[u][v], ans_grid[here[0]][here[1]]+1)
                q.append((u,v))
        for i in range(len(move)):
            u = move[i][0]
            v = move[i][1]
            if (move[i] not in used or ans_grid[u][v] > ans_grid[here[0]][here[1]]) and grid[u][v] == ".":
                ans_grid[u][v] = min(ans_grid[here[0]][here[1]], ans_grid[u][v])
                q.append((u,v))
                used.add((u,v))
        # print(ans_grid[2:])



bfs(ch,cw)
ans = ans_grid[dh][dw]
# print(ans_grid)
if ans == int(1e8):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections

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:
H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0

pool2 = [tuple(C)]
while(pool2):
    y, x = pool2.pop()
    pool = [(y, x)]
    p = [(y, x)]
    while(pool):
        y, x = pool.pop()
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.append((y+dy, x+dx))
                    p.append((y+dy, x+dx))
    q = []
    for y, x in set(p):
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if y + dy < 0 or H <= y + dy:
                    continue
                if x + dx < 0 or W <= x + dx:
                    continue
                if S[y+dy][x+dx] == "#":
                    continue
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                    V[y+dy][x+dx] = V[y][x] + 1
                    q.append((y+dy, x+dx))
    pool2 += list(set(q))
print(V[D[0]][D[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())
S = []
for i in range(H):
    s = input()
    t = []
    for c in s:
        if c == "#":
            t.append(True)
        else:
            t.append(False)
    S.append(t)

que = set()
que.add((Ch-1, Cw-1))
d = {}
d[(Ch-1, Cw-1)] = 0

def check(newh, neww, dis, c):
    if newh < 0 or newh >= H or neww < 0 or neww >= W:
        return
    if S[newh][neww]:
        return
    if dis == 1:
        if (newh,neww) in d:
            if c < d[(newh,neww)]:
                d[(newh, neww)] = c
                que.add((newh, neww))
        else:
            d[(newh, neww)] = c
            que.add((newh, neww))
    else:
        if (newh,neww) in d:
            if (c+1) < d[(newh,neww)]:
                d[(newh, neww)] = c+1
                que.add((newh, neww))
        else:
            d[(newh, neww)] = c+1
            que.add((newh, neww))
    

while que:
    h, w = que.pop()
    nowc = d[(h,w)]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            check(h+i, w+j, abs(i)+abs(j), nowc)

if (Dh-1, Dw-1) in d:
    print(d[(Dh-1, Dw-1)])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq,collections
h,w = map(int, raw_input().split())
s,t = tuple(map(lambda x:int(x)-1 , raw_input().split())), tuple(map(lambda x:int(x)-1 , raw_input().split()))
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = [(u[0] + i,u[1] + j) for i in [-2,-1,0,+1,+2] for j in [-2,-1,0,+1,+2]]
	return [v for v in ret if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.' and v != u and abs(v[0] - u[0]) + abs(v[1] - u[1])>= 2]
def f(s,t,mat):
	heap,r = [(0,s)], {} 
	while(heap):
		d,u = heapq.heappop(heap)
		r[u] = min(r[u] if u in r else +float('inf'), d)
		if u == t: return d

		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d: 
					r[v] = d
					heapq.heappush(heap,(d,v))
					
		for v in neighbors(u,mat):
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d + 1: 
					r[v] = d + 1
					heapq.heappush(heap,(d+1,v))
	return -1

print f(s,t,mat)

Submission status: Time Limit Exceeded

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

H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
S = [list(input()) for _ in range(H)]

stamp = [[-1 for _ in range(W)] for _ in range(H)]
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = [[-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]]
cnt = 0

def search(x,y):
  if x == gx-1 and y == gy-1:
    print(cnt)
    sys.exit()
  if x < 0 or H-1 < x or y < 0 or W-1 < y or stamp[x][y] != -1:
    return
  elif S[x][y] == "#":
    stamp[x][y] = 0
    return
  stamp[x][y] = 0
  for dx, dy in dxdy:
    search(x+dx,y+dy)
  return

x, y = sx-1, sy-1
search(x,y)

check = True
while check:
  cnt += 1
  for dx, dy in warp:
    search(x+dx,y+dy)
    
  check = False
  for i in stamp:
    for j in i:
      if j == -1:
        check = True

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    

    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    import heapq
    
    inf=10**7
    hq=[]
    heapq.heapify(hq)
    used=[[inf]*(W+4) for _ in range(H+4)]
    
    heapq.heappush(hq,(0,ch,cw))
    used[ch][cw]=0
    
    ans=-1
    while len(hq)!=0:
        cost,i,j=heapq.heappop(hq)
        for k in range(4):
            ii=i+dx[k]
            jj=j+dy[k]
            if S[ii][jj]==".":
                if used[ii][jj] > cost:
                    used[ii][jj]=cost
                    heapq.heappush(hq,(cost,ii,jj))
                
        for k in range(20):
            ii=i+dx2[k]
            jj=j+dy2[k]
            if S[ii][jj]==".":
                if used[ii][jj] > cost:
                    used[ii][jj]=cost+1
                    heapq.heappush(hq,(cost+1,ii,jj))
        

            
    ans=used[dh][dw]
    if ans>=10**6+5:
        ans=-1            
    print(ans)
    
    # for i in range(H+4):
    #     print(used[i])
            

                    
                

main()

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()))
s = []
warp = [[10000000] * w for i in range(h)]
for i in range(h):
    s.append(input())

q = [(ch - 1, cw - 1, 0)]
qi = 0
while qi < len(q):
    i = q[qi][0]
    j = q[qi][1]
    wc = q[qi][2]
    if wc < warp[i][j]:
        warp[i][j] = wc
    if i-1 >= 0 and s[i-1][j] == '.' and wc < warp[i-1][j]:
        q.append((i - 1, j, wc))
    if j-1 >= 0 and s[i][j-1] == '.' and wc < warp[i][j-1]:
        q.append((i, j - 1, wc))
    if i+1 < h and s[i+1][j] == '.' and wc < warp[i+1][j]:
        q.append((i + 1, j, wc))
    if j+1 < w and s[i][j+1] == '.' and wc < warp[i][j+1]:
        q.append((i, j + 1, wc))

    for di in range(max(i-2, 0), min(i+2, h-1)+1):
        for dj in range(max(j-2, 0), min(j+2, w-1)+1):
            if s[di][dj] == '.' and wc + 1 < warp[di][dj]:
                q.append((di, dj, wc + 1))
    qi += 1

if warp[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(warp[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = [[-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]]

    visited = [[10 ** 6] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == 10 ** 6:
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = "".join([input() for _ in range(h)])

start = si*w+sj
goal = gi*w+gj


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def bfs(i, j):
    v = i*w+j
    next_v = deque([v])
    members = set()
    while next_v:
        v = next_v.popleft()
        visited[v] = 1
        members.add(v)
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if visited[v2]:
                continue
            next_v.append(v2)
    return members


visited = [0]*(h*w)
islands = []
for i in range(h):
    for j in range(w):
        if visited[i*w+j]:
            continue
        if fld[i*w+j] == '#':
            continue
        islands.append(bfs(i, j))

# print(islands)

n = len(islands)
edges = [[]for _ in range(n)]


def iterv(s):
    res = set()
    for v in s:
        i, j = divmod(v, w)
        it = [-2, -1, 0, 1, 2]
        for di, dj in product(it, repeat=2):
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            res.add(x*w+y)
    return res


# ここN**2だけど大丈夫？
for i in range(n-1):
    for j in range(i+1, n):
        # i番目の島からいける頂点を列挙する
        for v in iterv(islands[i]):
            if v in islands[j]:
                edges[i].append(j)
                edges[j].append(i)


for i in range(n):
    if start in islands[i]:
        start_island = i
    if goal in islands[i]:
        goal_island = i

INF = 10**18


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)
    return dist


ans = bfs(start_island)[goal_island]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
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

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

# スペース区切りの整数の入力
H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())

#配列の入力
S = [list(input()) for _ in range(H)]
MAX = float('inf')
lst = [[MAX for _ in range(W)] for _ in range(H)]

def dfs(h ,w, warp_flg, warp_num):
    if h > H-1 or w > W-1 or h < 0 or w < 0:
        return
    if S[h][w] == '#':
        return
    
    if warp_num < lst[h][w]:
        lst[h][w] = warp_num
    else:
        return
    
    dfs(h-1, w, False, warp_num)
    dfs(h+1, w, False, warp_num)
    dfs(h, w-1, False, warp_num)
    dfs(h, w+1, False, warp_num)

    for i in range(-2,3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            dfs(h+i, w+j, True, warp_num+1)

dfs(Ch-1, Cw, False, 0)
dfs(Ch+1, Cw, False, 0)
dfs(Ch, Cw-1, False, 0)
dfs(Ch, Cw+1, False, 0)

for i in range(-2,3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        dfs(Ch+i, Cw+j, True, 1)

if lst[Dh][Dw] == MAX:
    print(-1)
else:
    print(lst[Dh][Dw])