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 heapq import heappush, heappop
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [input() for _ in range(h)]


dx = [-2, -1, 0, 1, 2]
dy = [-2, -1, 0, 1, 2]
dist = [[float("inf")]*w for _ in range(h)]
dist[ch-1][cw-1] = 0
q = [[0, ch-1, cw-1]]

while q:
    d, x, y = heappop(q)
    for ddx in dx:
        for ddy in dy:
            nx = x+ddx
            ny = y+ddy

            if not (0 <= x+ddx <= h-1 and 0 <= y+ddy <= w-1):
                continue
            if ddx == 0 and ddy == 0:
                continue
            if S[nx][ny] == "#":
                continue
            if dist[x][y]+1 > dist[nx][ny]:
                continue
            if ddx == 0 and (ddy == 1 or ddy == -1)and dist[x][y] < dist[nx][ny]:
                dist[nx][ny] = dist[x][y]
                heappush(q, [dist[nx][ny], nx, ny])
            elif (ddx == 1 or ddx == -1) and ddy == 0 and dist[x][y] < dist[nx][ny]:
                dist[nx][ny] = dist[x][y]
                heappush(q, [dist[nx][ny], nx, ny])
            elif dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                heappush(q, [dist[nx][ny], nx, ny])
if dist[dh-1][dw-1] == float("inf"):
    print(-1)
    exit()
print(dist[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)
    
INF = 1 << 50
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw

            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] != INF:continue
            if abs(dh) + abs(dw) <= 1:
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, inp().split())
    sy, sx = map(lambda x: int(x) - 1, inp().split())
    gy, gx = map(lambda x: int(x) - 1, inp().split())
    G = [inpS() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#import heapq
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

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#BFS
visited = [[False] * W for _ in range(H)]
willSearch = [[False] * W for _ in range(H)]
Q = deque()
QN = deque()
Q.append((0,Ch,Cw))
QN.append((0,Ch,Cw))
while Q:
  while Q:
    c,x,y = Q.popleft()
    if visited[x][y]:
      continue
    visited[x][y] = True
    QN.append((c,x,y))
    #print(c,x,y)
    if x == Dh and y == Dw:
      print(c)
      exit(0)
    for dx,dy in dpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c,nx,ny))
        QN.append((c,nx,ny))
        willSearch[nx][ny] = True
  while QN:
    c,x,y = QN.popleft()
    for dx,dy in mpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c+1,nx,ny))
        #print("m", c+1, nx,ny)
        #willSearch[nx][ny] = True
      
print(-1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))


while q:
    u, v = q.popleft()
    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if (0 <= u + i < H and 0 <= v + j < W
                and X[u + i][v + j] == "."
                and dist[u + i][v + j] > dist[u][v]):
            dist[u + i][v + j] = dist[u][v]
            q.append((u + i, v + j))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v] + 1):
                dist[u + i][v + j] = dist[u][v] + 1
                q.appendleft((u + i, v + j))

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

Submission status: Time Limit Exceeded

Solution code:
## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt, hn*N+wn))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    res = ans[gy][gx] if ans[gy][gx] < INF else -1
    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))
dif=list(dif)
warp=list(warp)

for i in range(h):
    for j in range(w):
        if grid[i][j]!=-1:
            for d in dif:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 0])
            for d in warp:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

dist=dijkstra(es,h*w,ch*w+cw)
if dist[dh*w+dw]==float('inf'):
    print(-1)
else:
    print(dist[dh*w+dw])

Submission status: Time Limit Exceeded

