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:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque 
inf = 10**9+1
def do():
    dyx = [(-1,0),(1,0),(0,1),(0,-1)]
    dd1 = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2)]
    dd2 = [(2,-2),(2,-1),(2,0),(2,1),(2,2),(1,-2),(1,-1),(1,1),(1,2)]
    dd3 = [(-2,2),(-1,2),(0,2),(1,2),(2,2),(-2,1),(-1,1),(1,1),(2,1)]
    dd4 = [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1)]
    h,w=INTM()
    sh,sw=INTM()
    sh-=1
    sw-=1
    gh,gw=INTM()
    gh-=1
    gw-=1
    dist=[[inf]*w for i in range(h)]
    dist[sh][sw]=0
    s=[]
    for i in range(h):
        s.append(STR())
    
    que=deque()
    que.append(sh*w+sw)
    while que:
        q=que.popleft()
        th=q//w
        tw=q%w
        for dy,dx in dyx:
            if (0 <= th+dy <h) and (0 <= tw+dx <w):
                if s[th+dy][tw+dx]=="#":
                    if (dy,dx)==(-1,0):
                        ddt=dd1
                    if (dy,dx)==(1,0):
                        ddt=dd2
                    if (dy,dx)==(0,1):
                        ddt=dd3
                    if (dy,dx)==(0,-1):
                        ddt=dd4
#                    for ddy in range(-2,3,1):
 #                       for ddx in range(-2,3,1):
                    for ddy,ddx in ddt:        
                         if (ddy,ddx) in dyx or ((ddy,ddx) == (0,0)):
                                continue
                         if (0 <= th+ddy <h) and (0 <= tw+ddx <w):
                            if  s[th+ddy][tw+ddx]==".":
                                if dist[th+ddy][tw+ddx] >dist[th][tw]+1:
                                    que.append((th+ddy)*w+(tw+ddx))
                                    dist[th+ddy][tw+ddx] =dist[th][tw]+1
                                    
                else:
                    if dist[th+dy][tw+dx] >dist[th][tw]:
                        que.append((th+dy)*w+(tw+dx))
                        dist[th+dy][tw+dx] =dist[th][tw]
        
    if dist[gh][gw]==inf:
        print(-1)
    else:
        print(dist[gh][gw])
        
    # print(dist)
                                
                                
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



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

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    #print(road_types)
    for i in range(H):
        for j in range(W):
            if(Maps[i][j] == "#" and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Maps, flag_searched, parents, j, i, Edges, road_types)
            """
            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types)

                for dy in range(-2, 3, 1):
                    for dx in range(-2, 3, 1):
                        if(-1< i+dy and i+dy < H and -1< j+dx and j+dx < W and flag_searched[i+dy][j+dx]==False):
                            flag_searched[i+dy][j+dx] = True

                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)
            """
    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()[:-1]

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=['X'*(W+4) for _ in range(2)]+['XX'+input()+'XX' for _ in range(H)]+['X'*(W+4) for _ in range(2)]
T=[[-2]*(W+4) for _ in range(H+4)]

from collections import deque
q0=deque()
q0.append([Ch, Cw])
T[Ch][Cw]=0
q1=deque()

