Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


def main():

    def f(hi, wi):
        return hi * w + wi


    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    hp = [[0, f(sh, sw)]]
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while hp:
        d, i = heappop(hp)
        hi, wi = divmod(i, w)

        if d != dist[hi][wi]:
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        cost = 0
                    else:
                        cost = 1

                    dist_now = d + cost
                    if dist_now < dist[nh][nw]:
                        dist[nh][nw] = dist_now
                        heappush(hp, [dist_now, f(nh, nw)])

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def Walk(X, Y):
    return [[X-1, Y], [X+1, Y], [X, Y-1], [X, Y+1]]

def Magic(X, Y):
    Ret = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            Ret.append([X+x, Y+y])
    return Ret

D = [[float("inf")]*W for _ in range(H)]
D[Ch-1][Cw-1] = 0

Used = [[False]*W for _ in range(H)]

que = [(0, [Ch-1, Cw-1])]
while que:
    c, pos = heapq.heappop(que)
    if Used[pos[0]][pos[1]]:
        continue
    D[pos[0]][pos[1]] = c
    Used[pos[0]][pos[1]] = True
    if Dh - 1 == pos[0] and Dw -1 == pos[1]:
        break
    for pos_to in Walk(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    heapq.heappush(que, (c, pos_to))
    for pos_to in Magic(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    heapq.heappush(que, (c+1, pos_to))
if D[Dh-1][Dw-1] == float("inf"):
    print(-1)
else:
    print(D[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W = map(int, input().split())
ori = list(map(int, input().split()))
dis = list(map(int, input().split()))
# S = [0] * H
S = np.zeros([H, W])
for i in range(H):
    S[i] = list(map(lambda c: 1 if c == '#' else 0, input()))

D = 10 ** 7

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

row = []
col = []
dist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == 1: continue
        for hh in range(-2, 3):
            if not 0 <= h + hh < H: continue
            for ww in range(-2, 3):
                if not (0 <= h + hh < H and 0 <= w + ww < W): continue
                if hh == ww == 0: continue
                if S[h+hh][w+ww] == 1: continue
                if abs(hh) + abs(ww) == 1:
                    d = 1
                else:
                    d = D
                row.append(co_num(h, w))
                col.append(co_num(h+hh, w+ww))
                dist.append(d)
#                 col.append(co_num(h, w))
#                 row.append(co_num(h+hh, w+ww))
#                 dist.append(d)
                
d = dijkstra(csr_matrix((dist, (row, col)), shape=[H*W, H*W]), directed=True, indices=co_num(ori[0]-1, ori[1]-1))

if d[co_num(dis[0]-1, dis[1]-1)] == np.inf:
    print(-1)
else:
    print(int(d[co_num(dis[0]-1, dis[1]-1)] // D))

# d.reshape([H, W])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch+1, cw+1, dh+1, dw+1

s =[[-1 for j in range(w+4)] for i in range(h+4)]
for i in range(h):
  a = input()
  for j in range(2, w+2):
    s[i+2][j] = w*h+1 if a[j-2]=='.' else -1

    
#for i in s:
#  print(i)
q1 = deque([[ch,cw]])
s[ch][cw] = 0
while(s[dh][dw] == w*h+1 and q1):
  q2 = q1.copy()
  while q1:
    now = q1.popleft()
    nows = s[now[0]][now[1]]
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] == -1):
        continue
      elif(s[nh][nw] > nows):
        s[nh][nw] = nows
        q1.append([nh, nw])
        q2.append([nh, nw])
 

  while q2:
    now = q2.popleft()
    nows = s[now[0]][now[1]]
    for i in range(-2,3):
      for j in range(-2,3):
        nh, nw = now[0]+i, now[1]+j
        if(s[nh][nw] == -1):
          continue
        elif(s[nh][nw] > nows+1):
          s[nh][nw] = nows+1
          q1.append([nh, nw])

if(s[dh][dw] == w*h+1):
  print(-1)
else:
  print(s[dh][dw])

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**6):
    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:
import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))
import collections
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0] + i,u[1] + j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u: ret.append(v)
	return ret
