AtCoder Beginner Contest 176 振り返り

D - Wizard in Maze

魔術師が迷路にいる．

上下左右に移動する，あるいはコスト1で自分を中心とした5×5のマスのどれかにワープすることができる．

なるべく少ないワープ回数で移動したい．

解）

ワープ回数0のエリア，1のエリア，…と分けていき，ゴールまでたどり着けばよい．

具体的な実装は以下のコードのものを参考にした．

Submission #16141246 - AtCoder Beginner Contest 176

ワープ回数をdist，現在位置をdeqとする．これらは一次元配列にして計算速度を早くする．

初期設定：

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:

            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

numbaを利用すると時間内に通る．

numbaをインポートし，関数の頭に@njitをつけることで使用できる．

import numba

from numba import njit, b1, i4, i8, f8

@njit*2

HW = list(zip(*[iter(HW)] * 2))

最大値を取り得るマスの数を数え，そのすべてのマスに箱がおかれているかチェックする．

    cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])

置かれていたら縦と横の和から1を引き，それ以外はそのまま和を出力すればよい．

    print(a + b - (cnt == 0))

Submission #16187005 - AtCoder Beginner Contest 176

*1:1, 0), (0, 1), (-1, 0), (0, -1

*2:b1[:, :], i8, i8, i8, i8), cache=True)

def main(wall, Sx, Sy, Tx, Ty):