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, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
#from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import heapq
def dijkstra(edges, start, end):
	#dist = [float('inf')]*N
	dist = defaultdict(lambda: float('inf'))
	dist[start] = 0
	heap = []
	heapq.heappush(heap, (0, start))
	while heap:
		d, n = heapq.heappop(heap)
		if n == end:
			return d
		if dist[n] != d:
			continue
		for nn, ed in edges[n]:
			nd = d + ed
			if dist[nn] > nd:
				dist[nn] = nd
				heapq.heappush(heap, (nd, nn))
	return -1

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

edges = defaultdict(list)
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': continue
		n = (i,j)
		edges[n] = []
		for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			edges[n].append(((ni, nj), 0))
		for di in range(-2, +3):
			for dj in range(-2, +3):
				ni, nj = i+di, j+dj
				if di == 0 and dj == 0: continue
				if (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					continue
				if not(0 <= ni < H and 0 <= nj < W): continue
				if M[ni][nj] == '#': continue
				edges[n].append(((ni, nj), 1))

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])
d = dijkstra(edges, start, end)
print(d)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]
inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)

    for dy, dx in magic:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            continue
        check[n_h][n_w] = dd + 1
        queue.append([n_h, n_w])
        queue.append(dd + 1)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

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

#print(b)

from collections import deque

def nbd(nh,nw,cost,dv):
    if 0 <= nh < h and 0 <= nw < w and b[nh][nw]==".":
        dv += cost
        if dv < res[nh][nw]:
            res[nh][nw] = dv
            if cost: q.append((dv,nh,nw))
            else: q.appendleft((dv,nh,nw))
    return 


INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    nbd(vh-1,vw,0,dv)
    nbd(vh,vw-1,0,dv)
    nbd(vh+1,vw,0,dv)
    nbd(vh,vw+1,0,dv)
    
    nbd(vh-1,vw-1,1,dv)
    nbd(vh-1,vw+1,1,dv)
    nbd(vh+1,vw-1,1,dv)
    nbd(vh+1,vw+1,1,dv)

    for i in range(-2,3):
        nbd(vh-2,vw+i,1,dv)
        nbd(vh+2,vw+i,1,dv)

    for i in range(-1,2):
        nbd(vh+i,vw-2,1,dv)
        nbd(vh+i,vw+2,1,dv)
    
    #print(res)
        
ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    sy, sx = (int(x) - 1 for x in input().split())
    gy, gx = (int(x) - 1 for x in input().split())
    G = [input().rstrip() for _ in range(H)]

    dq = deque()
    dq.append((sy, sx, 0))

    INF = H * W + 10

    ctr = [[INF] * W for _ in range(H)]
    ctr[sy][sx] = 0

    while dq:
        y, x, cnt = dq.popleft()
        if cnt > ctr[y][x]:
            continue

        if y == gy and x == gx:
            print(cnt)
            return

        if y > 0 and G[y - 1][x] == '.' and ctr[y - 1][x] > cnt:
            dq.appendleft((y - 1, x, cnt))
            ctr[y - 1][x] = cnt

        if x > 0 and G[y][x - 1] == '.' and ctr[y][x - 1] > cnt:
            dq.appendleft((y, x - 1, cnt))
            ctr[y][x - 1] = cnt

        if y < H - 1 and G[y + 1][x] == '.' and ctr[y + 1][x] > cnt:
            dq.appendleft((y + 1, x, cnt))
            ctr[y + 1][x] = cnt

        if x < W - 1 and G[y][x + 1] == '.' and ctr[y][x + 1] > cnt:
            dq.appendleft((y, x + 1, cnt))
            ctr[y][x + 1] = cnt

        ncnt = cnt + 1
        for dr in range(-2, 3):
            ny = y + dr
            if ny < 0 or ny >= H:
                continue
            for dc in range(-2, 3):
                nx = x + dc
                if nx < 0 or nx >= W:
                    continue
                if G[ny][nx] == '.' and ctr[ny][nx] > ncnt:
                    dq.append((ny, nx, ncnt))
                    ctr[ny][nx] = ncnt

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=1000000000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
def bfs(i,j):
    global h,w,s,dp
    if i>0:
        if dp[i-1][j]>dp[i][j]:
            dp[i-1][j]=dp[i][j]
            bfs(i-1,j)
    if j>0:
        if dp[i][j-1]>dp[i][j]:
            dp[i][j-1]=dp[i][j]
            bfs(i,j-1)
    if i<h-1:
        if dp[i+1][j]>dp[i][j]:
            dp[i+1][j]=dp[i][j]
            bfs(i+1,j)
    if j<w-1:
        if dp[i][j+1]>dp[i][j]:
            dp[i][j+1]=dp[i][j]
            bfs(i,j+1)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w:
                if dp[i+k][j+l]>dp[i][j]+1:
                    dp[i+k][j+l]=dp[i][j]+1
                    bfs(i+k,j+l)

