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())
S = [list(input()) for _ in range(H)]

INF = H * W

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(0) # 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 n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    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:
            queue.append((magic[0],magic[1]))

print(-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(input()) for _ in range(H)]

INF = H * W

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(0) # here 
        num_step[h[0]][h[1]] = num_warp
        # ゴールチェック
        if num_step[Dh - 1][Dw - 1] != INF:
            print(num_step[Dh - 1][Dw - 1])
            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 n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    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:
            queue.append((magic[0],magic[1]))

print(-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(input()) for _ in range(H)]

INF = H * W

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(0) # here 
        num_step[h[0]][h[1]] = num_warp
        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 n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] > num_warp:
                    # print(S[h[0] + y][h[1] + x])
                    # print((h[0] + y, h[1] + x))
                    magic_tiles.append((h[0] + y, h[1] + x))
    
    # ゴールチェック
    if num_step[Dh - 1][Dw - 1] != INF:
        print(num_step[Dh - 1][Dw - 1])
        exit()

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            queue.append((magic[0],magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))

d = [[-1 for i in range(W)] for j in range(H)]

Q = deque([[Ch -1, Cw - 1, 0]])

while len(Q) != 0:
    x, y, cnt = Q.popleft()

    if d[x][y] != -1:
        continue

    d[x][y] = cnt

    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if abs(tx) + abs(ty) == 1:
                    Q.appendleft([nx, ny, cnt])
                elif abs(tx) + abs(ty) >= 2:
                    Q.append([nx, ny, cnt + 1])

