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:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.append(input().rstrip('\n'))

d = [[10 ** 18 for i in range(w)] for j in range(h)]

stack = deque([[ch-1, cw-1, 0]])

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh][curw] <= cnt:
        continue
    else:
        d[curh][curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.':
            stack.append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh >= 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw >= 0 and nw < w and s[nh][nw] == '.':
                     stack.append([nh, nw, cnt+1])

# for item in d:
#     print(item)

if d[gh-1][gw-1] == 10 ** 18:
    print(-1)
else:
    print(d[gh-1][gw-1])

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

def search(cost, sx, sy):
    # ある地点からジャンプ無しで行ける範囲を探索

    que = deque()
    que.append((sx,sy))

    reached = []

    while que:
        x,y = que.popleft()

        # 訪れた場所リスト
        reached.append((x,y))

        if cost_map[y][x] <= cost:
            continue
        cost_map[y][x] = cost

        for x2, y2 in neighbors4(x,y):
            if x2<0 or x2>=w or y2<0 or y2>=h:
                continue
            if grid_s[y2][x2] == ".":
                que.append((x2, y2))
    
    return reached

def jump(cost, x, y):
    if cost >= cost_map[y][x]:
        return
    reached = search(cost, x, y)
    
    # ゴールに到達したらおわり
    if cost_map[dh][dw] != INF:
        print(cost_map[dh][dw])
        exit()
    
    # 1回ジャンプする
    for x,y in reached:
        for y2 in range(max(0, y-2), min(h, y+3)):
            for x2 in range(max(0, x-2), min(w, x+3)):
                if abs(x-x2) + abs(y-y2) < 2:
                    continue
                if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                    heappush(jump_heap, (cost+1, x2, y2))



def main():
    global h,w,dh,dw,grid_s,cost_map, jump_heap,INF
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w = get_nums_l()
    ch,cw = get_nums_l()
    dh,dw = get_nums_l()

    # 0-originに変換
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1

    grid_s = []
    for i in range(h):
        grid_s.append(input())
    
    cost_map = [[INF] * w for _ in range(h) ]

    jump_heap = [(0, cw, ch)]

    while jump_heap:
        cost, x, y = heappop(jump_heap)
        jump(cost, x, y)
    
    print(-1)

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:
      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

  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    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] == '.' and V[x][y]==0:
              part.append((x,y))
       
    ALL = list(set(part))
    Q = list(ALL)
    
    #print(temp,best)
    if (f1,f2) in ALL:
      print(count)
      break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    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 = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for i in range(h):
  s.append(input().strip())


o = set()
e = {(ch, cw)}

def walk(e):
  ne = set(e)
  def sub(xe):
    xxe = set()
    for nh, nw in xe:
      for mh, mw in [(nh+1, nw), (nh-1, nw), (nh, nw+1), (nh, nw-1)]:
        if (mh, mw) in o or (mh, mw) in ne:
          continue
        if mh < 0 or h <= mh or mw < 0 or w <= mw:
          continue
        if s[mh][mw] == '.':
          ne.add((mh, mw))
          xxe.add((mh, mw))
    return xxe
  while(e):
    e = sub(e)
  return ne

def warp(e):
  ne = set()
  for nh, nw in e:
    for i in range(-2, 3):
      for j in range(-2, 3):
        mh = nh + i
        mw = nw + j
        if i == j == 0 or (mh, mw) in o:
          continue
        if mh < 0 or h <= mh or mw < 0 or w <= mw:
          continue
        if s[mh][mw] == '.':
          ne.add((mh, mw))
  return ne

import sys

ww = 0

while(len(e) > 0):
  if (dh, dw) in e:
    print(ww)
    sys.exit()
  ne = walk(e)
  if (dh, dw) in ne:
    print(ww)
    sys.exit()
  o.update(e)
  e = ne
  ne = warp(e)
  ww += 1
  if (dh, dw) in ne:
    print(ww)
    sys.exit()
  o.update(e)
  e = ne
print('-1')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

move = [[0,1], [0,-1], [1,0], [-1,0]]

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

s =[[-1 for j in range(w+4)] for i in range(h+4)]
for i in range(h):
  a = input()
  for j in range(2, w+2):
    s[i+2][j] = w*h+1 if a[j-2]=='.' else -1

    
#for i in s:
#  print(i)


