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
import sys
sys.setrecursionlimit(10 ** 9)
h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
s = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
visited[ch][cw] = 1
queue = deque([[ch, cw, 0]])
queue2 = deque([])


def bfs():
    global s, visited, queue, queue2
    while queue:
        tmp_h, tmp_w, res = queue.pop()
        for p, q in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = tmp_h+p, tmp_w+q
            if (new_h, new_w) == (dh, dw):
                return res
            if new_h < 0 or new_h >= h or \
               new_w < 0 or new_w >= w:
                continue
            elif s[new_h][new_w] != '#' and \
                    visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                queue.appendleft([new_h, new_w, res])
            elif s[new_h][new_w] == '#':
                for p_ in [-2, -1, 0, 1, 2]:
                    for q_ in [-2, -1, 0, 1, 2]:
                        new_h, new_w = tmp_h+p_, tmp_w+q_
                        if new_h < 0 or new_h >= h or \
                                new_w < 0 or new_w >= w:
                            continue
                        elif s[new_h][new_w] != '#' and \
                                visited[new_h][new_w] == 0:
                            queue2.appendleft([new_h, new_w, res+1])
    while queue2:
        tmp_h, tmp_w, res = queue2.pop()
        if visited[tmp_h][tmp_w] == 0:
            queue.appendleft([tmp_h, tmp_w, res])
            break

    if (not queue) and (not queue2):
        return -1

    return bfs()


print(bfs())

Submission status: Time Limit Exceeded

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

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

def dist(x1, y1, x2, y2):
    return (x1-x2) ** 2 + (y1-y2) ** 2

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



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

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

    seen.add((row, col))

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


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

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

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())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def cango_step(x,y):
    cand =[]
    if x+1<=H-1:
        cand.append((x+1,y))
    if x-1>=0:
        cand.append((x-1,y))
    if y+1<=W-1:
        cand.append((x,y+1))
    if y-1>=0:
        cand.append((x,y-1))
    return cand
def cango_warp(x,y):
    cand = [(i,j) 
            for i in range(x-2,x+3) for j in range(y-2,y+3) 
            if 0<=i and i<=H-1 and 0<=j and j<=W-1]
    return cand

been = [[False]*W for _ in range(H)]
rooms=dict()
i_room=-1
for x in range(H):
    for y in range(W):
        if S[x][y]=="." and not been[x][y]:
            i_room+=1
            been[x][y]=True
            q = deque([(-1,-1,x,y)]) 

            rooms[(x,y)]=i_room
            while q:
                x_old,y_old,x_now,y_now = q.popleft()
                
                cand = cango_step(x_now,y_now)
                #print(x_old,y_old,x_now,y_now,time)
                
                if x_now==CH-1 and y_now==CW-1:
                    start_warp = i_room
                if x_now==DH-1 and y_now==DW-1:
                    end_warp = i_room
                
                for x_new,y_new in cand:
                    if not been[x_new][y_new] and S[x_new][y_new]==".":
                        q.append((x_now,y_now,x_new,y_new))
                        been[x_new][y_new]=True
#                        room.append((x_new,y_new))
                        rooms[(x_new,y_new)]=i_room
#            rooms.append(room)

if start_warp==end_warp:
    print(0)
else:
        
    #ワープで行けるほかの部屋をtree入れる
    n_rooms = i_room+1
    tree=[[] for _ in range(n_rooms)]
    
    i_loop=0
    for k,v in rooms.items():
        i_loop+=1
        cango = set(rooms[togo] for togo in cango_warp(*k) if S[togo[0]][togo[1]]=="." )
        for c in cango:
            if c!=v:
                tree[c].append(v)
                tree[v].append(c)
        if i_loop%1000==0:
            for i in range(len(tree)):
                tree[i] = list(set(tree[i]))
        #print(v,cango)

        
    for i in range(len(tree)):
        tree[i] = set(tree[i])
    
    
    q = deque([(-1,start_warp,0)]) #これでもよい
    
    been=[False]*n_rooms
    been[start_warp]=True
    reach=False
    while q:
        parent,x,time = q.popleft()
        if x==end_warp:
            reach=True
            break
        
        for y in tree[x]:
            if not been[y]:
                q.append((x,y,time+1))#子ノードを追加
                been[y]=True
        #print(parent,x,q,time)
    if reach:
        print(time)
    else:
        print(-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])
    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])

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)
    djkistra(g,x*m+y,dist)
    # 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:
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

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

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in [-2, 0, 2]:
                for g in [-2, 0, 2]:
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
 
H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region
 
regions = []
field = copy.deepcopy(S)
 
for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1
 
for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i
 
count = 0
d = deque()
arrived = set()
arrived_pos = set()
d.append(s_reg)
arrived.add(s_reg)
 
while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for i in range(len(regions)):
    if i not in arrived and i != pos:
      for pos1 in regions[i]:
        for pos2 in regions[pos]:
          hd = abs(pos1[0] - pos2[0])
          wd = abs(pos1[1] - pos2[1])
          if hd <= 2 and wd <= 2:
            if i not in arrived:
              arrived.add(i)
              d.append(i)
  count += 1
            
