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:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] >= w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw


    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def legal(x,y):
    if x<0 or y<0 or x>=h or y>=w or board[x][y]=='#':
        return False
    return True

h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx,sy=sx-1,sy-1
ex,ey=map(int,input().split())
ex,ey=ex-1,ey-1

xs=[]
ys=[]
board=[]
for i in range(h):
    l=list(map(str,input()))
    board.append(l)

xs.append(sx)
ys.append(sy)

dist = [[sys.maxsize]*w for i in range(h)]
dist[sx][sy]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]

while xs:
    curx=xs.pop(0)
    cury=ys.pop(0)
    for i in range(0,4):
        nx=curx + dx[i]
        ny=cury + dy[i]
        if not legal(nx,ny):
            continue
        if dist[nx][ny]>dist[curx][cury]:
            dist[nx][ny] = dist[curx][cury]
            xs.insert(0,nx)
            ys.insert(0,ny)

    for i in range(curx-2,curx+3):
        for j in range(cury-2,cury+3):
            if not legal(i,j):
                continue
            if dist[i][j]>dist[curx][cury]+1:
                dist[i][j] = dist[curx][cury]+ 1
                xs.append(i)
                ys.append(j)

if dist[ex][ey]==sys.maxsize:
    print(-1)
else:
    print(dist[ex][ey])

Submission status: Time Limit Exceeded

Solution code:
import sys

def legal(x,y):
    if x<0 or y<0 or x>=h or y>=w :
        return False
    if board[x][y]=='#':
        return False
    return True

h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx,sy=sx-1,sy-1
ex,ey=map(int,input().split())
ex,ey=ex-1,ey-1

xs=[]
ys=[]
board=[]
for i in range(h):
    l=list(map(str,input()))
    board.append(l)

xs.append(sx)
ys.append(sy)

dist = [[sys.maxsize]*w for i in range(h)]
dist[sx][sy]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]

while xs:
    curx=xs.pop(0)
    cury=ys.pop(0)
    for i in range(0,4):
        nx=curx + dx[i]
        ny=cury + dy[i]
        if not legal(nx,ny):
            continue
        if dist[nx][ny]>dist[curx][cury]:
            dist[nx][ny] = dist[curx][cury]
            xs.insert(0,nx)
            ys.insert(0,ny)

    for i in range(curx-2,curx+3):
        for j in range(cury-2,cury+3):
            if not legal(i,j):
                continue
            if dist[i][j]>dist[curx][cury]+1:
                dist[i][j] = dist[curx][cury]+ 1
                xs.append(i)
                ys.append(j)

if dist[ex][ey]==sys.maxsize:
    print(-1)
else:
    print(dist[ex][ey])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(y, x) for x in range(-2, 3) for y in range(-2, 3) if abs(y) + abs(x) > 1]
    que = deque()
    que.append((ch, cw, 0))
    while que:
        y, x, w = que.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                que.appendleft((ny, nx, w))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                mc[ny][nx] = w + 1
                que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    fp = [[10**6 for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    w_goto = []
    for i in range(5):
        for j in range(5):
            if [i, j] in next_y_x:
                pass
            else:
                w_goto.append([-2 + i, -2 + j])
    w_goto.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                    que.appendleft([ny, nx, temp[2]])
                    fp[ny][nx] = w_num
        
        for dy, dx in w_goto:
            nwy = temp[0] + dy
            nwx = temp[1] + dx
            nw = w_num +1

            if 0 <= nwy <= H-1 and 0 <= nwx <= W-1:
                if grid[nwy][nwx] == '.' and fp[nwy][nwx] > w_num:
                    que.append([nwy, nwx, nw])
                    fp[nwy][nwx] = nw


    if fp[Dh][Dw] != 10**6:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

def solve():
  H,W = map(int,input().split())
  C_h,C_w = map(lambda x:int(x)-1,input().split())
  D_h,D_w = map(lambda x:int(x)-1,input().split())
  S = [readline() for _ in range(H)]

  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  move_b = [(-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)]

  while len(deq):
    h,w = deq.popleft()
    if seen[h][w]:
      continue
      seen[h][w] = True
    for dh,dw in move_a:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
        dist[nh][nw] = dist[h][w]
        deq.appendleft((nh,nw))
    for dh,dw in move_b:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
        dist[nh][nw] = dist[h][w]+1
        deq.append((nh,nw))

  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
seen = [[False]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-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)]

while len(deq):
  h,w = deq.popleft()
  if seen[h][w]:
    continue
    seen[h][w] = True
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
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)]
INF = 10**6
t = [[INF]*W for i in range(H)]
for h in range(H):
    th = t[h]
    sh = s[h]
    for w in range(W):
        if sh[w] == '#':
            th[w] = -1

 

