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:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[g]=-1
d.append(g)

while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if S[h1][w1]=='.':
      visited[g]=-1
      d.append(a1)

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if visited[a1]==-1:
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.append(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if visited[a2]==-1:
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
dh,dw = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = ["" for _ in range(h)]
p = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
q = queue.Queue()
q.put((ch,cw))
p[ch][cw] = 0
l = [(ch,cw)]
la = l.append
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[j][k] = i
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            la((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi in [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]:
      if  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[j+hi][k+wi] = i+1
  if q.empty():
    print(-1)
    exit()
  l = nl
  la = l.append
  i += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 10**9 + 7


def main():
	# ans_ = []
	# ans_.append(ans)
	# print(("\n").join(map(str, ans_)))
	def wrap_nab(i,j):
		for x in range(i-2, i+3):
			for y in range(j-2, j+3):
				if (x, y) != (i,j):
					yield(x, y)
	def dfs(i, j, lis):
		if (i, j) == (dh-1, dw-1):
			return(True)
		vis[(i, j)] = 1
		stk = [(i, j)]
		corners = set()
		while stk:
			i, j = stk.pop()
			for child in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)]:
				x, y = child
				if child in vis and not vis[child]:
					# print(x, y)
					if mat[x][y] == ".":
				 		if (x, y) == (dh-1, dw-1):
				 			# found[0] = True
				 			return(True)
				 		vis[(x, y)] = 1
				 		stk.append((x,y))
					else:
				 		for nab in wrap_nab(i, j):
				 			if (nab in vis) and not vis[nab] and mat[nab[0]][nab[1]] == ".":# and not vis[nab]:
				 				corners.add(nab)
		lis.extend(list(corners))





	vis = defaultdict(int)

	h, w = read(); ch,cw = read(); dh,dw = read()
	mat = []
	for i in range(h):
		for j in range(w):
			vis[(i, j)] = 0
	# print(vis)

	for i in range(h):mat.append(list(input().strip()))

	# found = [False]
	next_ = [(ch-1, cw-1)]
	c = 0
	while next_:
		# print(next_)
		tem = []
		for i in next_:
			if dfs(*i, tem):
				print(c)
				exit()
		next_ = tem
		c += 1
	# if found[0]:print(c)
	print(-1)



	# for i in wrap_nab(5, 4):
	# 	print(i)








if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))
 
s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1
 
Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1
 
for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)
 
count = 0
best = 0
 
while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if V[i][j]==0:
        ALL.append((i,j))

      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))
 
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))
 
      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))
 
      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))
 
    Q = new_Q
 
  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
 
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    #print(ALL)
    Q = list(ALL)
    
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break
      
    ALL = []

Submission status: Time Limit Exceeded

Solution code:
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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 len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

ch -= 1
cw -= 1
dh -= 1
dw -= 1

def main():
    li = [["" for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque()

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0#ここをスタートの座標に変えること
    que.append((ch,cw))#ここもスタートの座標に変えること

    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]

        for i,j in zip(dx,dy):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        # 魔法の力をもってすれば行ける
        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

    if lin[dh][dw] == inf:
        print(-1)
    else:
        print(lin[dh][dw])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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())
T = [list(input()) for _ in range(H)]

for i in range(H):
  for j in range(W):
    if T[i][j] == ".":
      T[i][j] = float('inf')

def dfs(y, x, prey, prex, c):
  T[y][x] = c
  for dy in range(-2, 3):
    for dx in range(-2, 3):
      ny = y + dy
      nx = x + dx
      if 0 <= ny < H and 0 <= nx < W and T[ny][nx] != "#" and T[ny][nx] > c and (prey != ny or prex != nx):
        if abs(dy) + abs(dx) <= 1:
          dfs(ny, nx, y, x, c)
        else:
          dfs(ny, nx, y, x, c+1)

dfs(ch, cw, -1, -1, 0)

if T[dh][dw] == float('inf') or T[dh][dw] == "#":
  print(-1)
else:
  print(T[dh][dw])

Submission status: Time Limit Exceeded

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


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

OK = "."
NG = "#"

