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

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

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "#"
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10**6, space=4)
    D[y, x] = 0
    while Q:
        x, y = Q.pop()
        for dx, dy in product(range(-2, 3), repeat=2):
            nx, ny = x+dx, y+dy
            if dx==dy==0:
                G[y, x] = '!'
                continue
            elif not G.is_valid_xy(nx, ny) or G[ny, nx] in '#!':
                continue
            elif abs(dx)+abs(dy)<=1:
                G[y, x] = '!'
                Q.append((nx, ny))
                D[ny, nx] = D[y, x]
            elif D[ny, nx] > D[y, x]+1:
                Q.appendleft((nx, ny))
                D[ny, nx] = D[y, x]+1       
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(G, start, goal):
    Q = deque([start])
    x, y = start
    D = Grid(G.grid, function=lambda x:-9 if x=='#' else 10**6, space=4)
    D[y, x] = 0
    
    walk = list(zip([1, 0, -1, 0], [0, 1, 0, -1]))
    warp = [(dx, dy) for dx, dy in product(range(-2, 3), repeat=2)
            if abs(dx)+abs(dy) >= 2]
    while Q:
        x, y = Q.pop()
        if G[y, x] == '!':
            continue
        d = D[y, x]
        G[y, x] = '!'
        
        for dx, dy in walk:
            nx, ny = x+dx, y+dy
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d:
                D[ny, nx] = d
                Q.append((nx, ny))
        for dx, dy in warp:
            nx, ny = x+dx, y+dy                
            if G.is_valid_xy(nx, ny) and G[ny, nx]=='.' and D[ny, nx] > d+1:
                D[ny, nx] = d+1
                Q.appendleft((nx, ny))
    x, y = goal
    return D[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=4)
ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(grid, start, goal):
    dequeue = deque([start])
    x, y = start
    dist = Grid(grid.grid, function=lambda x:-9 if x=='#' else 10**6, space=3)
    dist[y, x] = 0
    i = 0
    while dequeue:
        x, y = dequeue.pop()
        d = dist[y, x]
        i += 1
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.' and dist[ny, nx] > d:
                dist[ny, nx] = d
                dequeue.append((nx, ny))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.' and dist[ny, nx] > d+1:
                dist[ny, nx] = d+1
                dequeue.appendleft((nx, ny))
    x, y = goal
    return dist[y, x]

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=3)
grid[sy, sx] = 's'
grid[gy, gx] = 'g'

