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:
"""
    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**6]*(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**6):
        print(-1)
    else:
        print(dist[xnot*m+ynot])









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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

def dijkstra(i, V, E, INF=1e9):
    D = {v: INF for v in V}
    D[i] = 0
    Q = [(d, v) for v, d in D.items()]
    heapq.heapify(Q)
    prev = {v: None for v in V}

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        for v, duv in E[u].items():
            dv = du + duv
            if D[v] > dv:
                D[v] = dv
                prev[v] = u
                heapq.heappush(Q, (dv, v))
    return D

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

s = [list(input()) for _ in range(h)]
V = []
E = defaultdict(dict)
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        V.append((i, j))

        for k in range(-2, 3):
            for l in range(-2, 3):
                if k == 0 and l == 0:
                    continue
                x = i + k
                y = j + l
                if x < 0 or x >= h or y < 0 or y >= w or s[x][y] == '#':
                    continue
                if (k, l) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    E[(i, j)][(x, y)] = 0
                    E[(x, y)][(i, j)] = 0
                else:
                    E[(i, j)][(x, y)] = 1
                    E[(x, y)][(i, j)] = 1

INF = 1e9
D = dijkstra((ch, cw), V, E, INF=INF)

if D[(dh, dw)] == INF:
    print(-1)
else:
    print(D[(dh, dw)])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, visited,Ch,Cw,Dh,Dw):
  queue = deque([[Ch,Cw]])
  visited[Ch][Cw] = 0
  while queue:
    y,x = queue.popleft()

    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      new_y,new_x = y+j,x+k
      if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == ".":
        if visited[new_y][new_x] == "x" or  visited[new_y][new_x] > visited[y][x]:
          visited[new_y][new_x] = visited[y][x]
          queue.append([new_y,new_x])
      elif 0 <= new_y+j < H and 0 <= new_x+k < W and maze[new_y][new_x] == "#"and maze[new_y+j][new_x+k] == ".":
        if visited[new_y+j][new_x+k] == "x" or  visited[new_y+j][new_x+k] > visited[y][x]+1:
          visited[new_y+j][new_x+k] = visited[y][x] +1
          queue.append([new_y+j,new_x+k])
    for l,m in ([1,1],[1,-1],[-1,-1],[-1,1],[1,2],[2,1],[2,2],[1,-2],[2,-1],[2,-2],[-1,-1],[-2,-1],[-2,-2],[-1,-2],[-1,2],[-2,1],[-2,2]):
      ex_y,ex_x = y + l, x + m
      if 0 <= ex_y < H and 0 <= ex_x < W and maze[ex_y][ex_x] == ".":
        if visited[ex_y][ex_x] == "x" or  visited[ex_y][ex_x] > visited[y][x]+1:
          visited[ex_y][ex_x] = visited[y][x] +1
          queue.append([ex_y,ex_x])

  if visited[Dh][Dw] == "x":
    return -1
  else:
    return visited[Dh][Dw]
        
        
                                      
      
  
H, W = map(int,input().split())
Ch,Cw =  map(int,input().split())
Dh,Dw = map(int,input().split())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

maze = [input() for i in range(H)]
visited = [["x"]*W for j in range(H)]

print(bfs(maze, visited,Ch,Cw,Dh,Dw))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = [int(s) - 1 for s in input().split()]
Dh, Dw = [int(s) - 1 for s in input().split()]
S = [input() for _ in range(H)]

tree_check = [[0 for _ in range(W)] for _ in range(H)]


def tree(way_start):
    while way_start:
        way = way_start.pop(0)
        y = way[0]
        x = way[1]
        tree_check[y][x] = 1
        if x - 1 >= 0:
            if S[y][x - 1] == '.':
                if tree_check[y][x - 1] == 0:
                    tree_check[y][x - 1] = 1
                    way_start.append([y, x - 1])
        if x + 1 < W:
            if S[y][x + 1] == '.':
                if tree_check[y][x + 1] == 0:
                    tree_check[y][x + 1] = 1
                    way_start.append([y, x + 1])
        if y - 1 >= 0:
            if S[y - 1][x] == '.':
                if tree_check[y - 1][x] == 0:
                    tree_check[y - 1][x] = 1
                    way_start.append([y - 1, x])
        if y + 1 < H:
            if S[y + 1][x] == '.':
                if tree_check[y + 1][x] == 0:
                    tree_check[y + 1][x] = 1
                    way_start.append([y + 1, x])


def warp():
    result = []
    for h in range(H):
        for w in range(W):
            if tree_check[h][w] == 1:
                for i in range(-2, 2 + 1):
                    if 0 <= h + i < H:
                        for j in range(-2, 2 + 1):
                            if 0 <= w + j < W:
                                if tree_check[h + i][w + j] == 0:
                                    if S[h + i][w + j] == '.':
                                        result.append([h + i, w + j])
    return result


way_tree = [[Ch, Cw]]
ans = 0
while way_tree:
    tree(way_tree)
    if tree_check[Dh][Dw] == 0:
        ans += 1
        way_tree = warp()
    else:
        break

if tree_check[Dh][Dw] == 0:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(h, w, maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx, 0]])
    visited[sy][sx] = 0
    worps = []
    while queue:
        y, x, worp = queue.popleft()
        # print(y, x, worp)
        if [y, x] == [gy, gx]:
            worps.append(worp)
        walkable = False
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + k
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                continue
            if maze[new_y][new_x] == ".":
                if visited[new_y][new_x] == -1 or visited[new_y][new_x] > worp:
                    visited[new_y][new_x] = worp
                    queue.append([new_y, new_x, worp])
                    walkable = True

        if walkable is False:
            for s, t in (
                [1, 1],
                [1, -1],
                [-1, 1],
                [-1, -1],
                [2, 0],
                [2, 1],
                [2, -1],
                [2, 2],
                [2, -2],
                [1, 2],
                [1, -2],
                [0, 2],
                [0, -2],
                [-1, 2],
                [-1, -2],
                [-2, 0],
                [-2, 1],
                [-2, -1],
                [-2, 2],
                [-2, -2],
            ):
                new_y, new_x = y + s, x + t
                if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                    continue
                if maze[new_y][new_x] == ".":
                    if visited[new_y][new_x] == -1 or visited[new_y][new_x] > worp:
                        visited[new_y][new_x] = worp + 1
                        queue.append([new_y, new_x, worp + 1])
    return min(worps) if len(worps) > 0 else -1


if __name__ == "__main__":
    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())
    s = [list(input()) for i in range(h)]
    visited = [[-1] * w for j in range(h)]
    print(bfs(h, w, s, visited, ch, cw, dh, dw))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for i in range(H)]
     
def dijkstra(x,y):
    weight = {(x,y):0}
    checklist = []
    heappush(checklist,[0,x,y])
    while(checklist):
        weight_node,node_x,node_y = heappop(checklist)
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        for next_x in range(max(0,node_x-2),min(H,node_x+3)):
                for next_y in range(max(0,node_y-2),min(W,node_y+3)):
                    if next_x == node_x and next_y == node_y:
                        continue
                    elif s[next_x][next_y] == '.':
                        if (next_x,next_y) in [(node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)]:
                            weight_next_node = weight_node
                        else:
                            weight_next_node = weight_node + 1
                        if (next_x,next_y) not in weight or weight_next_node < weight[(next_x,next_y)]:
                            #print(next_x,next_y)
                            weight[(next_x,next_y)] = weight_next_node
                            heappush(checklist,[weight_next_node,next_x,next_y])
    return -1

print(dijkstra(ch-1,cw-1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def Walk(X, Y):
    return [[X-1, Y], [X+1, Y], [X, Y-1], [X, Y+1]]

def Magic(X, Y):
    Ret = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            Ret.append([X+x, Y+y])
    return Ret

D = [[float("inf")]*W for _ in range(H)]
D[Ch-1][Cw-1] = 0

Used = [[False]*W for _ in range(H)]

que = [(0, [Ch-1, Cw-1])]
while que:
    c, pos = heapq.heappop(que)
    if Used[pos[0]][pos[1]]:
        continue
    D[pos[0]][pos[1]] = c
    Used[pos[0]][pos[1]] = True
    if Dh - 1 == pos[0] and Dw -1 == pos[1]:
        break
    for pos_to in Magic(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    if not Used[pos_to[0]][pos_to[1]]:
                        Step = abs(pos_to[0]-pos[0]) + abs(pos_to[1]-pos[1])
                        if Step == 0:
                            continue
                        elif Step == 1:
                            heapq.heappush(que, (c, pos_to))
                        else:
                            heapq.heappush(que, (c+1, pos_to))
if D[Dh-1][Dw-1] == float("inf"):
    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())
ch,cw = map(int, input().split())
dh, dw = map(int, input().split())
ls = [input() for _ in range(h)]


widou = []

for i in range(-2,3):
    for j in range(-2, 3):
        widou.append((i, j))
widou.remove((0,0))
widou.remove((1,0))
widou.remove((0,1))
widou.remove((-1,0))
widou.remove((0,-1))
#print(widou)

start = (ch-1, cw-1)
goal = (dh-1, dw-1)

explored = set()
tempexplored = set()

yexp= deque()
yexp.append(start)
ytemp= deque()
ytemp.append(start)

wap = 0


while yexp:
    now = yexp.popleft()
    ytemp.popleft()

    if now == goal:
        print(wap)
        exit(0)

    x = now[0]
    y = now[1]

    explored.add((x, y))
    tempexplored.add((x, y))

    idou = [(1,0), (0,1), (0,-1), (-1,0)]
    for i, j in idou:
        a = x + i
        b = y + j
        if 0 <= a < h and 0 <= b < w:
            if ls[a][b] == '.':
                if (a, b) not in explored:
                    #print(a,b)
                    yexp.append((a,b))
                    ytemp.append((a,b))
                    explored.add((a,b))
                    tempexplored.add((a,b))
    #print(ytemp)
    #print(tempexplored)
    #print(explored)


    if len(ytemp) ==0:
        #print('waap')
        wap += 1
        for s,t in tempexplored:
            #print(s,t)
            for i, j in widou:
                #print(i,j)
                a = s + i
                b = t + j
                #print('kekka', a,b)


                if 0 <= a < h and 0 <= b < w:
                    #print(a, b)
                    if ls[a][b] == '.':
                        if (a, b) not in explored:
                            #print('OK')
                            yexp.append((a, b))
                            ytemp.append((a, b))
                            explored.add((a, b))
        tempexplored = set()
        #print(ytemp)
        #print(tempexplored)
        #print(explored)
print('-1')

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


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

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

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

dp = []
for i in range(1000):
    dp.append([1000000009]*1000)

vy = [1, 0, -1, 0, -2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
vx = [0, 1, 0, -1, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

def bfs():
    ans = 1000000009
    while not q.empty():
        now = q.get()
        y = now[0]
        x = now[1]
        depth = now[2]
        dp[y][x] = min(dp[y][x], depth)

        if y == g_y and x == g_x:
            ans = min(ans, dp[y][x])

        for i in range(24):
            next = [y+vy[i], x+vx[i], depth]
            if (0 <= next[0] and next[0] <= h-1 and 0 <= next[1] and next[1] <= w-1 and (s[next[0]][next[1]] == "." or (s[next[0]][next[1]] == "x" and depth < dp[next[0]][next[1]]))):
                s[next[0]][next[1]] = "x"
                if i >= 4:
                    next[2] += 1
                q.put(next)
    if ans == 1000000009:
        return -1
    else:
        return ans

h, w = map(int, input().split())
s_y, s_x = map(int, input().split())
g_y, g_x = map(int, input().split())
s_y -= 1
s_x -= 1
g_y -= 1
g_x -= 1


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

q = Queue()
q.put([s_y, s_x, 0])
s[s_y][s_x] = "x"
print(bfs())

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, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # 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 == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.appendleft((nx, ny, c+1, d, e))
    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] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                q.append((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def Walk(X, Y):
    return [[X-1, Y], [X+1, Y], [X, Y-1], [X, Y+1]]

def Magic(X, Y):
    Ret = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            Ret.append([X+x, Y+y])
    return Ret

D = [[float("inf")]*W for _ in range(H)]
D[Ch-1][Cw-1] = 0

Used = [[False]*W for _ in range(H)]

que = [(0, [Ch-1, Cw-1])]
while que:
    c, pos = heapq.heappop(que)
    if Used[pos[0]][pos[1]]:
        continue
    D[pos[0]][pos[1]] = c
    Used[pos[0]][pos[1]] = True
    if Dh - 1 == pos[0] and Dw -1 == pos[1]:
        break
    for pos_to in Magic(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    Step = abs(pos_to[0]-pos[0]) + abs(pos_to[1]-pos[1])
                    if Step == 0:
                        continue
                    elif Step == 1:
                        heapq.heappush(que, (c, pos_to))
                    else:
                        if D[pos_to[0]][pos_to[1]] > c+1:
                            heapq.heappush(que, (c+1, pos_to))
if D[Dh-1][Dw-1] == float("inf"):
    print(-1)
else:
    print(D[Dh-1][Dw-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%10000==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:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
deq = deque([(0,sh,sw)])
visited[sh][sw] = 0
ans = 10**9
while deq:
    rp,h,w = deq.pop()
    if h == gh and w == gw:
        ans = min(ans,rp)
        continue
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                deq.append((rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            deq.append((rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(ans if ans != 10**9 else -1)