Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.append((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

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


V[C[0]][C[1]] = 0
pool = [tuple(C)]

while(pool):
    y, x = pool.pop()
    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        if not y + dy in range(H):
            continue
        if not x + dx in range(W):
            continue
        if S[y+dy][x+dx] == "#":
            continue
        if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
            V[y+dy][x+dx] = V[y][x]
            pool.append((y+dy, x+dx))
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if not y + dy in range(H):
                continue
            if not x + dx in range(W):
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((y+dy, x+dx))

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

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 = [10**18]*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] != "#":
                        if (k == i and abs(l-j)==1) or (l == j and abs(k-i) == 1):
                            graph[i*m + j + 1] += [(k*m+l+1, 1)]
                        else:
                            graph[i*m+j+1] += [(k*m+l+1, 6969)]

    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)] != 10**18:
        print(dj[val(dh-1, dw-1)]//6969)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
Ch, Cw = MAP()
Dh, Dw = MAP()
S = [input() for _ in range(H)]

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

dy = [1, 0, -1, 0, 1, 1, -1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]
dx = [0, -1, 0, 1, 1, -1, -1, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1]

def wizard_cnt(start_y, start_x):
	q = deque([(start_y, start_x)])
	while q:
		y, x = q.pop()
		for i in range(24):
			ny = y + dy[i]
			nx = x + dx[i]
			if i < 4 and 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and cnt[y][x] < cnt[ny][nx]:
				cnt[ny][nx] = cnt[y][x]
				q.append((ny, nx))
			elif 4 <= i and 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and cnt[y][x]+1 < cnt[ny][nx]:
				cnt[ny][nx] = cnt[y][x]+1
				q.append((ny, nx))

wizard_cnt(Ch-1, Cw-1)

if cnt[Dh-1][Dw-1] == INF:
	print(-1)
else:
	print(cnt[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())
ch -= 1
cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))

def is_valid_point(ph, pw):
    if 0 <= ph < h and 0 <= pw < w and s[ph][pw] == '.':
        return True
    else:
        return False

dh = (1, 0, -1, 0)
dw = (0, 1, 0, -1)

inf = 10 ** 18
dist = [[inf] * w for _ in range(h)]
dist[ch][cw] = 0

q = deque([(ch, cw)])
while q:
    ph, pw = q.popleft()
    for k in range(4):
        nh, nw = ph + dh[k], pw + dw[k]
        if is_valid_point(nh, nw):
            if dist[ph][pw] < dist[nh][nw]:
                dist[nh][nw] = dist[ph][pw]
                q.appendleft((nh, nw))
    for nh in range(ph - 2, ph + 3):
        for nw in range(pw - 2, pw + 3):
            if is_valid_point(nh, nw):
                if dist[ph][pw] + 1 < dist[nh][nw]:
                    dist[nh][nw] = dist[ph][pw] + 1
                    q.append((nh, nw))

if dist[Dh][Dw] == inf:
    print(-1)