ans = bfs_01(grid, (sx, sy), (gx, gy))
print(ans if ans != 10**6 else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid:
    def __init__(self, grid, w=0, h=0, function=lambda x: x, space=1):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
        self.space = space
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join(''.join(f'{{: >{self.space}}}'.format(x) for x in row) for row in self.grid) + '\n'
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

def bfs_01(grid, root):
    dequeue = deque([root])
    x, y = root
    dist = Grid(grid.grid, function=lambda x:-9 if x=='#' else -1, space=3)
    dist[y, x] = 0
    while dequeue:
        x, y = dequeue.pop()
        if grid[y, x] == 'g':
            return dist[y, x]
        grid[y, x] = '!'
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.':
                if grid[ny, nx] == 'g':
                    return dist[y, x]
                dist[ny, nx] = dist[y, x]
                grid[ny, nx] = '!'
                dequeue.append((nx, ny))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if grid.is_valid_xy(nx, ny) and grid[ny, nx] in 'g.':
                dist[ny, nx] = dist[y, x] + 1
                dequeue.appendleft((nx, ny))
    return -1

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
grid = Grid([input() for s in range(h)], space=3)
grid[sy, sx] = 's'
grid[gy, gx] = 'g'

print(bfs_01(grid, (sx, sy)))

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template

H,W = inputlist()
st = inputlist()
gl = inputlist()
maze = ['0']*H
for i in range(H):
    maze[i] = list(input())
table = [[10**9+7]*W for _ in range(H)]

from collections import deque
dx = [0,1,0,-1]
dy = [1,0,-1,0]

que = deque()
table[st[0]-1][st[1]-1] = 0
que.append((st[0]-1,st[1]-1,0))

while len(que) != 0:
    x,y,c = que.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and table[nx][ny] > c:
            table[nx][ny] = c
            que.append((nx,ny,c))

    for i in range(-2,3):
        for j in range(-2,3):
            if (i,j) == (0,1) or (i,j) == (1,0) or (i,j) == (0,-1) or (i,j) == (-1,0):
                continue
            nxa = x+i
            nya = y+j

            if 0 <= nxa < H and 0 <= nya < W and maze[nxa][nya] == "." and table[nxa][nya] > c+1:
                table[nxa][nya] = c+1
                que.append((nxa,nya,c+1))

if table[gl[0]-1][gl[1]-1] == 10**9+7:
    print(-1)
else:
    print(table[gl[0]-1][gl[1]-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]

for h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while P:
  x1,y1 = P.popleft()
  Q.append([x1,y1])
  for dx,dy in move:
    x = x1+dx
    y = y1+dy
    if ans[x][y]==-1:
      ans[x][y] = ans[x1][y1]
      P.append([x,y])
  
  if len(P)==0:
    while Q:
      x2,y2 = Q.popleft()
      for dx,dy in magic:
        x = x2+dx
        y = y2+dy
        if ans[x][y]==-1:
          ans[x][y] = ans[x2][y2]+1
          P.append([x,y])

print(ans[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
# ABC176_D 解説AC
from collections import 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 i in range(H): maze.append([c for c in input()])
dist = [[float('inf') for j in range(W)] for i in range(H)]

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

# 探索部分
deque = deque()
deque.append((Ch, Cw))
dist[Ch][Cw] = 0
while len(deque) > 0:
    # 現在の座標
    pi, pj = [p for p in deque.popleft()]
    d = dist[pi][pj]
    for i in range(4):
        # 新しい座標の候補
        ni, nj = pi + dx[i], pj + dy[i]
        if ni < 0 or ni >= H or nj < 0 or nj >= W: continue # 迷路の外
        if maze[ni][nj] == '#': continue
        if dist[ni][nj] <= d: continue
        dist[ni][nj] = d
        deque.appendleft((ni, nj))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            ni, nj = pi + i, pj + j
            if ni < 0 or ni >= H or nj < 0 or nj >= W: continue # 迷路の外
            if maze[ni][nj] == '#': continue
            if dist[ni][nj] <= d + 1: continue
            dist[ni][nj] = d + 1
            deque.append((ni, nj))

if dist[Dh][Dw] == float('inf'): print(-1)
else: print(dist[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
field=[list(input()) for _ in range(H)]
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1

Walk=[[1,0],[0,1],[-1,0],[0,-1]]
Warp=[[i,j] for i in range(-2,3) for j in range(-2,3)] 

dist=[[-1]*W for _ in range(H)]
que=deque()
dist[sy][sx]=0
que.append([sy,sx])

while que:
    y,x=que.popleft()
    for walk in Walk:
        nx,ny=x+walk[0],y+walk[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]!=dist[y][x]:
            dist[ny][nx]=dist[y][x]
            que.appendleft([ny,nx])
    
    for warp in Warp:
        nx,ny=x+warp[0],y+warp[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="#": continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(dist[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
  h,w = map(int,input().split())
  ch,cw = map(lambda x:int(x)+1,input().split())
  dh,dw = map(lambda x:int(x)+1,input().split())
  s = [["#"]*(w+4) for _ in range(2)]+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4) for _ in range(2)]
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

if __name__ == "__main__":
    main()

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())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
 
H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])
 
while dq:
  check = 0
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  # 상,하,좌,우 1칸씩 이동
  for i in range(4):
    newX = x + dx[i]
    newY = y + dy[i]
    # 상,하,좌,우 이동 가능하면
    if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and not(visited[newX][newY]):
      visited[x][y] = True
      check+=1
      dq.appendleft([cnt,newX,newY])
    # 상,하,좌,우 이동 가능 불가시
    else:
      if check == 0:
        # 인접한 5x5 탐색
        for j in range(24):
          newX = x + dx2[j]
          newY = y + dy2[j]
          if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and not(visited[newX][newY]):
            visited[x][y] = True
            dq.append([cnt+1,newX,newY])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from collections import deque

# 与えられた数値の桁数と桁値の総和を計算する.
def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


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

s = [[] for _ in range(h+2)]
for index in range(h):
    content = ["#"] + list(input()) + ["#"]
    s[index+1] = content
s[0] = s[-1] = ["#"] * (w+2)

costs = [[float('inf')] * (w+2) for _ in range(h+2)]
costs[ch][cw] = 0

data = deque([[ch, cw]])
while len(data) > 0:
    datum = data.popleft()
    x, y = datum[0], datum[1]

    if s[x-1][y] == "." and costs[x-1][y] > costs[x][y]:
        costs[x-1][y] = costs[x][y]
        data.appendleft([x-1, y])

    if s[x+1][y] == "." and costs[x+1][y] > costs[x][y]:
        costs[x+1][y] = costs[x][y]
        data.appendleft([x+1, y])

    if s[x][y-1] == "." and costs[x][y-1] > costs[x][y]:
        costs[x][y-1] = costs[x][y]
        data.appendleft([x, y-1])

    if s[x][y+1] == "." and costs[x][y+1] > costs[x][y]:
        costs[x][y+1] = costs[x][y]
        data.appendleft([x, y+1])

    for idx1 in range(5):
        for idx2 in range(5):
            if 0 <= x-2 + idx1 <= h+1 and 0 <= y-2 + idx2 <= w+1 \
                    and s[x-2+idx1][y-2+idx2] == "." and costs[x-2+idx1][y-2+idx2] > costs[x][y] + 1:
                costs[x-2+idx1][y-2+idx2] = costs[x][y] + 1
                data.appendleft([x-2+idx1, y-2+idx2])

print(costs[dh][dw] if costs[dh][dw] < float('inf') else - 1)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.append([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.append([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.append([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.append([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.append([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.append([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.append([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.append([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,-1,
        0, 0, 0, 0,
        1, 1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  visited[x][y] = True
  # 상,하,좌,우 1칸씩 이동
  for i in range(4):
    newX = x + dx[i]
    newY = y + dy[i]
    if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and not(visited[newX][newY]):
      dq.appendleft([cnt,newX,newY])
    else:
      # 인접한 5x5 탐색
      for j in range(24):
        newX = x + dx2[j]
        newY = y + dy2[j]
        if 0 <= newX < H and 0 <= newY < W and board[newX][newY] == '.' and not(visited[newX][newY]):
          dq.append([cnt+1,newX,newY])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

def main():
    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 = [input() for _ in range(H)]

    INF = 10**12
    path = [[INF] * W for _ in range(H)] # 各マスへの移動コスト
    
    # walk:移動A, warp:移動B
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[ch][cw] = 0
    q.append((ch, cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk: #移動A
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s:
                path[nx][ny] = s
                q.append((nx, ny, s)) # なぜleft?

        for dx, dy in warp: #移動B
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s+1)) # なぜright?

    ans = path[dh][dw] if path[dh][dw] != INF else "-1"
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,sys.stdin.readline().split())
C = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
D = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
# matrix 배열
board = [sys.stdin.readline() for _ in range(H)]
# 방문경로 배열
visited = [[False] * W for _ in range(H)]
# 좌/우/위/아래 방향 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 5x5 방향 이동
dx2 = [-2,-2,-2,-2,-2,
       -1,-1,-1,-1,
        0, 0,
        1, 1, 1, 1,
        2, 2, 2, 2, 2]   
dy2 = [-2,-1, 0, 1, 2,
       -2,-1, 1, 2,
       -2, 2,
       -2,-1, 1, 2,
       -2,-1, 0, 1, 2]
# bfs를 위한 큐 
dq = deque([[0,C[0],C[1]]])

while dq:
  cnt, x, y = dq.popleft()
  # 도착점에 도착하면 종료
  if [x,y] == D:
    print(cnt)
    exit()
  # 상,하,좌,우 1칸씩 이동
  for k in range(4):
    newX = x + dx[k]
    newY = y + dy[k]
    # 걸어서 갈 수 있는 경우 앞에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.appendleft([cnt,newX,newY])
    visited[x][y] = True
  # 인접한 5x5 탐색
  for k in range(20):
    newX = x + dx2[k]
    newY = y + dy2[k]
    # 마법을 사용한 경우 뒤에서부터 큐에 넣음
    if newX < 0 or newY < 0 or newX >= H or newY >= W:
      continue
    if visited[newX][newY] == True:
      continue
    if board[newX][newY] != '.':
      continue
    dq.append([cnt+1,newX,newY])
print(-1)

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] == "#" and (i, j) not in edges[cnt]:
            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

invalid_pos = set([(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)])
# 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):
                if (dx, dy) in  invalid_pos: continue
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num and mapped[x][y] not in g[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)