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:
#写経
#16133681

import sys
input = lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1
cw-=1
stack=[(ch,cw)]
dh,dw=map(int,input().split())
dh-=1
dw-=1
b=[w*[-1]for _ in range(h)]
for i in range(h):
  for j,t in enumerate(input()):
    if t=="#":b[i][j]=10**10
b[ch][cw]=0
dxy=((-1,0),(1,0),(0,-1),(0,1))
for ans in range(10**6):
  for x,y in stack:
    b[x][y]=1
    if x==dh and y==dw:
      print(ans)
      exit()
    for dx,dy in dxy:
      if 0<=x+dx<h and 0<=y+dy<w:
        if b[x+dx][y+dy]==10**10:continue
        if b[x+dx][y+dy]==-1:
          stack.append((x+dx,y+dy))
          b[x+dx][y+dy]=1
  stackk=[]
  for x,y in stack:
    for xx in range(max(0,x-2),min(h,x+3)):
      for yy in range(max(0,y-2),min(w,y+3)):
        if b[xx][yy]==-1:stackk.append((xx,yy))
  stack=stackk
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10 ** 12

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                self.queue.append(next_move)
                self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw, dist[ch][cw]))
#上下左右移動
mx = [-1,+1, 0, 0]
my = [ 0, 0,-1,+1]

#01-BFS
while dq:
    i, j, d = dq.popleft()
    #コスト0で追加されたキューが，コスト1として追加されたとき評価しない
    if d > dist[i][j]:
        continue
    #歩いて移動
    d = dist[i][j]
    for n in range(4):
        i2 = i + mx[n]
        j2 = j + my[n]
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2,dist[i2][j2]))

    #ワープ移動
    d += 1
    eju = -2
    for ei in range(-2,3):
        i2 = i+ei
        #範囲外へは進めない
        if i2 < 0:
            continue
        if h <= i2:
            break
        for ej in range(eju,3):
            j2 = j+ej
            #範囲外へは進めない
            if j2 < 0:
                eju = ej+1
                continue
            if w <= j2:
                break
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2,dist[i2][j2]))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw, dist[ch][cw]))
#上下左右移動
mx = [-1,+1, 0, 0]
my = [ 0, 0,-1,+1]

#01-BFS
while dq:
    i, j, d = dq.popleft()
    #コスト0で追加されたキューが，コスト1として追加されたとき評価しない
    if d > dist[i][j]:
        continue
    #歩いて移動
    d = dist[i][j]
    for n in range(4):
        i2 = i + mx[n]
        j2 = j + my[n]
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2,dist[i2][j2]))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        i2 = i+ei
        #範囲外へは進めない
        if i2 < 0:
            continue
        if h <= i2:
            break
        for ej in range(-2,3):
            j2 = j+ej
            #範囲外へは進めない
            if j2 < 0:
                continue
            if w <= j2:
                break
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2,dist[i2][j2]))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw, dist[ch][cw]))

#01-BFS
while dq:
    i, j, d = dq.popleft()
    #コスト0で追加されたキューが，コスト1として追加されたとき評価しない
    if d > dist[i][j]:
        continue
    #歩いて移動
    d = dist[i][j]
    for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2,dist[i2][j2]))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        i2 = i+ei
        #範囲外へは進めない
        if not 0 <= i2 < h:
            continue
        for ej in range(-2,3):
            j2 = j+ej
            #範囲外へは進めない
            if not 0 <= j2 < w:
                continue
            #同じ地点へのワープは無視
            if (i2,j2) == (i,j):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2,dist[i2][j2]))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

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=[input() for i in range(h)]

#for i in range(h):
#  s_=list(input())
#  s.append(s_)
#幅優先探索
from collections import deque
q=deque([(ch-1,cw-1)])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
X=((-1,0),(1,0),(0,1),(0,-1))
Y=((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,1),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2))
while len(q)>0:
  y,x=q.popleft()
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft((ny,nx))
  for dy,dx in Y:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]+1
        q.append((ny,nx))

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
#入力
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[]
for i in range(h):
  s_=list(input())
  s.append(s_)
#幅優先探索
from collections import deque
q=deque([(ch-1,cw-1)])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
X=((-1,0),(1,0),(0,1),(0,-1))
Y=((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,1),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2))
while len(q)>0:
  y,x=q.popleft()
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft((ny,nx))
  for dy,dx in Y:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]+1
        q.append((ny,nx))

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
#入力
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[]
for i in range(h):
  s_=list(input())
  s.append(s_)
#幅優先探索
from collections import deque
q=deque([(ch-1,cw-1)])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
while len(q)>0:
  y,x=q.popleft()
  X=((-1,0),(1,0),(0,1),(0,-1))
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft((ny,nx))
  Y=(-2,-1,0,1,2)
  for dx in Y:
    for dy in Y:
      if not(dx==0 and dy==0):
        if (dy,dx) not in X:
          nx=x+dx
          ny=y+dy
          if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
            if used[ny][nx]>used[y][x]:
              used[ny][nx]=used[y][x]+1
              q.append((ny,nx))

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw))

#01-BFS
while dq:
    i, j = dq.popleft()
    #歩いて移動
    d = dist[i][j]
    for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        i2 = i+ei
        #範囲外へは進めない
        if not 0 <= i2 < h:
            continue
        for ej in range(-2,3):
            j2 = j+ej
            #範囲外へは進めない
            if not 0 <= j2 < w:
                continue
            #同じ地点へのワープは無視
            if (i2,j2) == (i,j):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

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=[]
for i in range(h):
  s_=list(input())
  s.append(s_)
