D - Practical Skill Test

D - Practical Skill Test

解法
まず、整数から座標を持ってこれるようにする
こうすれば次の行き先へのコストがO(1)でわかる
また、L からRまでのコストがわかればいいので、累積和を使いたくなる
ゴールはD通りしかなく、それぞれのゴールから少ない数へたどっていけば、重複なく走査できるのでO(H*W)でセットできる

vvi A(330, vi(330));
int x[k5], y[k5];
int rui[k5];
signed main() {
    int D;
    cin >> H >> W >> D;
    nt(A, H, W);
    rep(h, H)rep(w, W)x[A[h][w]] = w, y[A[h][w]] = h;
    for (int s = H * W; s >= H * W - D + 1; --s) {
        for (int i = s - D; i >= 0; i -= D) {
            int cost = abs(x[i + D] - x[i]) + abs(y[i + D] - y[i]);
            rui[i] = rui[i + D] + cost;
        }
    }
    int Q = in();
    while (Q--) {
        int l = in(), r = in();
        cout << rui[l] - rui[r] << endl;
    }
    return 0;
}