from collections import defaultdict

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for h in range(H):
        Sh =  list(input())
        S.append(Sh)

    que = {(Ch-1,Cw-1)}
    jump_que = set()
    goal = (Dh-1, Dw-1)
    searched=set()
    jump =0

    while(True):
        while(len(que)):
            tmp = que.pop()
            if tmp ==goal:
                print(jump)

                return

            searched.add(tmp)
            nxts=get_around(S,H,W,tmp[0],tmp[1])-searched
            # print(f'nxts: {nxts}')
            que=que|nxts
            jump_nxts = get_jump_around(S, H, W, tmp[0], tmp[1]) - searched
            # print(f'jump_nxts: {jump_nxts}')
            jump_que = jump_que | jump_nxts
            # print(f'jump_que: {jump_que}')

        jump=jump+1
        que=jump_que
        if len(que)==0:
            print('-1')
            return


def get_around(S,H,W, h,w):
    hm = h-1
    hp =h+1
    wm = w-1
    wp= w+1
    nxt=set()
    if hm>=0 and S[hm][w]=='.':
        nxt.add((hm,w))

    if hp<H and S[hp][w]=='.':

        nxt.add((hp,w))
    if wm>=0 and S[h][wm]=='.':
        nxt.add((h,wm))

    if wp<W and S[h][wp]=='.':
        nxt.add((h,wp))
    return nxt

def get_jump_around(S,H,W, h,w):
    hm = max(h-2,0)
    hp =min(h+2,H-1)
    wm = max(w-2,0)
    wp= min(w+2,W-1)
    nxt=set()
    # print(hm,hp,wm,wp)
    for h in range(hm,hp+1):
        for w in range(wm, wp + 1):
            if S[h][w]=='.':
                nxt.add((h, w))

    return nxt


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output,out)

    def test_入力例_1(self):
        input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    wlist = []
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if [k, l] not in wlist:
                wlist.append([k, l])
    
    for k, l in wlist:
        if 0 <= k < h and 0 <= l < w:
            if map[k][l] == ".":
                if visit[k][l] != -1:
                    continue
                visit[k][l] = visit[y][x] + 1
                route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

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(1e6+2)]*(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(1e6+2):
    print(-1)
else:
    print(ans)

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())
smat=[]
smat.append([False]*(W+4))
smat.append([False]*(W+4))
for _ in range(H):
  line=[False,False]+[x=="." for x in input()]+[False,False]
  smat.append(line)
smat.append([False]*(W+4))
smat.append([False]*(W+4))
#print(smat)

from collections import defaultdict
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,prev={},{}
  used=set()
  for v in vlist:
    dist[v]=float("inf")
    prev[v]=-1
  dist[s]=0
  used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used.add(min_v)
    for v,w in graph[min_v]:
      if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

vlist=[]
#ここで点の集合をvlistに入れておく
for i in range(2,H+2):
  for j in range(2,W+2):
    if smat[i][j]:
      vlist.append((i,j))

graph=defaultdict(list)
#graph[i]: iから出る道の[重み,行先]の辞書
for i in range(2,H+2):
  for j in range(2,W+2):
    if not smat[i][j]:
      continue
    
    if smat[i-1][j]:
      graph[(i,j)].append([(i-1,j),0])
    else:
      graph[(i,j)].append([(i-2,j),1])
    if smat[i+1][j]:
      graph[(i,j)].append([(i+1,j),0])
    else:
      graph[(i,j)].append([(i+2,j),1])
    if smat[i][j-1]:
      graph[(i,j)].append([(i,j-1),0])
    else:
      graph[(i,j)].append([(i,j-2),1])
    if smat[i][j+1]:
      graph[(i,j)].append([(i,j+1),0])
    else:
      graph[(i,j)].append([(i,j+2),1])
      
    if smat[i-1][j-1]:
      graph[(i,j)].append([(i-1,j-1),1])
    if smat[i-1][j+1]:
      graph[(i,j)].append([(i-1,j+1),1])
    if smat[i+1][j-1]:
      graph[(i,j)].append([(i+1,j-1),1])
    if smat[i+1][j+1]:
      graph[(i,j)].append([(i+1,j+1),1])

    for k in range(-2,3):
      if k==0:
        continue
      if smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2,2):
      if smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if smat[i+k][j+2]:
        graph[(i,j)].append([(i+k,j+2),1])

