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, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = [False]*4 # L, R, D, U
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag[i] = True
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] > dists[y][x]+1):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        elif(N_Flag > 0):
            # L, R, D, U
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag[3] == True):
                dy_min = 1
            elif(Flag[2] == True):
                dy_max = 0
            elif(Flag[1] == True):
                dx_min = 1
            else:
                dx_max = 0
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] > dists[y][x]+1):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
MV = [(-1, 0), (0, -1), (1, 0), (0, 1)]
WP = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
WL = set()
WL_next = set()
# WL = []
# WL_next = []
S = []


def dfs(x, y, num):
    S[y][x] = num
    # S[y] = S[y][:x] + str(num) + S[y][x + 1:]
    for mv in MV:
        px, py = mv
        nx, ny = x + px, y + py
        for wp in WP:
            wx, wy = wp
            nwx, nwy = x + wx, y + wy
            if 0 <= nwx and 0 <= nwy and nwx < W and nwy < H:
                if S[nwy][nwx] == ".":
                    # S[nwy][nwx] = num + 1
                    # print(nwx + 1, nwy + 1)
                    # print(S[nwy][:nwx], str(num + 1), S[nwy][nwx + 1:])
                    # S[nwy] = S[nwy][:nwx] + str(num + 1) + S[nwy][nwx + 1:]
                    # WL_next.append((nwx, nwy))
                    WL_next.add((nwx, nwy))
        if 0 <= nx and 0 <= ny and nx < W and ny < H:
            if S[ny][nx] == ".":
                # print(nx + 1, ny + 1)
                dfs(nx, ny, num)


for i in range(H):
    # for j in range(W):
    S.append(list(input()))

WL.add((Cw - 1, Ch - 1))
WL_next.add((Cw - 1, Ch - 1))
# WL.append((Cw - 1, Ch - 1))
# WL_next.append((Cw - 1, Ch - 1))
S[Ch - 1][Cw - 1] = 0
cnt = 0
while WL_next and S[Dh - 1][Dw - 1] == ".":
    # WL_next = []
    WL_next = set()
    # while WL:
    for wx, wy in WL:
        # wx, wy = WL.pop()
        # print(wx, wy)
        if type(S[wy][wx]) is int and cnt != 0:
            continue
        dfs(wx, wy, cnt)
        # print(S)
    WL = set(WL_next)
    cnt += 1
if S[Dh - 1][Dw - 1] == ".":
    print(-1)
else:
    print(S[Dh - 1][Dw - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit

h,w=map(int,input().split())
sh,sw=map(lambda s: int(s)-1,input().split())
gh,gw=map(lambda s: int(s)-1,input().split())
s = [input() for _ in range(h)]
d = [[h*w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh))
while len(q):
  p = q.popleft()
  if p[0] == gw and p[1] == gh:
    print(d[gh][gw])
    exit(0)
  for dx in range(-2, 3):
    for dy in range(-2, 3):
      nx, ny = p[0] + dx, p[1] + dy
      c = 0 if abs(dx) + abs(dy) == 1 else 1
      if dx == dy == 0 or nx < 0 or ny < 0 or w <= nx or h <= ny or s[ny][nx] == '#' or d[ny][nx] <= d[p[1]][p[0]] + c:
        continue
      d[ny][nx] = d[p[1]][p[0]] + c
      np = (nx, ny)
      if c:
        q.append(np)
      else:
        q.appendleft(np)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = deque([(cx, cy)])

    c[cx][cy] = 0

    while q:
        x, y = q.pop()
        cp = c[x][y]
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i, j in d:
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                q.append((nx, ny))
                c[nx][ny] = cp
        cp += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                        ny] > cp:
                    c[nx][ny] = cp
                    q.appendleft((nx, ny))

    return -1 * (c[dx][dy] == 10**6) or c[dx][dy]


print(bfs())

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
import sys
from heapq import *
input = sys.stdin.readline

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heappush(self.q, (self.dist[dest], dest))
        return self.dist

def sep(): return map(int,input().split())
def solve():
    n,m = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    grid = []
    for i in range(n):
        temp = input().rstrip()
        grid.append(temp)

    g = [[] for i in range(n*m)]

    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '#'):
                continue
            for ii in range(i-2,i+3):
                for jj in range(j-2,j+3):
                    if(ii==i and jj==j):
                        continue
                    if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
                        if(abs(ii-i)+abs(jj-j) == 1):
                            g[i*m+j].append([ii*m+jj,0])
                        else:
                            g[i*m+j].append([ii*m+jj,1])
                        # print(i*m+j,ii*m+jj)
    # for i in range(n*m):
    #     print(g[i])

    # dist = [10**9]*(n*m)
    # print(x*m+y,xnot*m+ynot)
    d = Dijkstra(g)
    dist = d.calc(x*m+y)
    # print(dist[xnot*m+ynot])
    # print(dist)
    if(dist[xnot*m+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*m+ynot])

solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int,input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch, cw)])
S = [[float("inf")]*w for _ in range(h)]
S[ch][cw] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = ((1,0),(0,1),(-1,0),(0,-1))
    ans = S[y][x]

    if (y, x) == (dh, dw):
            S[y][x] = ans
            break

    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h and S[y+j][x+i] > ans and G[y+j][x+i] == ".":
            queue.appendleft((y+j, x+i))
            S[y+j][x+i] = ans
            

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= x+i < w and 0 <= y+j < h and S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.append((y+j, x+i))


if S[dh][dw] == float("inf"):
    print(-1)
else:
    print(S[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = False
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag = True
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(Flag==True):
            for dy in range( max(-y, -2), min(H-y, 3) ):
                for dx in range( max(-x, -2), min(W-x, 3) ):
                    next = [x+ dx, y+ dy]
                    if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
        


    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    heapq.heappush(deque, [0, start[1], start[0]])
    dists[start[0]][start[1]] = 0
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = [ [False]*3 for _ in range(3) ]
        N_Flag = 0
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="#"):
                Flag[dy+1][dx+1] = True
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            #print([x, y], next)
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>0):
            if(N_Flag > 1):
                for dy in range( max(-y, -2), min(H-y, 3) ):
                    for dx in range( max(-x, -2), min(W-x, 3) ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])
            else:
                dy_max = min(H-y, 3)
                dy_min = max(-y, -2)
                dx_min = max(-x, -2)
                dx_max = min(W-x, 3)
                if(Flag[2][1] == True):
                    dy_min = 1
                elif(Flag[0][1] == True):
                    dy_max = 0
                elif(Flag[1][2] == True):
                    dx_min = 1
                else:
                    dx_max = 0
                for dy in range( dy_min, dy_max ):
                    for dx in range( dx_min, dx_max ):
                        next = [x+ dx, y+ dy]
                        if(dists[next[1] ][next[0] ] > dists[y][x]+1 and Maps[y+dy][x+dx] == "."):
                            dists[next[1] ][next[0] ] = dists[y][x]+1
                            heapq.heappush(deque, [dists[next[1] ][next[0] ], next[0], next[1] ])




    #print(dists)
    if( dists[goal[0]][goal[1]]==inf ):
        print(-1)
    else:
        print(dists[goal[0]][goal[1]])

Submission status: Time Limit Exceeded

Solution code:
"""
    Satwik_Tiwari ;) .
    21st AUGUST , 2020  - FRIDAY
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
# def djkistra(g,st,dist): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly
#     pq = []
#     dist[st] = 0
#     # pq.append([0,st]
#     heappush(pq,[0,st])
#     while(len(pq) != 0):
#         curr = heappop(pq)[1]
#         for i in range(0,len(g[curr])):
#             b = g[curr][i][0]
#             w = g[curr][i][1]
#             if(dist[b] > dist[curr] + w):
#                 dist[b] = dist[curr]+w
#                 # pq.append([dist[b],b])
#                 heappush(pq,[dist[b],b])


INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heappush(self.q, (self.dist[dest], dest))
        return self.dist


def solve():
    n,m = sep()
    x,y = sep()
    xnot ,ynot = sep()
    x-=1
    y-=1
    xnot-=1
    ynot-=1

    grid = []
    for i in range(n):
        temp = list(inp())
        grid.append(temp)

    g = [[] for i in range(n*m)]

    for i in range(n):
        for j in range(m):
            if(grid[i][j] == '#'):
                continue
            for ii in range(i-2,i+3):
                for jj in range(j-2,j+3):
                    if(ii==i and jj==j):
                        continue
                    if(0<=ii<n and 0<=jj<m and grid[ii][jj] == '.'):
                        if(abs(ii-i)+abs(jj-j) == 1):
                            g[i*m+j].append([ii*m+jj,0])
                        else:
                            g[i*m+j].append([ii*m+jj,1])
                        # print(i*m+j,ii*m+jj)
    # for i in range(n*m):
    #     print(g[i])

    # dist = [10**9]*(n*m)
    # print(x*m+y,xnot*m+ynot)
    d = Dijkstra(g)
    dist = d.calc(x*m+y)
    # print(dist[xnot*m+ynot])
    # print(dist)
    if(dist[xnot*m+ynot] == 10**9):
        print(-1)
    else:
        print(dist[xnot*m+ynot])









testcase(1)
# testcase(int(inp()))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited = {}
visited[(cx, cy)] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    if (x, y) in visited and visited[(x, y)] < c:
        continue
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                continue
            visited[(nx, ny)] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                    continue
                visited[(nx, ny)] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))
# print(visited)
if (gx, gy) in visited:
    print(visited[(gx, gy)])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(70000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()