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())
from collections import deque

grid =  ''
grid +=  '#' * (W+4) * 2
for h in range(H):
  S = str(input())
  grid += '#' * 2 + S + '#' * 2
grid +=  '#' * (W+4) * 2

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

Ch, Cw, Dh, Dw = Ch+1, Cw+1, Dh+1, Dw+1
usedss = [[0] * (W + 4) for _ in  range(H+4)]
      
for x in range(H+4):
  for y in range(W+4):
    if grid[x*(W+4)+y] == '#':
      usedss[x][y] = 1
      
VS = set([(Ch, Cw)])
new_VS = set([(Ch, Cw)])
usedss[Ch][Cw] = 1
      
ans = 0
while True:
  while VS:
      VS2  = set()
      for x, y in VS:
        for dx, dy in D:
          x_ = x + dx
          y_ = y + dy
          if usedss[x_][y_] == 1:
            continue
          VS2.add((x_,y_))
          new_VS.add((x_, y_))
          usedss[x_][y_] = 1
      VS = VS2
      #print(VS)
      
  if usedss[Dh][Dw]:
    print(ans)
    break
    
  if not new_VS:
    print(-1)
    break
    
  VS = set()
  for x, y in new_VS:
    for dx in range(-2, 3):
      for dy in range(-2, 3):
        x_ = x + dx
        y_ = y + dy
        if usedss[x_][y_]  == 1:
          continue
        VS.add((x_, y_))
        usedss[x_][y_] = 1
        
  ans += 1
  new_VS = set(VS)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
from itertools import product

H, W = map(int, input().split())
S = tuple(map(lambda x: int(x)+1, input().split()))
G = tuple(map(lambda x: int(x)+1, input().split()))
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i, j in product(range(-2, 3), repeat=2)
               if (i, j) not in [(0, 0)] + walk]