def BFS(x,y):
    weight = 0
    checklist = deque([(x,y)])
    while(checklist):
        warplist = []
        while(checklist): 
            h,w = checklist.popleft()
            warplist.append((h,w))
            for i,j in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
                if 0<=i<H and 0<=j<W and t[i][j] > weight:
                    t[i][j] = weight 
                    checklist.append((i,j))
                    
        if t[dh-1][dw-1] != INF:
            return t[dh-1][dw-1]

        weight += 1
        for h,w in warplist:
            for i in range(max(0,h-2),min(H,h+3)):
                ti = t[i]
                for j in range(max(0,w-2),min(W,w+3)):
                    if ti[j] > weight:
                        ti[j] = weight 
                        checklist.append((i,j))
    if t[dh-1][dw-1] != INF:
        return t[dh-1][hw-1]
    else:
        return -1
print(BFS(ch-1,cw-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [readline() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-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)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e7)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
move_b = [(-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)]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))

print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__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())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        for ny, nx in [(y+1, x), (y-1, x), (y, x+1), (y, x-1)]:
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                walk_que.appendleft((ny, nx, w))
        for dy in range(-2, 3):
            ny = y + dy
            for dx in range(-2, 3):
                nx = x + dx
                if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                    mc[ny][nx] = w + 1
                    walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])

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 = [input() for i in range(H)]
INF = 10**6
t = [[INF for j in range(W)] for i in range(H)]
for h in range(H):
    th = t[h]
    sh = s[h]
    for w in range(W):
        if sh[w] == '#':
            th[w] = -1

 

def BFS(x,y):
    weight = 0
    checklist = deque([(x,y)])
    while(checklist):
        warplist = []
        while(checklist): 
            h,w = checklist.popleft()
            warplist.append((h,w))
            for i,j in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
                if 0<=i<H and 0<=j<W and t[i][j] > weight:
                    t[i][j] = weight 
                    checklist.append((i,j))
                    
        if t[dh-1][dw-1] != INF:
            return t[dh-1][dw-1]

        weight += 1
        for h,w in warplist:
            for i in range(max(0,h-2),min(H,h+3)):
                ti = t[i]
                for j in range(max(0,w-2),min(W,w+3)):
                    if ti[j] > weight:
                        ti[j] = weight 
                        checklist.append((i,j))
    if t[dh-1][dw-1] != INF:
        return t[dh-1][hw-1]
    else:
        return -1
print(BFS(ch-1,cw-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
dist[C_h][C_w] = 0
deq = deque()
deq.append((C_h,C_w))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w = deq.popleft()
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]:
      dist[nh][nw] = dist[h][w]
      deq.appendleft((nh,nw))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > dist[h][w]+1:
      dist[nh][nw] = dist[h][w]+1
      deq.append((nh,nw))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque

q = 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

# m=list(map(lambda x: list(x.decode()), stdin.readlines()))
# org_list = stdin.readlines()
# print(org_list)

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = stdin.readline()
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]

    # if val == "#" or val_cost == cost:
    #   continue
    # if val == "." or val_cost < val:
    #   cost_list[nh][nw] = cost
    #   q.appendleft([nh, nw])


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int,input().split())
sh, sw = map(int,input().split())
gh, gw = map(int,input().split())
sh, sw, gh, gw = sh-1, sw-1, gh-1, gw-1
S = [input() for _ in range(H)]

INF = 10**9
ans = [[INF] * W for _ in range(H)]
ans[sh][sw] = 0

Q = deque([[sh,sw]])

while len(Q) > 0:
    h, w = Q.popleft()
    
    for nh, nw in [[h,w+1],[h,w-1],[h+1,w],[h-1,w]]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and ans[nh][nw] > ans[h][w]:
            ans[nh][nw] = ans[h][w]
            Q.append([nh, nw])

    for nh in range(h-2,h+3):
        for nw in range(w-2,w+3):
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and ans[nh][nw] > ans[h][w] + 1:
                ans[nh][nw] = ans[h][w] + 1
                Q.append([nh,nw])