dist,prev=dijkstra_heap((Ch+1,Cw+1))
#print(dist)
#print(prev)

if dist[(Dh+1,Dw+1)]==float("inf"):
  print(-1)
else:
  print(dist[(Dh+1,Dw+1)])

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for i in range(h):
   s.append(input())
d = [[-1 for i in range(w)] for j in range(h)]
q = queue.Queue()

#通常移動ベクトル
dx = (-1,0,1,0)
dy = (0,-1,0,1)
#ワープベクトル
wx = (-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2)
wy = (-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2)
q.put((ch,cw))
d[ch][cw] = 0

while not q.empty():
  p = q.get()
  for i in range(4): #通常移動
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if 0 <= nx and nx < h and 0<= ny and ny < w and s[nx][ny]=="." and (d[nx][ny]==-1 or d[nx][ny]>d[p[0]][p[1]]):
      q.put((nx,ny))
      d[nx][ny]=d[p[0]][p[1]]
  for i in range(20): #ワープ移動
    nx = p[0] + wx[i]
    ny = p[1] + wy[i]
    if 0 <= nx and nx < h and 0<= ny and ny < w and s[nx][ny]=="." and (d[nx][ny]==-1 or d[nx][ny]>(d[p[0]][p[1]]+1)):
      q.put((nx,ny))
      d[nx][ny]=d[p[0]][p[1]]+1
print(d[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w=[int(x) for x in input().split()]
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

l=[]
for i in range(h):
  s=[x for x in input()]
  l.append(s)


done=[[float('inf') for i in range(w)] for j in range(h)]
move=[[-1,0],[1,0],[0,1],[0,-1]]

def bfs(x,y):
  ans=float('inf')
  que=[[x,y,0]]

  while(que):
    # print(que)
    nx,ny,cnt = que.pop(0)
    done[ny][nx]=cnt

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)
    for dx,dy in move:
      mx,my = nx+dx,ny+dy
      if 0<=mx<w and 0<=my<h:
        if l[my][mx]=="." and (cnt<done[my][mx]):
          done[my][mx]=cnt
          que.append([mx,my,cnt])

        elif l[my][mx]=="#" and (cnt<done[my][mx]):
          for i in range(-2,3):
            for j in range(-2,3):
              if i==0 and j==0:
                continue
              elif 0<=nx+i<w and 0<=ny+j<h and l[ny+j][nx+i]=="." and cnt<done[ny+j][nx+i]:
                done[ny+j][nx+i]=cnt+1
                que.append([nx+i,ny+j,cnt+1])
      
  return ans


ans1=bfs(cw-1,ch-1)

if ans1==float('inf'):
  print(-1)
else:
  print(ans1)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

import heapq
seen = set()
queue = [(0, CH-1, CW-1)]

while queue:
    move, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, new_row, new_col))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [int(i) for i in input().split()]
D = [int(i) for i in input().split()]
maze = [["#"]+[i for i in input()]+["#"] for j in range(H)]
maze = [["#"]*(W+2)] + maze + [["#"]*(W+2)]
dp = [[-1 for i in range(W+2)] for j in range(H+2)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp[C[0]][C[1]] = 0
pos = deque([[C[0], C[1], 0]])

while len(pos) > 0:

    h, w, count = pos.popleft()

    for dh, dw in dir:
        if maze[h+dh][w+dw] == "#":
            continue
        elif dp[h+dh][w+dw] == -1 or count < dp[h+dh][w+dw]:
            dp[h+dh][w+dw] = count
            pos.append([h+dh, w+dw, count])

    for next_h in range(max(0, h-2), min(H, h+2)+1):
        for next_w in range(max(0, w-2), min(W, w+2)+1):
            if maze[next_h][next_w] == "#":
                continue
            elif dp[next_h][next_w] == -1 or count + 1 < dp[next_h][next_w]:
                dp[next_h][next_w] = count + 1
                pos.append([next_h, next_w, count+1])

print(dp[D[0]][D[1]])