else:
    print(dist[Dh][Dw])

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 = [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 = [[float('inf')]*(W+4) for _ in range(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()

d.append((sh,sw,0))

while len(d)>0:
  h,w,cnt = d.popleft()
  if visited[h][w]<=cnt:
    continue
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        d.append((h1,w1,cnt))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        d.append((h2,w2,cnt+1))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from heapq import *

INF = 10**9

def dijkstra(s, es):
    dist = [INF] * len(es)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in es[v]:
            tmp = dv+cost
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(h, (tmp, u))
    return dist

def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x)-1, stdin.readline().split())
    Dh, Dw = map(lambda x: int(x)-1, stdin.readline().split())
    S = [stdin.readline()[:-1] for i in range(H)]
    es = [[] for i in range(H*W)]
    for i in range(H):
        for j in range(W):
            for k in range(i-2, i+3):
                for l in range(j-2, j+3):
                    if 0 <= k < H and 0 <= l < W and S[k][l] == '.':
                        if abs(i-k) + abs(j-l) == 1:
                            es[i*W+j].append((k*W+l, 0))
                        else:
                            es[i*W+j].append((k*W+l, 1))
    d = dijkstra(Ch*W+Cw, es)[Dh*W+Dw]
    ans = -1 if d == INF else d
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

grid = []
for _ in range(H):
	grid.append(list(c == "." for c in input().strip()))

m = H * W + 1
smallests = [[m] * W for _ in range(H)]

queue_move = [(0, Cw, Ch)]
queue_warp = []
smallests[Ch][Cw] = 0

def calc():
	while queue_move or queue_warp:
		if queue_move:
			queue = queue_move
		else:
			queue = queue_warp
		d, x, y = heappop(queue)
		if d == smallests[y][x]:
			for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				tx = x + dx
				ty = y + dy
				if tx >= 0 and tx < W and ty >= 0 and ty < H:
					if grid[ty][tx] and d < smallests[ty][tx]:
						smallests[ty][tx] = d
						heappush(queue_move, (d, tx, ty))
						heappush(queue_warp, (d, tx, ty))
			d += 1
			for tx in range(max(0, x - 2), min(W, x + 3)):
				for ty in range(max(0, y - 2), min(H, y + 3)):
					if grid[ty][tx] and d < smallests[ty][tx]:
						smallests[ty][tx] = d
						heappush(queue_move, (d, tx, ty))
						heappush(queue_warp, (d, tx, ty))
	return smallests[Dh][Dw]

result = calc()
if result == m:
	print(-1)
else:
	print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    c = list(map(lambda x: int(x) - 1, input().split()))
    d = list(map(lambda x: int(x) - 1, input().split()))
    grid = [list(input()) for _ in range(h)]
    q = deque([c])
    max_val = 10 ** 10
    dist = [[max_val for _ in range(w)] for _ in range(h)]
    dist[c[0]][c[1]] = 0
    next_d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    set_nd = {(0, 1), (1, 0), (0, -1), (-1, 0)}
    while q:
        now_x, now_y = q.pop()
        for dx, dy in next_d:
            nx = now_x + dx
            ny = now_y + dy
            if not (0 <= nx < h and 0 <= ny < w):
                continue
            elif grid[nx][ny] == "#":
                continue
            if dist[nx][ny] > dist[now_x][now_y]:
                dist[nx][ny] = dist[now_x][now_y]
                if [nx, ny] == d:
                    continue
                q.appendleft([nx, ny])
        for dx, dy in [[0, 1], [0, 2], [1, 0], [1, 2], [1, 1], [2, 2], [2, 0], [2, 1]]:
            for cx, cy in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
                nx = now_x + dx * cx
                ny = now_y + dy * cy
                if not (0 <= nx < h and 0 <= ny < w) or (nx, ny) in set_nd:
                    continue
                elif grid[nx][ny] == "#":
                    continue
                if dist[nx][ny] > dist[now_x][now_y] + 1:
                    dist[nx][ny] = dist[now_x][now_y] + 1
                    if [nx, ny] == d:
                        continue
                    q.append([nx, ny])
    print(dist[d[0]][d[1]] if dist[d[0]][d[1]] != max_val else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

sy-=1
sx-=1
gy-=1
gx-=1

C = [list(input()) for i in range(H)]

from collections import deque
task_list = deque([])

def bfs(y,x,count):#関数にしない方がわかりやすいかも

    if x<0 or y<0 or x>=W or y>=H:
        return#何もしない

    if C[y][x]=="#":
        return#何もしない
    elif C[y][x]==".":
        C[y][x]=str(count)#既に訪れたことを把握する必要あり
        task_list.append([y+1,x,count])
        task_list.append([y-1,x,count])
        task_list.append([y,x-1,count])
        task_list.append([y,x+1,count])
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                task_list.append([y+j,x+i,count+1])
    elif int(C[y][x]) > count:
        C[y][x]=str(count)#既に訪れたことを把握する必要あり
        task_list.append([y+1,x,count])
        task_list.append([y-1,x,count])
        task_list.append([y,x-1,count])
        task_list.append([y,x+1,count])
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                task_list.append([y+j,x+i,count+1])
    
y=sy
x=sx
count=0
C[y][x]=str(count)#既に訪れたことを把握する必要あり
task_list.append([y+1,x,count])
task_list.append([y-1,x,count])
task_list.append([y,x-1,count])
task_list.append([y,x+1,count])
for i in range(-2,3,1):
    for j in range(-2,3,1):
        task_list.append([y+j,x+i,count+1])

while(len(task_list)):
    y,x,t = task_list.popleft()
    bfs(y,x,t)

if C[gy][gx]==".":
    print(-1)
else:
    print(C[gy][gx])

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()
    flg = False
    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] == "#":
            flg = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg:
        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:
from collections import deque
import sys
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 = [input() for _ in range(H)]
d = [[0]*W for _ in range(H)]

que = deque([[cw, ch]])
count = 0
while que:
    while que:
        x, y = que.popleft()
        if x == dw and y == dh:
            print(count)
            sys.exit()
                
        d[y][x] = -1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nnx, nny = x+i, y+j
                if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                    d[nny][nnx] = 1
        
        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 d[ny][nx]!=-1:
                if nx == dw and ny == dh:
                    print(count)
                    sys.exit()
                
                d[ny][nx] = -1
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        nnx, nny = nx+i, ny+j
                        if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                            d[nny][nnx] = 1
                que.append([nx, ny])
                
    for i in range(W):
        for j in range(H):
            if d[j][i] == 1:
                d[j][i] == -1
                que.append([i, j])
    count += 1
print(-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)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, ch-1, cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, y, x = heappop(Q)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            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 (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    heappush(Q, (d, ny, nx))
            else:
                if dist[ny][nx]>d+1:
                    heappush(Q, (d+1, ny, nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)

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(start, end):
	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
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			if dist[nn] > nd:
				dist[nn] = nd
				heapq.heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '#': return edges
	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.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.append(((ni, nj), 1))
	return edges

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

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

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] != "#":
                        if (k == i and abs(l-j)==1) or (l == j and abs(k-i) == 1):
                            graph[i*m + j + 1] += [(k*m+l+1, 1)]
                        else:
                            graph[i*m+j+1] += [(k*m+l+1, 6969)]

    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)]//6969)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W=LI()
  Ch,Cw=LI()
  Dh,Dw=LI()
  Ch-=1
  Cw-=1
  Dh-=1
  Dw-=1
  field=[S() for _ in range(H)]

  q=collections.deque()
  q.append((Ch,Cw,0))
  ans=[[inf]*W for _ in range(H)]
  while q:
    # for x in ans:
    #   print(x)
    # print()
    y,x,cnt=q.popleft()
    if ans[y][x]<=cnt:
      continue
    ans[y][x]=cnt
    if y==Dh and x==Dw:
      continue

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<H and 0<=nx<W:
        if field[ny][nx]=='.':
          q.append((ny,nx,cnt))
        else:
          if dy==1 and dx==0:
            for i in range(0,2):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==1:
            for i in range(-2,3):
              for j in range(0,2):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    q.append((nny,nnx,cnt+1))
          elif dy==-1 and dx==0:
            for i in range(-1,1):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==-1:
            for i in range(-2,3):
              for j in range(-1,1):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    q.append((nny,nnx,cnt+1))

  x=ans[Dh][Dw]
  if x==inf:
    return -1
  return x

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Ch -= 1
Cw -= 1
Dh,Dw = map(int,input().split())
Dh -= 1
Dw -= 1
maze = [list(input()) for _ in range(H)]

que = deque([(Ch,Cw,0)])
adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
while que:
    h,w,worp = que.popleft()
    if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
        continue
    else:
        maze[h][w] = worp
        for a,b in adjecents:
            nxh,nxw = h+a,w+b
            if 0<=nxh < H and 0<=nxw < W:
                que.append((nxh,nxw,worp))
        
        for i in range(-2,3,1):
            for j in range(-2,3,1):
                nxh,nxw = h+i,w+j
                if 0<=nxh < H and 0<=nxw < W:
                    que.append((nxh,nxw,worp+1))
if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
    print(-1)
else:
    print(maze[Dh][Dw])

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())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
    for dy,dx 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)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
            elif d[(ny,nx)]>d[(y,x)]+1:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-1)