#幅優先探索
from collections import deque
q=deque([[ch-1,cw-1]])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
while len(q)>0:
  y,x=q.popleft()
  X=[[-1,0],[1,0],[0,1],[0,-1]]
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft([ny,nx])
  Y=[-2,-1,0,1,2]
  for dx in Y:
    for dy in Y:
      if not(dx==0 and dy==0):
        if [dy,dx] not in X:
          nx=x+dx
          ny=y+dy
          if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
            if used[ny][nx]>used[y][x]:
              used[ny][nx]=used[y][x]+1
              q.append([ny,nx])

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw))

#01-BFS
while dq:
    i, j = dq.popleft()
    #歩いて移動
    d = dist[i][j]
    for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
        #範囲外へは進めない
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        for ej in range(-2,3):
            i2 = i+ei
            j2 = j+ej
            #範囲外へは進めない
            if not (0 <= i2 < h and 0 <= j2 < w):
                continue
            #同じ地点へのワープは無視
            if (i2,j2) == (i,j):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw))

#01-BFS
while len(dq):
    i, j = dq.popleft()
    #歩いて移動
    d = dist[i][j]
    for i2, j2 in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):
        if not (0 <= i2 < h and 0 <= j2 < w):
            continue
        #壁へは進めない
        if s[i2][j2] == '#':
            continue
        #距離が小さければ更新
        if d < dist[i2][j2]:
            dist[i2][j2] = d
            #キューの先頭に追加
            dq.appendleft((i2,j2))

    #ワープ移動
    d += 1
    for ei in range(-2,3):
        for ej in range(-2,3):
            i2 = i+ei
            j2 = j+ej
            if not (0 <= i2 < h and 0 <= j2 < w):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue
            #距離が小さければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #キューの末尾に追加
                dq.append((i2, j2))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

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(input()) for _ in range(H)]
 
INF = H * W
 
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
 
# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True
 
num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0
 
# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0
 
# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        # next_  = [
        #     (h[0] + 1, h[1], 0),
        #     (h[0] - 1, h[1], 0),
        #     (h[0], h[1] + 1, 0),
        #     (h[0], h[1] - 1, 0),]
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp
 
        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]
 
        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))
 
    num_warp += 1
 
    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))
 
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0
arrived = [[0 for i in range(W)] for j in range(H)]
arrived[C_h-1][C_w-1] = 1

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    if cost > dist[h][w] and dist[h][w] != -1:
        continue
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
            arrived[h+dh][w+dw] = True
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    if cost > dist[h][w] and dist[h][w] != -1:
        continue
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-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 = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-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 = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-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 = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost) and dist[h+dh][w+dw] > cost:
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1) and dist[h+dh][w+dw] > cost + 1:
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-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 = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

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

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = min(dist[h+dh][w+dw], cost)
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] = min(dist[h+dh][w+dw], cost+1)

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
c = tuple(int(x)+1 for x in input().split())
d = [int(x)+1 for x in input().split()]
maze = [[-1] * (W+4), [-1] * (W+4)]

for i in range(H):
    temp = []
    s0 = input()
    s0 = '11' + s0.replace('.', '0').replace('#', '1') + '11'
    for j, s in enumerate(s0):
        temp.append(-int(s))
    maze.append(temp)
maze.append([-1] * (W+4))
maze.append([-1] * (W+4))

def check55(i, j):
    cset = {(ii, jj) for ii in range(i-2, i+3) for jj in range(j-2, j+3) if maze[ii][jj]==0}
    cset = cset - {(i-1, j), (i, j), (i+1, j), (i, j-1), (i, j+1)}
    return cset

def check(i, j, delta):
    if delta[0] != 0:
        ii = i + 3 * delta[0]
        cset = {(ii, jj) for jj in range(j-2, j+3) if maze[ii][jj]==0} 
    else:
        jj = j + 3 * delta[1]
        cset = {(ii, jj) for ii in range(i-2, i+3) if maze[ii][jj]==0}
    return cset

#bfs

k = 1
tempbfs = deque([[c[0], c[1], k]])
flag = 0
while tempbfs:
    if flag == 1:break
    p = tempbfs.popleft()

    #dfs
    if maze[p[0]][p[1]] != 0:continue
    maze[p[0]][p[1]] = p[2]
    if p[0] == d[0] and p[1] == d[1]:
        flag = 1
        k = p[2]
        break
    temp = [(p[0], p[1])]
    dset = set()
    while temp:
        p0 = temp.pop()
        for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            y = p0[0] + delta[0]
            x = p0[1] + delta[1]
            if maze[y][x] != 0: continue
            maze[y][x] = p[2]
            if y == d[0] and x == d[1]:
                flag = 1
                k = p[2]
                break
            temp.append((y, x))
            dset = dset | check(p0[0], p0[1], delta)

    if flag == 1: break
    for l in dset:
        if maze[l[0]][l[1]] == 0:
            tempbfs.append([l[0], l[1], p[2]+1])
    dset = check55(p[0], p[1])
    for l in dset:
        tempbfs.append([l[0], l[1], p[2]+1])

print(k - 1 if flag else -1)