def f(s,t,mat):
	heap = [(0,s)]
	r = {} 
	while(heap):
		d,u = heapq.heappop(heap)
		if u in r and d >= r[u]: continue
		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:
					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:
					heapq.heappush(heap,(d+1,v))
	return -1

def g(s,t,mat):
	q = collections.deque([s])
	vis = set()
	while(q):
		u = q.popleft()
		vis.add(u)
		if u == t:
			return True
		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] < len(mat) and 0 <= v[1] < len(mat[0]) and mat[v[0]][v[1]] == '.' and v not in vis:
				vis.add(v)
				q.append(v)

	return False



if False:# g(s,t,mat):
	print 0
else:
	print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from heapq import *
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return 0
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
        return 1
for x in range(h*w):
        i=x%h
        j=x//h
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
            else:
                f(i,j,i+2,j)
                f(i,j,i+1,j+1)
                
                
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
            else:
                f(i,j,i,j+2)
                f(i,j,i-1,j+1)
        
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j+1)

        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,W = map(int,input().split())
    C = list(map(int,input().split()))
    D = list(map(int,input().split()))
    S = [input().rstrip() for i in range(H)]

    deq = deque()
    deq.append([C[0]-1,C[1]-1])
    cost = [[-1 for j in range(W)] for i in range(H)]
    cost[C[0]-1][C[1]-1] = 0
    checked = []

    while deq:
        nowp = deq.popleft()
        nowc = cost[nowp[0]][nowp[1]]
        if nowp in checked:
            continue
        checked.append(nowp)
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0) & (j == 0):
                    continue
                elif [nowp[0]+i,nowp[1]+j] in checked:
                    continue
                elif (abs(i) + abs(j) == 1):
                    if (0 <= nowp[0] + i) & (nowp[0] + i < H):
                        if (0 <= nowp[1] + j) & (nowp[1] + j < W):
                            if S[nowp[0]+i][nowp[1]+j] == '.':
                                if cost[nowp[0]+i][nowp[1]+j] == -1:
                                    cost[nowp[0]+i][nowp[1]+j] = nowc
                                else:
                                    cost[nowp[0]+i][nowp[1]+j] = min(nowc,cost[nowp[0]+i][nowp[1]+j])
                                deq.append([nowp[0]+i,nowp[1]+j])
                else:
                    if cost[nowp[0]][nowp[1]] != -1:
                        if (0 <= nowp[0] + i) & (nowp[0] + i < H):
                            if (0 <= nowp[1] + j) & (nowp[1] + j < W):
                                if S[nowp[0]+i][nowp[1]+j] == '.':
                                    if cost[nowp[0]+i][nowp[1]+j] == -1:
                                        cost[nowp[0]+i][nowp[1]+j] = nowc + 1
                                    else:
                                        cost[nowp[0]+i][nowp[1]+j] = min(nowc+1,cost[nowp[0]+i][nowp[1]+j])
                                    deq.append([nowp[0]+i,nowp[1]+j])

    res = cost[D[0]-1][D[1]-1]
    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


def f(hi, wi):
    return hi * w + wi


h, w = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())
s = [input() for _ in range(h)]
INF = 10 ** 9

sh -= 1
sw -= 1
gh -= 1
gw -= 1

hp = [[0, f(sh, sw)]]
dist = [[INF] * w for _ in range(h)]
dist[sh][sw] = 0

while hp:
    d, i = heappop(hp)
    hi, wi = divmod(i, w)

    if d != dist[hi][wi]:
        continue

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            nh = hi + dh
            nw = wi + dw
            if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                if abs(dh) + abs(dw) == 1:
                    cost = 0
                else:
                    cost = 1

                dist_now = d + cost
                if dist_now < dist[nh][nw]:
                    dist[nh][nw] = dist_now
                    heappush(hp, [dist_now, f(nh, nw)])

ans = dist[gh][gw]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
sys.setrecursionlimit(1000000)
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**18]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

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
                    