Solution code:
## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*INF+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, INF)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt, hn*INF+wn))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt+1, hn*INF+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]!=-1:
            for d in dif:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 0])
            for d in warp:
                if 0<=i+d[0]<h and 0<=j+d[1]<w and grid[i+d[0]][j+d[1]]!=-1:
                    es[i*w+j].append([(i+d[0])*w+j+d[1], 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

dist=dijkstra(es,h*w,ch*w+cw)
if dist[dh*w+dw]==float('inf'):
    print(-1)
else:
    print(dist[dh*w+dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
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]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.pop()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s:
            d[nx][ny] = s
            q.append((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 d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.append((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    q = deque()
    q.append((sy, sx, 0))
    ans[sy][sx] = 0

    while q:
        sy, sx, cost = q.popleft()
        for dy, dx in drc4:
            ny, nx = dy + sy, dx + sx
            if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                ans[ny][nx] = cost
                q.append((ny, nx, cost))

        for dy8, dx8 in warp:
            ny8, nx8 = dy8 + sy, dx8 + sx
            if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                ans[ny8][nx8] = cost + 1
                q.append((ny8, nx8, cost + 1))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append((sy, sx, 0))
        ans[sy][sx] = 0

        while q:
            sy, sx, cost = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == "." and ans[ny][nx] > cost:
                    ans[ny][nx] = cost
                    q.append((ny, nx, cost))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W and G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                    ans[ny8][nx8] = cost + 1
                    q.append((ny8, nx8, cost + 1))

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append((sy, sx, 0))
        ans[sy][sx] = 0

        while q:
            sy, sx, cost = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > cost:
                        ans[ny][nx] = cost
                        q.append((ny, nx, cost))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                        ans[ny8][nx8] = cost + 1
                        q.append((ny8, nx8, cost + 1))

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.pop()
    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 d[nx][ny] > s:
            d[nx][ny] = s
            q.append((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.append((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [input() for _ in range(h)]


dx = [-2, -1, 0, 1, 2]
dy = [-2, -1, 0, 1, 2]
dist = [[float("inf")]*w for _ in range(h)]
dist[ch-1][cw-1] = 0
q = [[0, ch-1, cw-1]]

while q:
    d, x, y = heappop(q)
    for ddx in dx:
        for ddy in dy:
            nx = x+ddx
            ny = y+ddy

            if not (0 <= x+ddx <= h-1 and 0 <= y+ddy <= w-1):
                continue
            if ddx == 0 and ddy == 0:
                continue
            if S[nx][ny] == "#":
                continue
            if dist[x][y]+1 > dist[nx][ny]:
                continue
            if ddx == 0 and (ddy == 1 or ddy == -1)and dist[x][y] < dist[nx][ny]:
                dist[nx][ny] = dist[x][y]
                q.append([dist[nx][ny], nx, ny])
            elif (ddx == 1 or ddx == -1) and ddy == 0 and dist[x][y] < dist[nx][ny]:
                dist[nx][ny] = dist[x][y]
                q.append([dist[nx][ny], nx, ny])
            elif dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                q.append([dist[nx][ny], nx, ny])
if dist[dh-1][dw-1] == float("inf"):
    print(-1)
    exit()
print(dist[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                        ans[ny][nx] = ans[sy][sx]
                        q.append((ny, nx))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                        ans[ny8][nx8] = ans[sy][sx] + 1
                        q.append((ny8, nx8))

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
"""
01-BFS
"""

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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]
dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

q = deque([(ch, cw)])
dist[ch][cw] = 0
while q:
    y, x = q.popleft()
    for dy, dx in dwalk:
        py = y+dy; px = x+dx
        if not 0<=py<h: continue
        if not 0<=px<w: continue
        if area[py][px]=='#': continue
        if dist[py][px]>dist[y][x]:
            dist[py][px] = dist[y][x]
            q.appendleft((py, px))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            py = y+dy; px = x+dx
            if not 0<=py<h: continue
            if not 0<=px<w: continue
            if area[py][px]=='#': continue
            if dist[py][px]>dist[y][x]+1:
                dist[py][px] = dist[y][x]+1
                q.append((py, px))

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

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            # if sy == gy and sx == gx:
            #     return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                    # if G[ny8][nx8] == "#":
                    #     continue
                    # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                    #     continue
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                        ans[ny8][nx8] = ans[sy][sx] + 1
                        q.append((ny8, nx8))
        # return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.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 d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 999999999999

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.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 d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])

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())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]
all_lis = [[Ch-1, Cw-1]]

while True:
  new_move_lis  = []
  for i,j in move_lis:
    if maze[i][0][j] == "#":
      continue
    for k,l in walk_move:
      if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in all_lis:
        dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
        new_move_lis.append([i+k, j+l])
        already_lis.append([i+k, j+l])
        all_lis.append([i+k, j+l])
  if not len(new_move_lis):
    new_already_lis = []
    for o,p in already_lis:
      for m,n in magic_move:
        if not m and not n:
          continue
        if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == "." and not [o+m, p+n] in all_lis:
          dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
          new_move_lis.append([o+m, p+n])
          new_already_lis.append([o+m, p+n])
          all_lis.append([o+m, p+n])
    already_lis = new_already_lis
  if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
    break
  else:
    move_lis = new_move_lis

ans = dp[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(ans)