while T[Dh][Dw]==-2 and len(q0)>0:  
  while q0:
    a, b=q0.popleft()
    q1.append([a, b])
    if T[a-1][b]==-2 and S[a-1][b]=='.':
      q0.append([a-1, b])
      T[a-1][b]=T[a][b]+0
    if T[a+1][b]==-2 and S[a+1][b]=='.':
      q0.append([a+1, b])
      T[a+1][b]=T[a][b]+0
    if T[a][b-1]==-2 and S[a][b-1]=='.':
      q0.append([a, b-1])
      T[a][b-1]=T[a][b]+0
    if T[a][b+1]==-2 and S[a][b+1]=='.':
      q0.append([a, b+1])
      T[a][b+1]=T[a][b]+0
  while q1:
    a, b=q1.popleft()
    if T[a-2][b-2]==-2 and S[a-2][b-2]=='.':
      q0.append([a-2, b-2])
      T[a-2][b-2]=T[a][b]+1
    if T[a-2][b-1]==-2 and S[a-2][b-1]=='.':
      q0.append([a-2, b-1])
      T[a-2][b-1]=T[a][b]+1
    if T[a-2][b]==-2 and S[a-2][b]=='.':
      q0.append([a-2, b])
      T[a-2][b]=T[a][b]+1
    if T[a-2][b+1]==-2 and S[a-2][b+1]=='.':
      q0.append([a-2, b+1])
      T[a-2][b+1]=T[a][b]+1
    if T[a-2][b+2]==-2 and S[a-2][b+2]=='.':
      q0.append([a-2, b+2])
      T[a-2][b+2]=T[a][b]+1
    if T[a-1][b-2]==-2 and S[a-1][b-2]=='.':
      q0.append([a-1, b-2])
      T[a-1][b-2]=T[a][b]+1
    if T[a-1][b-1]==-2 and S[a-1][b-1]=='.':
      q0.append([a-1, b-1])
      T[a-1][b-1]=T[a][b]+1
    if T[a-1][b+1]==-2 and S[a-1][b+1]=='.':
      q0.append([a-1, b+1])
      T[a-1][b+1]=T[a][b]+1
    if T[a-1][b+2]==-2 and S[a-1][b+2]=='.':
      q0.append([a-1, b+2])
      T[a-1][b+2]=T[a][b]+1
    if T[a][b-2]==-2 and S[a][b-2]=='.':
      q0.append([a, b-2])
      T[a][b-2]=T[a][b]+1
    if T[a][b+2]==-2 and S[a][b+2]=='.':
      q0.append([a, b+2])
      T[a][b+2]=T[a][b]+1
    if T[a+1][b-2]==-2 and S[a+1][b-2]=='.':
      q0.append([a+1, b-2])
      T[a+1][b-2]=T[a][b]+1
    if T[a+1][b-1]==-2 and S[a+1][b-1]=='.':
      q0.append([a+1, b-1])
      T[a+1][b-1]=T[a][b]+1
    if T[a+1][b+1]==-2 and S[a+1][b+1]=='.':
      q0.append([a+1, b+1])
      T[a+1][b+1]=T[a][b]+1
    if T[a+1][b+2]==-2 and S[a+1][b+2]=='.':
      q0.append([a+1, b+2])
      T[a+1][b+2]=T[a][b]+1
    if T[a+2][b-2]==-2 and S[a+2][b-2]=='.':
      q0.append([a+2, b-2])
      T[a+2][b-2]=T[a][b]+1
    if T[a+2][b-1]==-2 and S[a+2][b-1]=='.':
      q0.append([a+2, b-1])
      T[a+2][b-1]=T[a][b]+1
    if T[a+2][b]==-2 and S[a+2][b]=='.':
      q0.append([a+2, b])
      T[a+2][b]=T[a][b]+1
    if T[a+2][b+1]==-2 and S[a+2][b+1]=='.':
      q0.append([a+2, b+1])
      T[a+2][b+1]=T[a][b]+1
    if T[a+2][b+2]==-2 and S[a+2][b+2]=='.':
      q0.append([a+2, b+2])
      T[a+2][b+2]=T[a][b]+1
      
    
if T[Dh][Dw]>-1:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# ---------------------------iye ha aam zindegi---------------------------------------------
import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
#setrecursionlimit(300000)
# ------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
#sys.setrecursionlimit(300000)
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")


# -------------------game starts now----------------------------------------------------import math
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# -------------------------------iye ha chutiya zindegi-------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


# --------------------------------------iye ha combinations ka zindegi---------------------------------
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m


# --------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z


# --------------------------------------------------product----------------------------------------
def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por


# --------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] < key):
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


# --------------------------------------------------binary----------------------------------------
def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c
def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)


# --------------------------------------------------binary------------------------------------
class BinaryTrie:
    class Node:
        def __init__(self, bit: bool = False):
            self.bit = bit  # Stores the current bit (False if 0, True if 1)
            self.children = []
            self.count = 0  # stores number of keys finishing at this bit
            self.counter = 1  # stores number of keys with this bit as prefix

    def __init__(self, size):
        self.root = BinaryTrie.Node()
        self.size = size  # Maximum size of each key

    def convert(self, key):
        """Converts key from string/integer to a list of boolean values!"""
        bits = []
        if isinstance(key, int):
            key = bin(key)[2:]
        if isinstance(key, str):
            for i in range(self.size - len(key)):
                bits += [False]
            for i in key:
                if i == "0":
                    bits += [False]
                else:
                    bits += [True]
        else:
            return list(key)
        return bits

    def add(self, key):
        """Add a key to the trie!"""
        node = self.root
        bits = self.convert(key)
        for bit in bits:
            found_in_child = False
            for child in node.children:
                if child.bit == bit:
                    child.counter += 1
                    node = child
                    found_in_child = True
                    break
            if not found_in_child:
                new_node = BinaryTrie.Node(bit)
                node.children.append(new_node)
                node = new_node
        node.count += 1

    def remove(self, key):
        """Removes a key from the trie! If there are multiple occurences, it removes only one of them."""
        node = self.root
        bits = self.convert(key)
        nodelist = [node]
        for bit in bits:
            for child in node.children:
                if child.bit == bit:
                    node = child
                    node.counter -= 1
                    nodelist.append(node)
                    break
        node.count -= 1
        if not node.children and not node.count:
            for i in range(len(nodelist) - 2, -1, -1):
                nodelist[i].children.remove(nodelist[i + 1])
                if nodelist[i].children or nodelist[i].count:
                    break

    def query(self, prefix, root=None):
        """Search for a prefix in the trie! Returns the node if found, otherwise 0."""
        if not root: root = self.root
        node = root
        if not root.children:
            return 0
        for bit in prefix:
            bit_not_found = True
            for child in node.children:
                if child.bit == bit:
                    bit_not_found = False
                    node = child
                    break
            if bit_not_found:
                return 0
        return node