print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def bfs(sx, sy):
  que = deque([[sy,sx]])
  D =  [(0,1), (1,0), (0,-1), (-1,0)]

  DD =  [(-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) ]

  while que:
    y,x = que.popleft()
    flag = 1
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "#"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]
          que.append([y+j,x+i])
        elif(dist>G[y][x]):
          G[y+j][x+i] = G[y][x]
          que.append([y+j,x+i])
      elif(flag==1):
        flag = 0
        for k,l in DD:
            if(x+k<0 or y+l<0 or x+k>W-1 or y+l>H-1):
                continue
            dist = G[y+l][x+k]
            #print(G[y][x])
            if(G[y+l][x+k] != "#"):
                if(type(G[y+l][x+k]) is str):
                    G[y+l][x+k] = G[y][x]+1
                    que.append([y+l,x+k])
                elif(dist>G[y][x]+1):
                    G[y+l][x+k] = G[y][x]+1
                    que.append([y+l,x+k])

sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H, W = map(int, input().split())
magicY, magicX = map(int, input().split())
goalY, goalX = map(int, input().split())
G = [list(input()) for i in range(H)]
G[magicY-1][magicX-1] = 0
ans = 0

#print(G[magicX-1][magicY-1])

bfs(magicX-1, magicY-1)

if(G[goalY-1][goalX-1]=="."):
    print(-1)
else:
    print(G[goalY-1][goalX-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

input = sys.stdin.readline

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

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
q3 = []
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q3.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1
    q2 = copy.copy(q3)

print(v[dh-1][dw-1])

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


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


def generate_v2_X(v):
    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
        yield x*w+y


# ここN**2だけど大丈夫？
for i in range(n-1):
    for j in range(i+1, n):
        # i→jは可能？
        skip = 0
        for v in islands[i]:
            if skip:
                break
            for v2 in generate_v2_X(v):
                if v2 in islands[j]:
                    edges[i].append(j)
                    edges[j].append(i)
                    skip = 1
                    break


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:
from heapq import heappop,heappush
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for i in range(H)]
     
def dijkstra(x,y):
    weight = {(x,y):0}
    checklist = []
    heappush(checklist,[0,x,y])
    while(checklist):
        weight_node,node_x,node_y = heappop(checklist)
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        for next_x,next_y in ((node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)):
                if 0<=next_x < H and 0 <= next_y < W and s[next_x][next_y] == '.':
                    if (next_x,next_y) not in weight or weight_node < weight[(next_x,next_y)]:
                        weight[(next_x,next_y)] = weight_node
                        heappush(checklist,[weight_node,next_x,next_y])
        for next_x in range(node_x-2,node_x+3):
                for next_y in range(node_y-2,node_y+3):
                    if [next_x,next_y] in ((node_x,node_y),(node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)):
                        pass 
                    elif 0<= next_x < H and 0 <= next_y < W and s[next_x][next_y] == '.':
                        weight_next_node = weight_node + 1
                        if (next_x,next_y) not in weight or weight_next_node < weight[(next_x,next_y)]:
                            weight[(next_x,next_y)] = weight_next_node
                            heappush(checklist,[weight_next_node,next_x,next_y])
    return -1

print(dijkstra(ch-1,cw-1))

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
HW = [list(input()) for _ in range(H)]


def check(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] == ".":
        return True
    else:
        return False


HW[ch - 1][cw - 1] = "#"
dist = [[float("inf")] * W for _ in range(H)]
# print("dist")
# pl(dist)
dist[ch - 1][cw - 1] = 0


deq = deque()
deq.append([(ch - 1, cw - 1)])  # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
warpy = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
warpx = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
step = 0
found = False
cnt = 0
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    # pl(HW)
    # pl(dist)
    for val in cqueue:
        y, x = val
        # if val == (gy - 1, gx - 1):
        #     found = True
        #     break
        for dy, dx in zip(ddy, ddx):
            chky = set()
            chkx = set()
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if dy != 0:
                    chky.add(dy)
                    chky.add(dy * 2)
                if dx != 0:
                    chkx.add(dx)
                    chkx.add(dx * 2)
                HW[ny][nx] = "#"
                if dist[y][x] < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x]
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x])
                nqueue.append((ny, nx))
        for dy, dx in zip(warpy, warpx):
            if (dy in chky) or (dx in chkx):
                continue
            # cnt += 1
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if dist[y][x] + 1 < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x] + 1
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1)
                nqueue.append((ny, nx))
    # if found:
    #     break
    deq.append(nqueue)
    # step += 1
