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:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    data = list(data.reshape(-1))
    HEIGHT = H + 4
    WIDTH = W + 4
    N = HEIGHT * WIDTH
    visited = [0] * N
    distance = [0] * N
    jump = [0] * N
    from collections import deque

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = deque()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if visited[p]:
                continue
            if p == goal:
                return currentDistance
            distance[p] = currentDistance
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    jump[p + dx + dy] = currentDistance + 1
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d]:
                    q.append(p + d)

        # no continuous cell
        for i in range(HEIGHT * WIDTH):
            if not data[i]:
                continue
            if visited[i]:
                continue
            # not visited vacant cell
            if jump[i] > 0:
                q.append(i)
        currentDistance += 1
        if not q:
            return -1

    # print(distance)
    # print(visited.reshape((H+4, -1)))


def main():
    global data
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    data = np.array(list(read().strip()) + [0])
    data = np.equal(data, 46).reshape((H, W + 1))
    D = np.zeros((H + 4, W + 4), dtype=np.int8)
    D[2:2+H, 2:2+W+1] = data
    # print(data)
    # print(D)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

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

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      #print(node)
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))

      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))

    Q = new_Q

  #print(f1,f2)
  if V[f1][f2]==1:
    print(count)
    break
  else:
    #print(V)
    temp = sum(sum(kk) for kk in V) 
    count += 1
    #print(ALL,best,temp)
    part= []
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w:
            if G[x][y] == '.':
              V[x][y] = 1
              part.append((x,y))
              
    part = list(set(part))
    ALL = part+ALL

    if temp==best:
      print(-1)
      break
    else:
      best = temp

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        f = False
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] == '.':
                    if dist[ni][nj] > d:
                        dist[ni][nj] = d
                        q.append((ni, nj))
                else:
                    f = True
        if f:
            for ni in range(i - 2, i + 2 + 1, 1):
                for nj in range(j - 2, j + 2 + 1, 1):
                    if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                        if dist[ni][nj] > d + 1:
                            dist[ni][nj] = d + 1
                            q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    djk=Dijkstra((H+4)*(W+4))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    for i in range(2,H+2):
        for j in range(2,W+2):
            if S[i][j]!="#":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]!="#":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        djk.add(fro,to,0)
                for k in range(20):
                    ii=i+dx2[k]
                    jj=j+dy2[k]
                    if S[ii][jj]!="#":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        djk.add(fro,to,1)
                        
    s=ch*(W+4)+cw
    g=dh*(W+4)+dw
    D=djk.shortest_path(s)
    ans=D[g]
    if ans>=10**6+5:
        ans=-1
    print(ans)
                    
                