queue = deque([[ch,cw]])
s[ch][cw] = 0
while queue:
    now = queue.popleft()
    nows = s[now[0]][now[1]]
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] == -1):
        continue
      elif(s[nh][nw] > nows):
        s[nh][nw] = nows
        queue.append([nh, nw])
        
    for i in range(-2,3):
      for j in range(-2,3):
        nh, nw = now[0]+i, now[1]+j
        if(s[nh][nw] == -1):
          continue
        elif(s[nh][nw] > nows+1):
          s[nh][nw] = nows+1
          queue.append([nh, nw])
        
      
#print()
#for i in s:
#  print(i)

if(s[dh][dw] == w*h+1):
  print(-1)
else:
  print(s[dh][dw])

Submission status: Time Limit Exceeded

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
h,w=map(int, input().split())
start=list(map(int, input().split()))
goal=list(map(int, input().split()))
m = [list(input().rstrip("\n")) for i in range(h)]
start[0]-=1
start[1]-=1
goal[0]-=1
goal[1]-=1
#print(m,start,goal,h,w)

def bfs(h, w, m, start, goal):
    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    canwarp=True
    cnt=0
    while canwarp:
        #print(goal)
        mimi=100000
        k=0
        trace=[]
        t=[]
        while not a.empty():
            hh, ww = map(int, a.get())
            #print(hh,ww)
            d[hh][ww]=1
            if hh == goal[0] and ww==goal[1]:
                flg = True
                break
            for i in range(4):
                nx, ny = ww+dx[i], hh+dy[i]
                if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == 0:
                    if m[ny][nx] != "#":
                        a.put([ny, nx])
                        d[ny][nx] = 1
                    else:
                        trace.append([hh,ww])
                        d[ny][nx] = 1

        if flg==True:
            break

        #mimi=100000
        #k=0
        """
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                    t=[hh+i,ww+j]
                    mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                    k=1"""
        #print(t)
        for item in trace:
            for i in range(-2,3):
                for j in range(-2,3):
                    if 0 <= item[0]+i < h and 0 <= item[1]+j < w and m[item[0]+i][item[1]+j]=="." and d[item[0]+i][item[1]+j] == 0:
                        t.append([item[0]+i,item[1]+j])
                        k=1
        if k>0:
            for i in range(len(t)):
                a.put(t[i])
            cnt+=1
        else:
            canwarp=False
            break

    return cnt if flg else -1

print(bfs(h, w, m, start, goal))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)
G = nx.Graph()
path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    # path[h*W + w].append((0, new_h*W + new_w))
                    # path[new_h*W + new_w].append((0, h*W + w))
                    G.add_edge(h*W + w, new_h*W + new_w, weight=0)
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        # path[h*W + w].append((1, new_h*W + new_w))
                        # path[new_h*W + new_w].append((1, h*W + w))
                        G.add_edge(h*W + w, new_h*W + new_w, weight=1)
            for dy, dx in MAGIC:
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    # path[h*W + w].append((1, new_h*W + new_w))
                    # path[new_h*W + new_w].append((1, h*W + w))
                    G.add_edge(h*W + w, new_h*W + new_w, weight=1)

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
# dist = dijkstra(path, N, c_h * W + c_w)
# print(dist[d_h*W+d_w])
try:
    length = nx.dijkstra_path_length(G, c_h * W + c_w, d_h*W+d_w)
    print(length)
except:
    print(-1)
    exit()

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""

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()) #ゴール
#Ch-=1; Cw-=1; Dh-=1; Dw-=1
S=[]
S.append('#'*(W+2))
for i in range(H):
    S.append('#'+input()+'#')
S.append('#'*(W+2))

H+=2; W+=2
ans=0


done=[[0 for i in range(W)] for j in range(H)]
kin4=([1,0],[-1,0],[0,1],[0,-1])
kin8=([1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1])
MAP=S

def dfs(y,x,n):
    if MAP[y][x]=='#' or done[y][x]:
        return
    else:
        done[y][x]=n
        for i,j in kin4:
            if not(y+i<0 or y+i>H-1 or x+j<0 or x+j>W-1):
                dfs(y+i,x+j,n)

def search(M,D):
    b,a=-1,-1
    for i in range(H):
        for j in range(W):
            if D[i][j]==False and M[i][j]=='.':
                b,a=i,j
                return [b,a]
    return [b,a]


cnt=1
while True:
    #print(cnt)
    s=search(MAP,done)
    Y,X=s[0],s[1]
    #print(s)
    if Y==-1 and X==-1:
        break
    dfs(Y,X,cnt)
    #print(done)
    cnt+=1

#print(done)

N=cnt-1

graph=[[0 for i in range(N+1)] for j in range(N+1)]

dx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
dy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]