if ans[gh][gw] == INF:
    print(-1)
else:
    print(ans[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -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 Q:
    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])

ans = d[DH - 1][DW - 1]

# print(f'{d=}')
print(ans)

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())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.appendleft([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
ch, cw = [int(i) - 1 for i in  input().split()]
dh, dw = [int(i) - 1 for i in  input().split()]
maze = []
for _ in range(H):
    a = input()
    maze.append(a)
d = deque([(ch, cw, 0)])
value = [[-1 for _ in range(W)] for _ in range(H)]
while d:
    h, w, v = d.popleft()
    if value[h][w] == -1:
        value[h][w] = v
    for hi in range(-2, 3):
        for wi in range(-2, 3):
            next_h = h + hi
            next_w = w + wi
            if (0 <= next_h < H) & (0 <= next_w < W):                
                if (maze[next_h][next_w] == '.'):
                    if (abs(hi) + abs(wi) == 1) & (value[next_h][next_w] == -1):
                        d.appendleft((next_h, next_w, v))
                    elif (abs(hi) + abs(wi) > 1) & (value[next_h][next_w] == -1):
                        d.append((next_h, next_w, v + 1))
print(value[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque

q = 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

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  # s = input()
  s = stdin.readline()
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
# 参考: https://marco-note.net/abc-176-work-log/
import math
from collections import deque

H, W                = map(int, input().split())
start_h, start_w    = map(int, input().split())
goal_h, goal_w      = map(int, input().split())
S                   = [input() for i in range(H)]

INF = math.inf
cost = [[INF] * W for i in range(H)]

# 衝突判定
def wall_check(y, x):
    if(0 <= y < H and 0 <= x < W and S[y][x] == '.'):
        return True
    else:
        return False

# 上下左右
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# ワープ魔法
# (-2, -2) ~ (2, 2) ※(0, 0)とmoveは除く
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move]

dq = deque()
cost[start_h - 1][start_w - 1] = 0          # スタート地点のコストは0
dq.append((start_h - 1, start_w - 1, 0))    # (行, 列, コスト)

while dq:
    h, w, c = dq.popleft()  # 先頭を取り出し，削除
    # 歩いて移動
    for dy, dx in move:
        y, x = h + dy, w + dx
        # 歩いて行ける & コストが更新される場合
        if wall_check(y, x) and cost[y][x] > c:
            cost[y][x] = c
            # 先頭（左側）に要素を追加
            dq.appendleft((y, x, c))    
    # ワープ
    for dy, dx in warp:
        y, x = h + dy, w + dx
        # ワープで行ける & コストが更新される場合
        if wall_check(y, x) and cost[y][x] > c + 1:
            cost[y][x] = c + 1
            dq.appendleft((y, x, c + 1))

if(cost[goal_h - 1][goal_w - 1] != INF):
    print(cost[goal_h - 1][goal_w - 1])
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

q = 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

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

  # # ジャンプ--------------
  # for i in range(-2, 3):
  #   if (ph + i < 0) or (h - 1 < ph + i):
  #     continue

  #   for j in range(-2, 3):
  #     if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
  #       continue
  #     if cost_list[ph + i][pw + j] <= cost:
  #       continue
  #     if org_list[ph + i][pw + j] == ".":
  #       cost_list[ph + i][pw + j] = cost + 1
  #       q.append([ph + i, pw + j])



result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

q = 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

INF = 10 ** 18
# org_list = [INF for i in range(h)]
org_list = deque()
# cost_list = [[INF for j in range(w)] for i in range(h)]
cost_list = [[INF]*w for i in range(h)]

for i in range(h):
  # 文字列の入力
  s = input()
  # org_list[i] = s
  org_list.append(s)


cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]
    if val == "#" or val_cost == cost:
      continue
    if val == "." or val_cost < val:
      cost_list[nh][nw] = cost
      q.appendleft([nh, nw])

  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if cost_list[ph + i][pw + j] <= cost:
        continue
      if org_list[ph + i][pw + j] == ".":
        cost_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)