#--------------------------------------------trie-------------------------------------------------
class TrieNode:

    # Trie node class
    def __init__(self):
        self.children = [None] * 26
        self.data=0
        self.isEndOfWord = False


class Trie:

    # Trie data structure class
    def __init__(self):
        self.root = self.getNode()

    def getNode(self):

        # Returns new trie node (initialized to NULLs)
        return TrieNode()

    def _charToIndex(self, ch):

        # private helper function
        # Converts key current character into index
        # use only 'a' through 'z' and lower case

        return ord(ch) - ord('a')

    def insert(self, key,val):
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])

            # if current character is not present
            if not pCrawl.children[index]:
                pCrawl.children[index] = self.getNode()
            pCrawl = pCrawl.children[index]
            pCrawl.data+=val
        pCrawl.isEndOfWord = True

    def search(self, key):

        # Search key in the trie
        # Returns true if key presents
        # in trie, else false
        pCrawl = self.root
        length = len(key)
        c=0
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
        return pCrawl!=None
    def present(self, key):
        ans=0
        pCrawl = self.root
        length = len(key)
        c=0
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
            ans+=pCrawl.data
        if pCrawl!=None:
            return ans
        return -1
#----------------------------------trie----------------------------
n,m=map(int,input().split())
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(input()))
for i in range(n):
    for j in range(m):
        if l[i][j]=='.':
            l[i][j]==0
        else:
            l[i][j]=1
dp=[[999999999999 for i in range(m+1)]for j in range(n+1)]
dp[x1-1][y1-1]=0
def BFS(s):
    visited = [[False for i in range(m)]for j in range(n)]
    acc=set()
    queue = []
    queue.append(s)
    visited[s[0]][s[1]] = True
    while (queue):
        s = queue.pop(0)
        for j in range(-2,3):
            for k in range(-2,3):
                if j==0 and k==0:
                    continue
                if 0<=s[0]+j<n and 0<=s[1]+k<m and visited[s[0]+j][s[1]+k] == False and l[s[0]+j][s[1]+k]!=1:
                    queue.append((s[0]+j,s[1]+k))
                    dp[s[0]+j][s[1]+k]=min(dp[s[0]][s[1]]+1,dp[s[0]+j][s[1]+k])
                    if abs(j)==1 and abs(k)==0:
                        #print(s[0] + j,s[1] + k)
                        dp[s[0] + j][s[1] + k] = min(dp[s[0]][s[1]], dp[s[0] + j][s[1] + k])
                        visited[s[0]+j][s[1]+k] = True
                    elif abs(k)==1 and abs(j)==0:
                        #print(s[0] + j,s[1] + k)
                        dp[s[0] + j][s[1] + k] = min(dp[s[0]][s[1]], dp[s[0] + j][s[1] + k])
                        visited[s[0]+j][s[1]+k] = True
    return dp[x2-1][y2-1]
ans=BFS((x1-1,y1-1))
if ans==999999999999:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1
S = [[None] * W for _ in range(H)]
for i in range(H):
    for j, c in enumerate(input()):
        S[i][j] = c


if S[D_h][D_w] == '#' or S[C_h][C_w] == '#':
    print(-1)
else:
    queue = [(0, (C_h, C_w))]
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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


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

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

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

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)
    for dx,dy in move:
      mx,my = nx+dx,ny+dy

      if 0<=mx<w and 0<=my<h and l[my][mx]=="." and (cnt<done[my][mx]):
        done[my][mx]=cnt
        que.append([mx,my,cnt])

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


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

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