main()

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
input = sys.stdin.readline

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())
num = [[float("inf") for i in range(w)] for i in range(h)]
flag = [[False for i in range(w)] for i in range(h)]
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
d2 = [[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]]
d3 = [[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]]
d4 = [[-2, -2], [-2, 2], [2, -2], [2, 2]]
while queue:
    test = queue.popleft()
    x = test[0]
    y = test[1]
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = temp
            queue.append([x2, y2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(num[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        h = []
        self.set(start[1], start[0], 0)
        heappush(h, (0, cx, cy))
        while h:
            cc, cx, cy = heappop(h)
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    heappush(h, (cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    heappush(h, (cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    D_h, D_w = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    F = [[float('inf')] * W for _ in range(H)]
    queue = deque([(C_h - 1, C_w - 1)])
    nextqueue = deque([])
    t = 0
    alr = set()
    while queue:
        i, j = queue.popleft()
        if not (i, j) in alr:
            F[i][j] = min(t, F[i][j])
            if D_h == i + 1 and D_w == j + 1:
                break
            alr.add((i, j))
            for dx, dy in direction:
                nx, ny = i + dx, j + dy
                if 0 <= nx <= H - 1 and 0 <= ny <= W - 1:
                    if field[nx][ny] == '.':
                        queue.append((nx, ny))
            for p in range(i - 2, i + 3):
                for q in range(j - 2, j + 3):
                    if 0 <= p <= H - 1 and 0 <= q <= W - 1:
                        if field[p][q] == '.':
                            nextqueue.append((p, q))
                            F[p][q] = min(F[p][q], t + 1)
        if not queue:
            queue = nextqueue.copy()
            nextqueue.clear()
            t += 1

    if F[D_h-1][D_w-1] == float('inf'):
        print(-1)
    else:
        print(F[D_h - 1][D_w - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque
import sys

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

MAZE = []

for i in range(H):
    MAZE.append([-1 if x == '#' else -2  for x in input()])

que = deque()
que.append((CH, CW, 0))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

while len(que):
    cur_h, cur_w, cost = que[0]
#    print(cur_h, cur_w, cost)
    que.popleft()
    if MAZE[cur_h][cur_w] == -1:
        continue
    if MAZE[cur_h][cur_w] <= cost and MAZE[cur_h][cur_w] != -2:
        continue

    MAZE[cur_h][cur_w] = cost

    for h, w in can_walk:
        next_h = cur_h + h 
        next_w = cur_w + w 
        if next_h < 0 or next_w < 0 or next_h >= H or next_w >= W:
            continue
        que.append((next_h, next_w, cost))

    for h in (-2, -1, 0, 1, 2):
        for w in (-2, -1, 0, 1, 2):
            if (h, w) in can_walk :
                continue 

            next_h = cur_h + h 
            next_w = cur_w + w 
            if next_h < 0 or next_w < 0 or next_h >= H or next_w >= W:
                continue
            que.append((next_h, next_w, cost+1))

#for i in range(H):
#    print (MAZE[i])
ret = MAZE[DH][DW]
if ret < 0:
    print(-1)
else:
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input().rstrip()) for _ in range(H)]

dir_h = [0, 0, 1, -1]
dir_w = [1, -1, 0, 0]

seen = [[-1 for _ in range(W)] for _ in range(H)]
edge = []
nex = [[ch - 1, cw - 1]]
num = 0


def bfs():
    q = deque([])

    for h, w in nex:
        q.append([h, w])
        seen[h][w] = num
        while q:
            h, w = q.popleft()

            for dh, dw in zip(dir_h, dir_w):
                nh, nw = h + dh, w + dw

                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                elif S[nh][nw] == "#":
                    edge.append([h, w])
                    continue
                elif seen[nh][nw] != -1:
                    continue
                else:
                    seen[nh][nw] = num
                    q.append([nh, nw])


def dfs():
    d = deque([])
    for h, w in edge:
        d.append([h, w])

        while d:
            h, w = d.pop()
            num = seen[h][w]
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw

                    if nh < 0 or nh >= H or nw < 0 or nw >= W:
                        continue
                    elif S[nh][nw] == "#":
                        continue
                    elif seen[nh][nw] != -1:
                        continue
                    else:
                        seen[nh][nw] = min(num, seen[nh][nw])
                        nex.append([nh, nw])


while True:
    bfs()
    if not edge:
        break
    nex = []
    num += 1
    dfs()
    if not nex:
        break
    edge = []

# for s in seen:
#     print(s)

print(seen[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
H, W = [int(x) for x in 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

cell = [list(input()) for i in range(H)]

dp = [[-1]*W for _ in range(H)]

stack = deque()
stack.append([Ch,Cw])

dp[Ch][Cw] = 0

while len(stack) > 0:
    h,w = stack.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dy
        nw = w + dx
        if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
            if cell[nh][nw] == '.':
                dp[nh][nw] = dp[h][w]
                stack.append([nh,nw])
            else:
                for ddy in range(-2,3):
                    for ddx in range(-2,3):
                        if ddy==ddx==0:
                            continue
                        nnh = h + ddy
                        nnw = w + ddx
                        if 0 <= nnh < H and 0 <= nnw < W:
                            if cell[nnh][nnw] == '.' and (dp[nnh][nnw] == -1 or dp[nnh][nnw] > dp[h][w]+1):
                                dp[nnh][nnw] = dp[h][w] + 1
                                stack.append([nnh,nnw])
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
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
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))

es=[set([]) for _ in range(col)]
visited=[-1]*col
for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if (x,y) in dif:
                        continue
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    S = [['#'] * (W + 4)]
    tmp = ['#'] * (W + 4)
    S.append(tmp)

    for _ in range(H):
        tmp = ['#', '#'] + list(input()) + ['#']
        S.append(tmp)

    tmp = ['#'] * (W + 4)
    S.append(tmp)
    S.append(tmp)
    # print (*S, sep = '\n')

    INF = 10 ** 9

    G = [[INF] * (W + 4) for _ in range(H + 4)] 

    move1 = ((1, 0), (-1, 0), (0, 1), (0, -1))

    pque = [(0, Ch + 1, Cw + 1)]
    G[Ch + 1][Cw + 1] = 0


    tmp_lst = []
    while pque:
        xy = heappop(pque)
        tmp, x, y = xy[0], xy[1], xy[2]
        # print (tmp, x, y)
        if G[x][y] < tmp: #すでに小さい
            continue

        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                if dx == 0 and dy == 0:
                    continue
                if S[nx][ny] == '.': #道の時
                    if (dx, dy) in move1:
                        if G[nx][ny] > tmp:
                            G[nx][ny] = tmp
                            heappush(pque, (tmp, nx, ny))
                    else:
                        if G[nx][ny] > tmp + 1:
                            G[nx][ny] = tmp + 1
                            heappush(pque, (tmp + 1, nx, ny))

    # print (*G, sep = '\n')

    if G[Dh + 1][Dw + 1] == INF:
        print (-1)
    else:
        print (G[Dh + 1][Dw + 1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

ch -= 1
cw -= 1
dh -= 1
dw -= 1

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

cost = [[-1] * w for _ in range(h)]
hq = [(0,ch,cw)]


while(hq):
    ci,xi,yi = heappop(hq)
    if(cost[xi][yi] != -1):
        continue
    cost[xi][yi] = ci

    for dx in range(-2,3):
        for dy in range(-2,3):
            xj,yj = xi+dx,yi+dy
            # print(xi,yi,xj,yj)
            if(xj<0)|(xj>=h)|(yj<0)|(yj>=w):
                continue
            if(cost[xj][yj]!=-1):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                heappush(hq,(ci,xj,yj))
            else:
                heappush(hq,(ci+1,xj,yj))

print(cost[dh][dw])

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [list(input()) for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    if D > d[y][x]:
        continue
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if i == 0 and j == 0:
                continue
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '#':
                    continue
                if abs(i) + abs(j) <= 1:
                    if d[ny][nx] > D:
                        d[ny][nx] = D
                        heappush(H, (D, nx, ny))
                else:
                    if d[ny][nx] > D + 1:
                        d[ny][nx] = D + 1
                        heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, cnt):
    flag = [1] * 4
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            flag[i] = 0
            d[nx][ny] = cnt
            dfs(nx, ny, cnt)
    for i in range(4):
        if flag[i]:
            nx = x + tx[i] * 2
            ny = y + ty[i] * 2
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
                d[nx][ny] = cnt + 1
                dfs(nx, ny, cnt + 1)
    for i in range(4):
        if flag[i] & flag[(i+1) % 4]:
            for j in range(1, 3):
                for k in range(1, 3):
                    nx = x + tx[i] * j + tx[(i+1) % 4] * k
                    ny = y + ty[i] * j + ty[(i+1) % 4] * k
                    if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
                        d[nx][ny] = cnt + 1
                        dfs(nx, ny, cnt + 1)

d[C[0]-1][C[1]-1] = 0
dfs(C[0]-1, C[1]-1, 0)

if d[D[0]-1][D[1]-1] == INF:
    print(-1)
else:
    print(d[D[0]-1][D[1]-1])