if g_reg not in arrived:
  print(-1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n , m = map(int, input().split())
ch , cw = map(int, input().split())
dh , dw = map(int, input().split())
maze = [['#','#']+list(input())+['#','#'] for i in range(n)]
maze = [['#']*(m+4)]+[['#']*(m+4)]+maze+[['#']*(m+4)]+[['#']*(m+4)]

step = [(0,1),(1,0),(-1,0),(0,-1)]
warp_u = [(-2,0)]
warp_d = [(2,0)]
warp_r = [(0,2)]
warp_l = [(0,-2)]
warp_ur = [(-1,1),(-2,1),(-2,2),(0,2),(-2,0),(-1,2)]
warp_dr = [(2,0),(2,1),(2,2),(1,1),(1,2),(0,2)]
warp_ul = [(-2,0),(-2,-1),(-2,-2),(-1,-1),(-1,-2),(0,-2)]
warp_dl = [(2,0),(2,-1),(2,-2),(1,-1),(1,-2),(0,-2)]



warp=0

v = [[-1]*(m+4) for i in range(n+4)]
d = deque()
d.append((ch+1,cw+1,0,0,0))
v[ch+1][cw+1]=0
while d:
    y,x,wa,ex_y,ex_x=d.popleft()
    for dy,dx in step:
        if dy==ex_y*(-1) and dx==ex_x*(-1):
            continue
        if maze[y+dy][x+dx]=='.' and (v[y+dy][x+dx]==-1 or v[y+dy][x+dx]>wa):
            v[y+dy][x+dx]=wa
            d.append((y+dy,x+dx,wa,dy,dx))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_d:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_dr:
                if dy2==ex_y*(-1) and dx2==ex_x*(-1):
                    continue
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_dl:
                if dy2==ex_y*(-1) and dx2==ex_x*(-1):
                    continue
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_r:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_u:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_l:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
print(v[dh+1][dw+1])

Submission status: Time Limit Exceeded

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

import collections
import sys
input=sys.stdin.readline

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append(r2)
                    checked.add((r1,r2))
q=collections.deque()
q.append(((uf.FindRoot((sy-1)*w+(sx-1))),0))
checked=[False]*(h*w+1)
ans=10**18
goal=uf.FindRoot((gy-1)*w+(gx-1))
while len(q)!=0:
    v,times=q.popleft()
    if v==goal:
        ans=min(ans,times)
        break
    checked[v]=True
    for u in edges[v]:
        if checked[u]==False:
            q.append((u,times+1))
if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
from collections import deque
import sys
sys.setrecursionlimit(10**8) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  while len(q):
    y,x=q.popleft()
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              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
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:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = [[False]*W for _ in range(H)]
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and not used[h][w]:
                    v[h][w] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    worp += 1
    for h in range(H):
        for w in range(W):
            if v[h][w] and not used[h][w]:
                q.append([h, w])
                used[h][w] = True

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
maze = [['#']*(W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#']*(W+2)]
around = [[-1,0], [0,-1], [1,0], [0,1]]
more_around = [[i-2,j-2] for i in range(5) for j in range(5)]
t = 0

que = deque([start])
while len(que) > 0:
    nque = []
    while len(que) > 0:
        h, w = que.popleft()
        if [h, w] == goal:
            print(t)
            exit()
        maze[h][w] = t
        DE = True
        for i, j in around:
            if maze[h+i][w+j] == '.':
                que.append([h+i, w+j])
                DE = False
        if DE:
            nque.append([h, w])
    
    que = deque(nque)
    nque = []
    while len(que) > 0:
        h, w = que.popleft()
        for i, j in more_around:
            if 0 <= h+i <= H+1 and 0 <= w+j <= W+1:
                if maze[h+i][w+j] == '.':
                    nque.append([h+i, w+j])
    que = deque(nque)
    t += 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=10000000000
input=sys.stdin.readline
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input().split()[0])
q=dq([cx*m+cy])
dis=[inf]*(n*m+1)
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=dd(list)
for x in range(n):
    for y in range(m):
        
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.'):
                d[x*m+y].append((X*m+Y,0))
        X=x-2
        Y=y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.'):
                    if((abs(X+i-x)+abs(Y+j-y))>1):
                        d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    #print(curr)
    if(curr==des):
        print(dis[curr])
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solvemaze(y, x, num):
    maps.append([])
    dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
    maze[y][x] = num
    que = deque()
    que.append((y, x))
    while que:
        y_, x_ = que.popleft()
        maps[num].append((y_, x_))
        for i in range(4):
            y2 = y_ + dy[i]
            x2 = x_ + dx[i]
            if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] == '.':
                maze[y2][x2] = num
                que.append((y2, x2))

def makeroute(s_maps, num):
    for y, x in s_maps:
        for i in range(-2, 3):
            for j in range(-2, 3):
                y2 = y + i
                x2 = x + j
                if 0 <= y2 < h and 0 <= x2 < w:
                    num2 = maze[y2][x2]
                    if not  num2 in [0, '#'] + E[num]:
                        E[num].append(num2)
                        E[num2].append(num)
    

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
maps = []

num = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            solvemaze(i, j, num)
            num += 1

E = [[] for _ in range(num)]
for i in range(num):
    makeroute(maps[i], i)

s = maze[Ch-1][Cw-1]
g = maze[Dh-1][Dw-1]
used = [False] * num
used[s] = True
que = deque()
que.append((0, s))
cost = [float('inf')] * num
cost[s] = 0
while que:
    c, v = que.popleft()
    for e in E[v]:
        if not used[e]:
            que.append((c+1, e))
            cost[e] = c+1
            used[e] = True

if not used[g]:
    print(-1)
else:
    print(cost[g])