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:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
MV = [(-1, 0), (0, -1), (1, 0), (0, 1)]
WP = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
WL = []
WL_next = []
S = []


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


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

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

Submission status: Time Limit Exceeded

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

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

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

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

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


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


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

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

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

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

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

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

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


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 deque

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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    l = list(d)
    d = deque()
    for Th,Tw in l:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in l) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.append((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.add(k)
						
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.add(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
visited = [[-2]*(w+2) for i in range(h+2)]
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]==".":
			visited[i][j] = -1

delta1 = [[0,1],[1,0],[-1,0],[0,-1]]

q = {(ch,cw)}
set_list = set()
cost = 0
while 1:
	if len(q)==0:
		break
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		for dx,dy in delta1:
			x2 = x+dx
			y2 = y+dy
			if visited[x2][y2]==-1:
				q.add((x2,y2))
	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for dx in range(-2,3):
			for dy in range(-2,3):
				x2 = x+dx
				y2 = y+dy
				if visited[min(x2,h+1)][min(y2,w+1)]!=-1: continue
				q.add((x2,y2))

print(visited[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

H, W = list(map(int, input().strip().split()))
Ch, Cw = list(map(int, input().strip().split()))
Dh, Dw = list(map(int, input().strip().split()))
mazeMap = []
for i in range(H):
    mazeLength = input()
    array = []
    for j in range(W):
        array.append(mazeLength[j])
    mazeMap.append(array)
mapping = copy.copy(mazeMap)
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1
vec = [[1,0],[-1,0],[0,1],[0,-1]]
warpCount = 0
sys.setrecursionlimit(100000000)

def mazeMapping(Mh, Mw):
    global mapping
    mapping[Mh][Mw] = "*"
    for i in range(len(vec)):
        if Mh+vec[i][0] < 0 or Mh+vec[i][0] >= H:
            continue;
        elif Mw+vec[i][1] < 0 or Mw+vec[i][1] >= W:
            continue;
        elif mapping[Mh+vec[i][0]][Mw+vec[i][1]] == "#":
            continue;
        elif mapping[Mh+vec[i][0]][Mw+vec[i][1]] == ".":
            mazeMapping(Mh+vec[i][0],Mw+vec[i][1])
    return;

def mazeWarping(Mh, Mw):
    global Ch
    global Cw
    global warpCount
    for i in range(5):
        for j in range(5):
            if Mh+i-2 < 0 or Mh+i-2 >= H:
                continue;
            elif Mw+j-2 < 0 or Mw+j-2 >= W:
                continue;
            elif mapping[Mh+i-2][Mw+j-2] == ".":
                Ch = Mh+i-2
                Cw = Mw+j-2
                warpCount += 1
                return True;
    return False;

while True:
    if mapping[Dh][Dw] == "*":
        print(warpCount)
        break;
    elif mapping[Dh][Dw] == "#":
        print(-1)
        break;
    elif mapping[Ch][Cw] == "*":
        print(-1)
        break;
    mazeMapping(Ch, Cw)
    for i in range(H):
        for j in range(W):
            if mapping[i][j] == "*":
                canWarp = mazeWarping(i,j)
                if canWarp == True:
                    break;
        else:
            continue;
        break;

Submission status: Time Limit Exceeded

Solution code:
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in P:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
            que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
yukaset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in settansaku:
						setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in P:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
            que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

V[C[0]][C[1]] = 0

pool = deque()
pool.append(tuple([0, C[0], C[1]]))
while(pool):
    c, y, x = pool.pop()
    if c != V[y][x]:
        continue
    for dx in [-2, -1, 0, 1, 2]:
        for dy in [-2, -1, 0, 1, 2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.appendleft((c, y+dy, x+dx))
            elif V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((c+1, y+dy, x+dx))
print(V[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [input().strip() for _ in range(H)]

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

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import heapq
xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

h,w=map(int,input().split())
c1,c2=map(int,input().split())
d1,d2=map(int,input().split())
d=[list(input().rstrip()) for i in range(h)]
d[c1-1][c2-1]=0
p=[]
heapq.heappush(p,(0,c1-1,c2-1))
while len(p):
    a,b,c=heapq.heappop(p)
    for x,y in xy:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a:
                d[x][y]=a
                heapq.heappush(p,(a,x,y))
    for x,y in wp:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a+1:
                d[x][y]=a+1
                heapq.heappush(p,(a+1,x,y))
#    if len(p)>2000:
#        print(-1)
#    print(p)
#    if d[d1-1][d2-1]==a:
#        print(a)
#        exit()
#    print(p)
#    print(d)

print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Time Limit Exceeded

Solution code:
class P:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False
        self.checked = False

from collections import deque
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [[None for _ in range(H)] for _ in range(W)]
for y in range(H):
    tmp = input()
    for x in range(W):
        S[x][y] = P(tmp[x])

def neighbors(x, y, d):
    for i in range(max(0, x-1), min(W, x+2)):
        if S[i][y].reached == False and S[i][y].c == '.':
            d.append((i, y))
    for i in range(max(0, y-1), min(H, y+2)):
        if S[x][i].reached == False and S[x][i].c == '.':
            d.append((x, i))

def jump(x, y, d):
    S[x][y].checked = True
    for i in range(max(0, x-2), min(W, x+3)):
        for j in range(max(0, y-2), min(H, y+3)):
            if S[i][j].reached == False and S[i][j].searched == False and S[i][j].c == '.':
                d.append((i, j))
                S[i][j].searched = True


def BFS(x, y):
    d = deque([(x, y)])
    route = deque([])
    while True:
        x, y = d.popleft()
        route.append((x, y))
        S[x][y].reached = True
        neighbors(x, y, d)
        if len(d) == 0:
            break
    return route


counter = 0
if Cw == Dw and Ch == Dh:
    print(0)
    exit()
q = deque([(Cw, Ch)])
flag = False
while True:
    array = []
    while len(q) > 0:
        x, y = q.popleft()
        if S[x][y].reached:
            pass
        else:
            array.append(BFS(x, y))
    if S[Dw][Dh].reached == True:
        break
    counter += 1
    for each in array:
        while len(each) > 0:
            i, j = each.pop()
            if S[i][j].reached and S[i][j].checked == False:
                jump(i, j, q)
    if len(q) == 0:
        flag = True
        break
if flag:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != '#':
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input().strip()) for _ in range(H)]

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

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))