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

Submission #16141246

Source Code Expand

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

@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)
deq = np.empty(H * W + 100, np.int64)
dist[S] = 0
deq[0], l, r = S, 0, 1
while l < r:
v, l = deq[l], l + 1
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] <= dist[v]:
continue
dist[w] = dist[v]
deq[l - 1], l = w, l - 1
# ワープする
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] <= dist[v] + 1:
continue
dist[w] = dist[v] + 1
deq[r], r = w, r + 1
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 22:13:26+0900 D - Wizard in Maze maspy Python (3.8.2) 400 1893 Byte AC 679 ms 118416 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 493 ms 106532 KB
hand_02.txt 492 ms 105672 KB
max_01.txt 510 ms 115956 KB
random_01.txt 507 ms 114476 KB
random_02.txt 492 ms 106624 KB
random_03.txt 547 ms 115880 KB
random_04.txt 504 ms 106420 KB
random_05.txt 679 ms 118416 KB
random_06.txt 548 ms 109656 KB
random_11.txt 495 ms 106652 KB
random_12.txt 483 ms 106072 KB
sample_01.txt 494 ms 105636 KB
sample_02.txt 488 ms 106048 KB
sample_03.txt 491 ms 106048 KB