for i in range(H):
    for j in range(W):
        c=done[i][j]
        if c==0:
            continue
        for h in range(25):
            if 0<=i+dx[h]<H and 0<=j+dy[h]<W:
                c2=done[i+dx[h]][j+dy[h]]
                if c!=c2 and c2!=0:
                    graph[c][c2]=1
                    graph[c2][c]=1

#print(graph)       

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n
    used=[False]*n
    d[s]=0
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1):
               v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
               break
        used[v]=True
               
        for j in range(n):
               d[j]=min(d[j],d[v]+cost[v][j])
    return d

cost = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
w=0
for i in range(N+1):
    for j in range(N+1):
        if graph[i][j]:
            cost[i][j]=1
            w+=1
start=done[Ch][Cw]
goal=done[Dh][Dw]

ds=dijkstra(start,N+1,w,cost)
#print(ds)
#print(ds[goal])

if ds[goal]>10000:
    print(-1)
else:
    print(ds[goal])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, 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

maze = []
for _ in range(H):
    row = list(input())
    maze.append(row)

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#":
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))
    if isFind:
        break

if not isFind:
    print(-1)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        vec5 += [(i,j)]

q = [(0, (ch, cw))]
heapq.heapify(q)
while len(q) > 0:
    c, (i,j) = heapq.heappop(q)
    if s[i][j] != '.' and s[i][j] != '#' and s[i][j] <= c:
        continue
    s[i][j] = c
    for v in vec:
        ii = i + v[0]
        jj = j + v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c, (ii, jj)))
    for v in vec5:
        ii = i+v[0]
        jj = j+v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c+1, (ii, jj)))
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque

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

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

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

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

cost = 0

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
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] and not visited[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())
    D = [0] * ((H + 4) * (W + 4))
    for i in range(H):
        S = input().strip()
        for j in range(W):
            D[(i + 2) * (W + 4) + (j + 2)] = 1 if S[j] == ord(b".") else 0
    # print(D)
    # for i in range(H + 4):
    #     print(D[i * (H + 4): i * (H + 4) + (W + 4)])
    # 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:
h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
s = [list(input()) for _ in range(h)]

c[0] -= 1
c[1] -= 1
d[0] -= 1
d[1] -= 1

stack = []
q = [[c, 0]]
ans = -1
dt = [[h*w for _ in range(w)] for _ in range(h)]
dt[c[0]][c[1]] = 0
while q:
  #print("q: {}".format(q))
  pos,time = q.pop(0)
  stack = [pos]
  while stack:
    #print("stack: {}".format(stack))
    pos = stack.pop()
    if pos[0] == d[0] and pos[1] == d[1]:
      ans = time
      q = []
      break
    for i in range(-2,3):
      for j in range(-2,3):
        if i==0 and j==0:
          continue
        elif (i==0 and j >=-1 and j <= 1) or (j==0 and i >=-1 and i <= 1):
          if (pos[0]+i>-1 and pos[0]+i<h and pos[1]+j>-1 and pos[1]+j<w
              and s[pos[0]+i][pos[1]+j]=="."):
            stack.append([pos[0]+i, pos[1]+j])
            s[pos[0]+i][pos[1]+j] = "#"
            dt[pos[0]+i][pos[1]+j] = time
        else:
          if (pos[0]+i>-1 and pos[0]+i<h and pos[1]+j>-1 and pos[1]+j<w
              and s[pos[0]+i][pos[1]+j]=="." and dt[pos[0]+i][pos[1]+j]>time+1):
            q.append([[pos[0]+i, pos[1]+j],time+1])
            dt[pos[0]+i][pos[1]+j] = time+1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

h, w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
S = [list(input()) for _ in range(h)]
Dist = [[float('inf')] * w for _ in range(h)]
ff_direct = []
for i in [-2, -1, 0, 1, 2]:
    for j in [-2, -1, 0, 1, 2]:
        if not (i==0 and j==0):
            ff_direct.append((i, j))
four_direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_search(px, py, di):
    if px < 0 or py < 0 or px >= h or py >= w:
        return False
    elif S[px][py] == '#' or Dist[px][py] <= di:
        return False
    else:
        return True
    
def dfs(px, py, di):
    Dist[px][py] = di
    for dx, dy in ff_direct:
        nx = px + dx
        ny = py + dy
        if is_search(nx, ny, di):
            if (dx, dy) in four_direct:
                dfs(nx, ny, di)
            else:
                dfs(nx, ny, di+1)
dfs(c[0]-1, c[1]-1, 0)
dist = Dist[d[0]-1][d[1]-1]
if dist <= 10 ** 6:
    print(dist)
else:
    print(-1)