LW = len(warp)
qu = deque([(S[0], S[1], 0)])
qu_1 = deque()
check[S[0]][S[1]] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        I, J = i+di, j+dj
        if maze[I][J] == '.' and check[I][J] > cost:
            check[I][J] = cost
            qu.appendleft((I, J, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for k in range(LW):
                di, dj = warp[k]
                I, J = i+di, j+dj
                if maze[I][J] == '.' and check[I][J] > cost + 1:
                    check[I][J] = cost + 1
                    qu.append((I, J, cost+1))

#print(check)
if check[G[0]][G[1]] == INF:
    print(-1)
else:
    print(check[G[0]][G[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_list = []

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

s_list[ch - 1][cw - 1] = 0
checked_list =[[[ch - 1, cw - 1]]]
step = 0

while 1:
    for now in checked_list[step]:
        if now[0] != 0 and s_list[now[0] - 1][now[1]] == ".":
            s_list[now[0] - 1][now[1]] = step
            checked_list[step].append([now[0] - 1, now[1]])
        if now[0] != h - 1 and s_list[now[0] + 1][now[1]] == ".":
            s_list[now[0] + 1][now[1]] = step
            checked_list[step].append([now[0] + 1, now[1]])
        if now[1] != 0 and s_list[now[0]][now[1] - 1] == ".":
            s_list[now[0]][now[1] - 1] = step
            checked_list[step].append([now[0], now[1] - 1])
        if now[1] != w - 1 and s_list[now[0]][now[1] + 1] == ".":
            s_list[now[0]][now[1] + 1] = step
            checked_list[step].append([now[0], now[1] + 1])

    if [dh - 1, dw - 1] in checked_list[step]:
        break

    checked_list.append([])

    for now in checked_list[step]:
        for i in range(-2, 3):
            for j in range(-2, 3):
                if now[0] + i < 0 or now[0] + i > h - 1 or now[1] + j < 0 or now[1] + j > w - 1:
                    continue
                elif s_list[now[0] + i][now[1] + j] == ".":
                    s_list[now[0] + i][now[1] + j] = step + 1
                    checked_list[step + 1].append([now[0] + i, now[1] + j])

    step += 1
    if [dh - 1, dw - 1] in checked_list[step]:
        break
    elif len(checked_list[step]) == 0:
        step = -1
        break

print(step)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
from itertools import product

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i, j in product(range(-2, 3), repeat=2)
               if (i, j) not in [(0, 0)] + walk]
LW = len(warp)
qu = deque([(Si+1, Sj+1, 0)])
qu_1 = deque()
check[Si+1][Sj+1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        I, J = i+di, j+dj
        if maze[I][J] == '.' and check[I][J] > cost:
            check[I][J] = cost
            qu.appendleft((I, J, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for k in range(LW):
                di, dj = warp[k]
                I, J = i+di, j+dj
                if maze[I][J] == '.' and check[I][J] > cost + 1:
                    check[I][J] = cost + 1
                    qu.append((I, J, cost+1))

#print(check)
if check[Gi+1][Gj+1] == INF:
    print(-1)
else:
    print(check[Gi+1][Gj+1])

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        if i+1<h:
            if s[i+1][j]==".":
                g[i][j].append((i+1,j))        
            else:
                wpg2[i][j]=1
        if 0<=i-1:
            if s[i-1][j]==".":
                g[i][j].append((i-1,j))        
            else:
                wpg2[i][j]=1
        if j+1<w:
            if s[i][j+1]==".":
                g[i][j].append((i,j+1))        
            else:
                wpg2[i][j]=1
        if 0<=j-1:
            if s[i][j-1]==".":
                g[i][j].append((i,j-1))        
            else:
                wpg2[i][j]=1
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
from itertools import product

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i, j in product(range(-2, 3), repeat=2)
               if (i, j) not in [(0, 0)] + walk]
LW = len(warp)
qu = deque([(Si+1, Sj+1, 0)])
qu_1 = deque()
check[Si+1][Sj+1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if maze[i+di][j+dj] == '#' or check[i+di][j+dj] <= cost:
            continue
        check[i+di][j+dj] = cost
        qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for k in range(LW):
                di, dj = warp[k]
                if maze[i+di][j+dj] == '#' or check[i+di][j+dj] <= cost + 1:
                    continue
                check[i+di][j+dj] = cost + 1
                qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi+1][Gj+1] == INF:
    print(-1)
else:
    print(check[Gi+1][Gj+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


def exists(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    elif S[h][w] == "#":
        return False
    else:
        return True


costs = [[-1] * W for _ in range(H)]
passed = [[0] * W for _ in range(H)]
costs[C_h - 1][C_w - 1] = 0
d = deque()
d.append((C_h - 1, C_w - 1))
while d:
    h, w = d.popleft()
    c = costs[h][w]
    if passed[h][w] == 1:
        continue
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if exists(hh, ww):
            if (hh, ww) in d:
                d.remove((hh, ww))
            costs[hh][ww] = c
            d.appendleft((hh, ww))
    for i in range(5):
        for j in range(5):
            hh = h + i - 2
            ww = w + j - 2
            if exists(hh, ww):
                if costs[hh][ww] == -1:
                    costs[hh][ww] = c + 1
                    d.append((hh, ww))
    passed[h][w] = 1
print(costs[D_h - 1][D_w - 1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
from itertools import product

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i, j in product(range(-2, 3), repeat=2)
               if (i, j) not in [(0, 0)] + walk]
LW = len(warp)
qu = deque([(Si+1, Sj+1, 0)])
qu_1 = deque()
check[Si+1][Sj+1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if maze[i+di][j+dj] == '.' and check[i+di][j+dj] > cost:
            check[i+di][j+dj] = cost
            qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for k in range(LW):
                di, dj = warp[k]
                if maze[i+di][j+dj] == '.' and check[i+di][j+dj] > cost + 1:
                    check[i+di][j+dj] = cost + 1
                    qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi+1][Gj+1] == INF:
    print(-1)
else:
    print(check[Gi+1][Gj+1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
qu = deque([(Si+1, Sj+1, 0)])
qu_1 = deque()
check[Si+1][Sj+1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if maze[i+di][j+dj] == '.' and check[i+di][j+dj] > cost:
            check[i+di][j+dj] = cost
            qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if maze[i+di][j+dj] == '.' and check[i+di][j+dj] > cost + 1:
                        check[i+di][j+dj] = cost + 1
                        qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi+1][Gj+1] == float(INF):
    print(-1)
else:
    print(check[Gi+1][Gj+1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
gy, gx = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)] 
from collections import deque

def bfs(maze, seen, sy, sx, gy, gx):
    queue = deque()
    queue.append([sy, sx, 0])
    while queue:
        y, x, c = queue.popleft()
        if seen[y][x] > -1:
            continue
        seen[y][x] = c
        if seen[gy][gx] > -1:
            return c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):   
                    dy = y + i
                    dx = x + j
                    if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                        continue
                    if maze[dy][dx] == '#':
                        continue
                    queue.appendleft([dy, dx, c])
                dy = y + i
                dx = x + j
                if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                    continue
                if maze[dy][dx] == '#':
                    continue
                queue.append([dy, dx, seen[y][x] + 1])
    return -1

print(bfs(maze, seen, sy, sx, gy, gx))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
top_dummy = ['#' * (W+4)] * 2 
bottom_dummy = ['#' * (W+4)] * 2 
maze = top_dummy + [f'##{input()}##' for _ in range(H)] + bottom_dummy
#print(maze)

INF = float('inf')
check = [[INF for i in range(W+4)] for j in range(H+4)]
walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
qu = deque([(Si+1, Sj+1, 0)])
qu_1 = deque()
check[Si+1][Sj+1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if not maze[i+di][j+dj] == '#':
            if check[i+di][j+dj] > cost:
                check[i+di][j+dj] = cost
                qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if not maze[i+di][j+dj] == '#':
                        if check[i+di][j+dj] > cost + 1:
                            check[i+di][j+dj] = cost + 1
                            qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi+1][Gj+1] == float(INF):
    print(-1)
else:
    print(check[Gi+1][Gj+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


def exists(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    elif S[h][w] == "#":
        return False
    else:
        return True


costs = -1 * np.ones((H, W), dtype=np.int)
passed = np.zeros((H, W), dtype=np.int)
costs[C_h - 1, C_w - 1] = 0
d = deque()
d.append((C_h - 1, C_w - 1))
while d:
    h, w = d.popleft()
    c = costs[h, w]
    if passed[h, w] == 1:
        continue
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if exists(hh, ww):
            if (hh, ww) in d:
                d.remove((hh, ww))
            costs[hh, ww] = c
            d.appendleft((hh, ww))
    for i in range(5):
        for j in range(5):
            hh = h + i - 2
            ww = w + j - 2
            if exists(hh, ww):
                if costs[hh, ww] == -1:
                    costs[hh, ww] = c + 1
                    d.append((hh, ww))
    passed[h, w] = 1
print(costs[D_h - 1, D_w - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

#def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
#        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
#                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
#        g[i][j]=ggg        
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h or 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        while q:
            h, w = q.popleft()
            if done[h][w] == -1 and S[h][w] == ".":
                done[h][w] = num
                for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nh, nw = h+dh, w+dw
                    if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                        continue
                    if done[nh][nw] == -1:
                        q.append((nh, nw))
        num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in hh:
    for j in ww:
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
                g[i][j].append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
                
for i in hh:
    for j in ww:
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)