Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #16156582

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from heapq import *

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
INF = 1 << 30
H, W = wall.shape
S = Sx * W + Sy
T = Tx * W + Ty
dist = np.full(H * W, INF, np.int64)
q = [(0,S)]
while q:
dv, v = heappop(q)
if dv > dist[v]:
continue
vx, vy = divmod(v, W)
# そのままあるく
for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
wx, wy = vx + dx, vy + dy
if not (0 <= wx < H):
continue
if not (0 <= wy < W):
continue
if wall[wx, wy]:
continue
w = wx * W + wy
if dist[w] <= dv:
continue
dist[w] = dv
heappush(q, (dv, w))
# ワープする
for dx in range(-2, 3):
for dy in range(-2, 3):
wx, wy = vx + dx, vy + dy
if not (0 <= wx < H):
continue
if not (0 <= wy < W):
continue
if wall[wx, wy]:
continue
w = wx * W + wy
if dist[w] <= dv + 1:
continue
dist[w] = dv + 1
heappush(q, (dv+1, w))
ans = dist[T]
if ans == INF:
ans = -1
return ans

Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))
```

#### Submission Info

Submission Time 2020-08-22 23:30:12+0900 D - Wizard in Maze maspy Python (3.8.2) 400 1863 Byte AC 872 ms 114828 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
 AC × 3
 AC × 14
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, max_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_11.txt, random_12.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt 599 ms 106780 KB
hand_02.txt 583 ms 106016 KB
max_01.txt 599 ms 114828 KB
random_01.txt 590 ms 114624 KB
random_02.txt 570 ms 106828 KB
random_03.txt 661 ms 114648 KB
random_04.txt 603 ms 106320 KB
random_05.txt 872 ms 114452 KB
random_06.txt 637 ms 109256 KB
random_11.txt 561 ms 106716 KB
random_12.txt 554 ms 105940 KB
sample_01.txt 576 ms 106080 KB
sample_02.txt 585 ms 106336 KB
sample_03.txt 582 ms 106704 KB