print(d[Dh - 1][Dw - 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())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

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

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    if d>cost[x][y]:
        continue
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

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

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    if d>cost[x][y]:
        continue
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

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

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
stack = deque([[Ch-1,Cw-1]])

for h in range(H):
  maze.append(list(input()))
  vis.append([1e9]*W)

vis[Ch-1][Cw-1] = 0

while stack:
  p = stack.popleft()
  a = p[0]
  b = p[1]
  dis = vis[a][b]
  
  for i in range(-2,3):
    ai=a+i
    if not(0<= ai <H):
      continue
    for j in range(-2,3):
      bj=b+j
      s=i*i+j*j
      if s==0:
        continue
        
      if 0<= bj <W:
        if maze[ai][bj]=="#":
          continue
          
        if s==1:
          if vis[ai][bj]<=dis:
            continue
          vis[ai][bj] = dis
          stack.appendleft([ai,bj])
          
        elif s > 1:
          if vis[ai][bj] <= dis+1:
            continue
          vis[ai][bj] = dis+1
          stack.append([ai,bj])
          
if vis[Dh-1][Dw-1]!=1e9:
  print(vis[Dh-1][Dw-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
stack = deque([[Ch-1,Cw-1]])

for h in range(H):
  maze.append(list(input()))
  vis.append([1e9]*W)

vis[Ch-1][Cw-1] = 0

while stack:
  p = stack.popleft()
  a = p[0]
  b = p[1]
  dis = vis[a][b]
  
  for i in range(-2,3):
    for j in range(-2,3):
      if 0<= a+i <H and 0<= b+j <W:
        if maze[a+i][b+j]=="#":
          continue
          
        if 0<i*i+j*j<=1:
          if vis[a+i][b+j]<=dis:
            continue
          vis[a+i][b+j] = dis
          stack.appendleft([a+i,b+j])
          
        elif i*i+j*j > 1:
          if vis[a+i][b+j] <= dis+1:
            continue
          vis[a+i][b+j] = dis+1
          stack.append([a+i,b+j])
          
if vis[Dh-1][Dw-1]!=1e9:
  print(vis[Dh-1][Dw-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
ans = -1
stack = deque([[Ch-1,Cw-1]])

def privis():
  for v in vis:
    print(v)
  print("/n")

for h in range(H):
  maze.append(list(input()))
  vis.append([1e9]*W)

vis[Ch-1][Cw-1] = 0

while stack:
  p = stack.popleft()
  dis = vis[p[0]][p[1]]
  for i in range(-2,3):
    for j in range(-2,3):
      if 0<= p[0]+i <H and 0<= p[1]+j <W:
        if maze[p[0]+i][p[1]+j]=="#":
          continue
        if vis[p[0]+i][p[1]+j]>dis:
          if 0<i*i+j*j<=1: #
            vis[p[0]+i][p[1]+j] = dis
            if [p[0]+i,p[1]+j] in stack:
              stack.remove([p[0]+i,p[1]+j])
            stack.appendleft([p[0]+i,p[1]+j])
          elif i*i+j*j > 1:
            if [p[0]+i,p[1]+j] in stack:
              continue
            vis[p[0]+i][p[1]+j] = dis+1
            stack.append([p[0]+i,p[1]+j])
  #print(stack)
if vis[Dh-1][Dw-1]!=1e9:
  ans = vis[Dh-1][Dw-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
ans = -1
stack = deque([[Ch-1,Cw-1]])

def privis():
  for v in vis:
    print(v)
  print("/n")

for h in range(H):
  maze.append(list(input()))
  vis.append([1e9]*W)

vis[Ch-1][Cw-1] = 0

while stack: #0cost
  p = stack.popleft()
  if p == [Dh-1,Dw-1]:
    break
  dis = vis[p[0]][p[1]]
  for i in range(-2,3):
    for j in range(-2,3):
      if 0<= p[0]+i <H and 0<= p[1]+j <W:
        if maze[p[0]+i][p[1]+j]==".":
          if vis[p[0]+i][p[1]+j]>dis:
            if 0<i*i+j*j<=1:
              vis[p[0]+i][p[1]+j] = dis
              stack.appendleft([p[0]+i,p[1]+j])
            elif i*i+j*j > 1:
              if [p[0]+i,p[1]+j] in stack:
                continue
              vis[p[0]+i][p[1]+j] = dis+1
              stack.append([p[0]+i,p[1]+j])
              
if vis[Dh-1][Dw-1]!=1e9:
  ans = vis[Dh-1][Dw-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
01BFS: ステップ数が多ければ後ろに持っていく
"""
from collections import deque
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = [list(input()) for _ in range(H)]

que = deque([(Ch-1,Cw-1,0)])
adjectns = [(1,0),(0,1),(-1,0),(0,-1)]
for _ in range(100000000):
    if not que:
        break
    h,w,step = que.popleft()
    if h == Dh-1 and w == Dw-1:
        print(step)
        exit()
    else:
        if maze[h][w] == ".":
            maze[h][w] = step
            for a,b in adjectns:
                x = h + a
                y = w + b
                if 0<=x<H and 0<=y<W:
                    que.appendleft((x,y,step))
            for i in range(-2,3):
                for j in range(-2,3):
                    x = h+i
                    y = w+j
                    if 0<=x<H and 0<=y<W:
                        que.append((x,y,step+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
"""
01BFS: ステップ数が多ければ後ろに持っていく
"""
from collections import deque
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = [list(input()) for _ in range(H)]

que = deque([(Ch-1,Cw-1,0)])
adjectns = [(1,0),(0,1),(-1,0),(0,-1)]
while que:
    h,w,step = que.popleft()
    if h == Dh-1 and w == Dw-1:
        print(step)
        exit()
    else:
        if maze[h][w] == ".":
            maze[h][w] = step
            for a,b in adjectns:
                x = h + a
                y = w + b
                if 0<=x<H and 0<=y<W:
                    que.appendleft((x,y,step))
            for i in range(-2,3):
                for j in range(-2,3):
                    x = h+i
                    y = w+j
                    if 0<=x<H and 0<=y<W:
                        que.append((x,y,step+1))
print(-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())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

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

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
can = []
stack = [[Ch-1,Cw-1]]
flag = True
for h in range(H):
  maze.append(list(input()))
  vis.append([-1]*W)
vis[Ch-1][Cw-1] = 0

while flag:
  canN=[]
  previs = copy.deepcopy(vis)
  while stack: #0cost
    p = stack.pop()
    canN.append(p)
    
    for i in [-1,0,1]:
      for j in [-1,0,1]:
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j==1:
          if maze[p[0]+i][p[1]+j]==".":
            if vis[p[0]+i][p[1]+j]==-1 or vis[p[0]+i][p[1]+j]>vis[p[0]][p[1]]:
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]
              stack.append([p[0]+i,p[1]+j])
  can.append(canN)
  #print(vis)
  
  while canN:
    p = canN.pop()
    for i in range(-2,3):
      for j in range(-2,3):
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j>1:
          if maze[p[0]+i][p[1]+j]==".":
            if vis[p[0]+i][p[1]+j]==-1 or vis[p[0]+i][p[1]+j]>vis[p[0]][p[1]]:
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]+1
              stack.append([p[0]+i,p[1]+j])
  #print(vis)
  if previs==vis:
    print(vis[Dh-1][Dw-1])
    flag=False

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
can = []
stack = [[Ch-1,Cw-1]]
flag = True
for h in range(H):
  maze.append(list(input()))
  vis.append([-1]*W)
vis[Ch-1][Cw-1] = 0

while flag:
  canN=[]
  previs = copy.deepcopy(vis)
  while stack: #0cost
    p = stack.pop()
    canN.append(p)
    
    for i in [-1,0,1]:
      for j in [-1,0,1]:
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j==1:
          if maze[p[0]+i][p[1]+j]==".":
            if vis[p[0]+i][p[1]+j]==-1 or vis[p[0]+i][p[1]+j]>vis[p[0]][p[1]]:
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]
              stack.append([p[0]+i,p[1]+j])
  can.append(canN)
  #print(vis)
  
  while canN:
    p = canN.pop()
    for i in range(-2,3):
      for j in range(-2,3):
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j>1:
          if maze[p[0]+i][p[1]+j]==".":
            if vis[p[0]+i][p[1]+j]==-1 :
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]+1
              stack.append([p[0]+i,p[1]+j])
  #print(vis)
  if previs==vis:
    print(vis[Dh-1][Dw-1])
    flag=False

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

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

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]

queue = deque()

INF=10**12
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]

queue = deque()

INF=10**12
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0] + dxdy]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
c = [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))

k = 0
for i in range(2,H+2):
    for j in range(2, W+2):
        if maze[i][j] != 0: continue
        k += 1
        maze[i][j] = k
        temp = [[i, j]]
        
        while temp:
            p = temp.pop()
            for dd in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if maze[p[0] + dd[0]][p[1] + dd[1]] == 0:
                    temp.append([p[0] + dd[0], p[1] + dd[1]])
                    maze[p[0] + dd[0]][p[1] + dd[1]] = k
visited = [0] * k
lst = [set() for _ in range(k)]
for i in range(2, H+2):
    for j in range(2, W+2):
        p = maze[i][j]
        aset = set()
        if p == -1: continue
        for k in range(-2, 3):
            aset = aset | set(maze[i+k][j-2: j+3])
        for k in aset - {p, -1}:
            lst[p-1].add(k-1)
            lst[k-1].add(p-1)
stt = maze[c[0]][c[1]] - 1
gl = maze[d[0]][d[1]] - 1
if stt == gl: ans = 0
else:
    dq = deque([[stt, 0]])
    visited[stt] = 1
    ans = -1
    while dq:
        p = dq.popleft()
        for q in lst[p[0]]:
            if visited[q] == 1:continue
            if q == gl:
                ans = p[1] + 1
                break
            else:
                dq.append([q, p[1]+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

# 入力
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))

# コストをまとめる表
cost = [[float("inf")] * W for i in range(H)]

def bfs(que, c):
    # 幅優先探索を用いて、位置(init_x, init_y)から追加コストなしで辿り着けるマスを列挙

    next_que = deque([])

    while que:

        # キューの先頭を取り出す
        x, y = que.popleft()
        cost[x][y] = c

        # next_que に含まれる点なら除く
        if (x,y) in next_que:
            next_que.remove((x,y))

        # 取り出してきたキューがゴールなら探索をやめる
        if (x, y) == (D_h-1, D_w-1):
            return True, next_que

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

        # 現在地から移動Aで到達可能で未探索の点をキューに追加
        # 移動4方向をループ
        for dx, dy in moveA_vector:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf"):
                que.append((nx, ny))
                # cost[nx][ny] = c この処理は先頭でやる

        # 現在地から移動Bで到達可能で未探索の点を次のコストのキューに追加
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) not in moveA_vector:  # 5*5の範囲内でかつ移動Aで到達できない点 = 現在地から移動Bで到達可能な点
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf") and ((nx, ny) not in next_que):  # 到達可能で未探索の点
                        next_que.append((nx, ny))

    return False, next_que

c = 0
que = deque([])
que.append((C_h-1, C_w-1))

while True:

    f, que = bfs(que, c)

    """

    print(c)
    print(que)
    for i in range(H):
        print(cost[i])
    print("\n")

    """

    if f:  # ゴールが見つかった
        print(c)
        sys.exit()
    if not que:  # queが空のとき、これ以上移動不可能（dequeなのでque==[]は誤り）
        break
    c += 1
print("-1")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(lambda x: x - 1, map(int, input().split()))
Dh, Dw = map(lambda x: x - 1, map(int, input().split()))
S = []
already = []
yet = 1000000
for i in range(H):
    S.append(input())
    already.append([yet] * W)
queue = deque()
queue.append((Cw, Ch, 0))
already[Ch][Cw] = 0
answer = -1
while len(queue) > 0:
    #print(queue)
    #print(already)
    x, y, cost = queue.popleft()
    #print(x, y, cost)
    if x == Dw and y == Dh:
        answer = cost
        break
    for i in range(-2, 3):
        for j in range(-2, 3):
            new_x, new_y = (x + i, y + j)
            # 場外
            if new_x < 0 or new_y < 0 or W <= new_x or H <= new_y:
                continue
            # 動かない
            if new_x == x and new_y == y:
                continue
            # 壁
            if S[new_y][new_x] == '#':
                continue
            # 探索済み
            if already[new_y][new_x] <= cost:
                continue
            if (i == 0 and j == -1) \
            or (i == 0 and j == 1) \
            or (i == 1 and j == 0) \
            or (i == -1 and j == 0):
                queue.appendleft((new_x, new_y, cost))
                already[new_y][new_x] = cost
            else:
                queue.append((new_x, new_y, cost+1))
                already[new_y][new_x] = cost+1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    H, W = LI()
    CH, CW = LI1()
    DH, DW = LI1()
    S = SR(H)
    dist = make_list(H, W, default=-1)

    q = deque()
    dist[CH][CW] = 0
    q.append((0, CH, CW))



    while q:
        d, y, x = q.popleft()
        if y == DH and x == DW:
            print(d)
            return

        for dx in range(-2, 2+1):
            for dy in range(-2, 2+1):
                newx, newy = x + dx, y + dy
                if newx >= 0 and newx < W and newy >= 0 and newy < H:
                    if S[newy][newx] == ".":
                        cost = int([dy, dx] not in dire)
                        if dist[newy][newx] == -1 or dist[newy][newx] > d + cost:
                            dist[newy][newx] = d + cost
                            if cost:
                                q.append((d + 1, newy, newx))
                            else:
                                q.appendleft((d, newy, newx))

    print(dist[DH][DW])







if __name__ == '__main__':
    main()