bfs(c[0],c[1])
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from queue import PriorityQueue

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

Cx = Cw - 1
Cy = Ch - 1
Dx = Dw - 1
Dy = Dh - 1
queue = PriorityQueue()
queue.put((0, (Cx, Cy)))
ans = -1
done = defaultdict(int)
while not queue.empty():
    cost, (x, y) = queue.get()
    done[x, y] = min(done[x, y], cost)
    if (x, y) == (Dx, Dy):
        ans = cost
        break
    for dx, dy in ((-1, 0), (0, -1), (1, 0), (0, 1)):
        nx, ny = x + dx, y + dy
        if (
            0 <= nx < W and 0 <= ny < H
            and S[ny][nx] == '.'
            and (nx, ny) not in done
        ):
            queue.put((cost, (nx, ny)))
    for dx, dy in (
        (-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
        (-2, -1), (-1, -1), (1, -1), (2, -1),
        (-2, 0), (2, 0),
        (-2, 1), (-1, 1), (1, 1), (2, 1),
        (-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2),
    ):
        nx, ny = x + dx, y + dy
        if (
            0 <= nx < W and 0 <= ny < H
            and S[ny][nx] == '.'
            and (nx, ny) not in done
        ):
            queue.put((cost + 1, (nx, ny)))
print(ans)

Submission status: Time Limit Exceeded

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

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

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




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

H,W=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=[[1<<30]*W for i in range(H)]

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

ANS[sh][sw]=0

Q=deque([(sh,sw,0)])

while Q:
    x,y,sc=Q.popleft()
    if ANS[x][y]<sc:
        continue

    for i,j 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),(x-1,y+1),(x-1,y+2),(x,y-2),(x,y-1),(x,y+1),(x,y+2),(x+1,y-2),(x+1,y-1),(x+1,y),(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 0<=i<H and 0<=j<W:
            if MAP[i][j]=="." and abs(i-x)+abs(j-y)==1 and ANS[i][j]>ANS[x][y]:
                ANS[i][j]=ANS[x][y]
                Q.append((i,j,ANS[i][j]))
            elif MAP[i][j]=="." and abs(i-x)+abs(j-y)>1 and ANS[i][j]>ANS[x][y]+1:
                ANS[i][j]=ANS[x][y]+1
                Q.append((i,j,ANS[i][j]))

if ANS[gh][gw]==1<<30:
    print(-1)
else:
    print(ANS[gh][gw])

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=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from heapq import heappop,heappush
todo=[[0,Ch,Cw]]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[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 todo:
  cnt,nh,nw=heappop(todo)
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        heappush(todo,[cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        heappush(todo,[cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                M[h][w] = -2
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1:
                        if (dh, dw) in move:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

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=[[x=="." for x in input()] for _ in range(H)]
#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(H):
  for j in range(W):
    if smat[i][j]:
      vlist.append((i,j))

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

    for k in range(-2,3):
      if i-2>=0 and 0<=j+k<W and smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if i+2<H and 0<=j+k<W and smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2):
      if 0<=i+k<H and j-2>=0 and smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if 0<=i+k<H and j+2<W and 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 sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
def check(i,j):
  return 0 <= i < h and 0 <= j < w 
def on_block(i,j):
  return S[i][j] == "#"
h,w = map(int,input().split())
ci,cj = map(int,input().split())
ci-=1;cj-=1
gi,gj = map(int,input().split())
gi-=1;gj-=1
S = [list(input()) for i in range(h)]
grid = [[inf] * w for i in range(h)]
grid[ci][cj] = 0
que = []
que.append((0,ci,cj))
while que:
  now,si,sj = heapq.heappop(que)
  if now > grid[si][sj]:continue
  for di,dj in dydx4:
    ni = si + di
    nj = sj + dj
    if not check(ni,nj):continue
    if on_block(ni,nj): continue
    else:
      if now < grid[ni][nj] :
        grid[ni][nj] = now
        heapq.heappush(que,(now,ni,nj))
  for i in range(si-2,si+3):
    for j in range(sj-2,sj+3):
      if not check(i,j):continue
      if on_block(i,j):continue
      else:
        if now + 1 < grid[i][j] :
          grid[i][j] = now + 1
          heapq.heappush(que,(now+1,i,j))
print(grid[gi][gj] if grid[gi][gj] != inf else -1)
# print(*grid,sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

INF = 10**7
dist = [[INF]*w for _ in range(h)]
dist[sh][sw] = 0
q = [(0,sh,sw)]

while q:
    
    d,vsh,vsw = heapq.heappop(q)
    
    for dh in range(-2,3):
        for dw in range(-2,3):
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if dh == 0 and dw==0: continue
            if s[newh][neww] == "#": continue
                
            if abs(dh)+abs(dw)==1:
                if dist[newh][neww] > d:
                    dist[newh][neww] = d
                    heapq.heappush(q,(d,newh,neww))
            else:
                if dist[newh][neww] > d+1:
                    dist[newh][neww] = d+1
                    heapq.heappush(q,(d+1,newh,neww))
                    
if dist[gh][gw] == INF: print(-1)
else: print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
from math import ceil

from heapq import heappop, heappush

def dijkstra(graph, alpha):
    n = len(graph)
    distance = [float("inf")]*n
    distance[alpha] = 0
    queue = [(0, alpha)]
    while queue:
        length, v = heappop(queue)
        for x, dist in graph[v]:
            if dist + length < distance[x]:
                distance[x] = dist + length
                heappush(queue, (dist+length, x))
    return distance

for _ in range(int(input()) if not True else 1):
    n, m = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    a = []
    for i in range(n):
        a += [[k for k in input()]]

    def val(i, j):
        return i*m + j + 1

    graph = [[] for i in range(n*m + 1)]
    for i in range(n):
        for j in range(m):
            if a[i][j] == "#":continue
            for k in range(max(0, i-2), min(i+3, n)):
                for l in range(max(0, j-2), min(j+3, m)):
                    if a[k][l] != "#":
                        graph[val(i,j)] += [(val(k, l), 1) if (k,l) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] else (val(k, l), 696969)]

    pos = val(ch-1, cw-1)
    #print(pos, graph[pos])
    #print(graph[13])
    dj = dijkstra(graph, pos)
    #print(dj)
    if dj[val(dh-1, dw-1)] != float("inf"):
        print(dj[val(dh-1, dw-1)]//696969)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=1000000000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
def bfs(i,j):
    global h,w,s,dp
    if i>0:
        if dp[i-1][j]>dp[i][j]:
            dp[i-1][j]=dp[i][j]
            bfs(i-1,j)
    if j>0:
        if dp[i][j-1]>dp[i][j]:
            dp[i][j-1]=dp[i][j]
            bfs(i,j-1)
    if i<h-1:
        if dp[i+1][j]>dp[i][j]:
            dp[i+1][j]=dp[i][j]
            bfs(i+1,j)
    if j<w-1:
        if dp[i][j+1]>dp[i][j]:
            dp[i][j+1]=dp[i][j]
            bfs(i,j+1)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w:
                if dp[i+k][j+l]>dp[i][j]+1:
                    dp[i+k][j+l]=dp[i][j]+1
                    bfs(i+k,j+l)

bfs(c[0],c[1])
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

que = []
que.append((ch,cw,0))

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

for x,y,c in que:
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.append((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

H,W=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=[[1<<30]*W for i in range(H)]

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

ANS[sh][sw]=0

Q=deque([(sh,sw)])

while Q:
    x,y=Q.popleft()

    for i,j 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),(x-1,y+1),(x-1,y+2),(x,y-2),(x,y-1),(x,y+1),(x,y+2),(x+1,y-2),(x+1,y-1),(x+1,y),(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 0<=i<H and 0<=j<W:
            if MAP[i][j]=="." and abs(i-x)+abs(j-y)==1 and ANS[i][j]>ANS[x][y]:
                ANS[i][j]=ANS[x][y]
                Q.append((i,j))
            elif MAP[i][j]=="." and abs(i-x)+abs(j-y)>1 and ANS[i][j]>ANS[x][y]+1:
                ANS[i][j]=ANS[x][y]+1
                Q.append((i,j))

if ANS[gh][gw]==1<<30:
    print(-1)
else:
    print(ANS[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
graph = [[] for _ in range(H*W)]

for sh in range(H):
    for sw in range(W):
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                    graph[sh*W+sw].append((0,(sh+dx)*W+sw+dy))
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                        graph[sh*W+sw].append((1,(sh+dx)*W+sw+dy))

dist = dijkstra(graph, H*W, Ch*W+Cw)
ans = dist[Dh*W+Dw]
if ans == inf:
    ans = -1
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())
S = [list(input()) for i in range(H)]

from collections import deque

q = deque([(CH-1, CW-1)])

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

M = []
for i in range(H):
    M.append([float('inf')] * W)
M[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] == ".":
            if M[h+dh][w+dw] > M[h][w]:
                M[h+dh][w+dw] = M[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] == ".":
            if M[h+wh][w+ww] > M[h][w] + 1:
                M[h+wh][w+ww] = M[h][w] + 1
                q.append((h+wh, w+ww))

if M[DH-1][DW-1] == float('inf'):
    print(-1)
else:
    print(M[DH-1][DW-1])