# print(cnt)
val = dist[dh - 1][dw - 1]
if val == float("inf"):
    print(-1)
else:
    print(val)
# print(dist[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import numpy as np
from collections import defaultdict
# input = sys.stdin.buffer.readline
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch - 1, cw - 1  # 0-indexed
dh, dw = map(int, input().split())
dh, dw = dh - 1, dw - 1  # 0-indexed
# print(f'{ch=}, {cw=}')
S = []
for _ in range(H):
    S.append(list(input()))
S = np.array(S)
# print(f'{S=}')

G = np.full_like(S, -1, dtype='int')
# print(f'{G=}')

current_G = 0
group_dic = defaultdict(list)
for h in range(H):
    for w in range(W):
        if S[h, w] == '#':
            continue
        if G[h, w] != -1:
            continue
        G[h, w] = current_G
        group_dic[current_G].append((h, w))
        q = deque([(h, w)])
        while q:
            # print(f'{q=}')
            _h, _w = q.popleft()
            # print(f'{_h=}, {_w=}')
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nx = _w + dx
                ny = _h + dy
                # print(f'{nx=}, {ny=}')
                if nx < 0 or ny < 0 or nx >= W or ny >= H:
                    # print(f'fuga {nx=}, {ny=}')
                    continue
                if S[ny, nx] == '#':
                    continue
                if G[ny, nx] != -1:
                    # print(f'hoge')
                    continue
                G[ny, nx] = current_G
                q.append((ny, nx))
                group_dic[current_G].append((ny, nx))
        current_G += 1
#         print(f'')
# print(f'{G=}')
# print(f'{current_G=}')
# print(f'{group_dic=}')

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

# print(f'start group = {G[ch, cw]=}')
start_group = G[ch, cw]

P = [-1] * (current_G)
P[start_group] = 0
# print(f'{P=}')

g = start_group
GG = deque([start_group])
while GG:
    g = GG.popleft()
    for h, w in group_dic[g]:
        for dx, dy in ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2),
                       (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2),
                       (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0),
                       (2, 1), (2, 2)):
            nx = w + dx
            ny = h + dy
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if S[ny, nx] == '#':
                continue
            _g = G[ny, nx]
            if P[_g] != -1:
                continue
            P[_g] = P[g] + 1
            GG.append(_g)

# print(f'{P=}')
# print(f'goal group = {G[dh, dw]=}')
ans = P[G[dh, dw]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


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


def main():
    h, w = map(int, read().split())
    start = tuple(int(i) - 1 for i in input().split())
    goal = tuple(int(i) - 1 for i in input().split())
    s = [input() for _ in range(h)]
    todo = deque([start])
    seen = set()
    while todo:
        y, x = todo.popleft()
        if (y, x) == goal:
            print(0)
            return
        if s[y][x] == "#":
            continue
        if (y, x) in seen:
            continue
        seen.add((y, x))
        for (ny, nx) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]:
            if 0 <= nx < w and 0 <= ny < h:
                todo.append((ny, nx))
    left, right = 0, h * w
    while right - left > 1:
        mid = (left + right) // 2
        todo = deque([(*start, mid)])
        seen = set()
        while todo:
            y, x, k = todo.popleft()
            if (y, x) == goal:
                right = mid
                break
            if s[y][x] == "#":
                continue
            if (y, x, k) in seen:
                continue
            seen.add((y, x, k))
            for ny in range(max(y - 2, 0), min(y + 2 + 1, h)):
                for nx in range(max(x - 2, 0), min(x + 2 + 1, w)):
                    d = abs(x - nx) + abs(y - ny)
                    if d == 0:
                        continue
                    elif d == 1:
                        todo.append((ny, nx, k))
                    elif k > 0:
                        todo.append((ny, nx, k - 1))
        else:
            left = mid
    print(right if right < h * w else -1)


if __name__ == '__main__':
    main()