分からないのでヒントを見てしまった。自力で解く/解けるべきだった。

C - ビーム

問題

プレイヤーは$H\times W$の盤上にいる。 プレイヤーは隣接する4マスに好きなだけ移動できる。 座標軸と並行にビームが飛んでくるので、全て回避したい。 最小の移動回数を求めよ。

解法

クエリは縦と横で独立なので分割しそれぞれ計算。 $O(Q)$。

移動するのは現在位置にビームが来たときだけでよい。 また、来たビームに垂直な方向のいずれかに最小の距離だけでよい。 ただし、複数のビームが同じ時間に来て、太いものになっている場合があることに注意。

ここから縦のビームと横のビームが独立であることが分かる。 すると$H \times 1$と$1 \times W$の盤面に分けて考えることができ、ひとつのクエリは$O(1)$で処理できる。

実装

sortを忘れててWA。始めは気付いていたので、vectorじゃなくてsetにすべきかなあとか頭に浮かんでいたが、いつの間にか消えていた。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
constexpr int inf = 1000000007;
int min_steps(int l, map<int,vector<int> > & qs) {
    vector<int> xs(l);
    for (auto & q : qs) {
        vector<int> & beams = q.second;
        sort(beams.begin(), beams.end());
        for (int x : beams) if (x+1 < l) xs[x+1] = min(xs[x+1], xs[x] + 1);
        reverse(beams.begin(), beams.end());
        for (int x : beams) if (0 <= x-1) xs[x-1] = min(xs[x-1], xs[x] + 1);
        for (int x : beams) xs[x] = inf;
    }
    return *min_element(xs.begin(), xs.end());
}
int main() {
    int w, h, q; cin >> w >> h >> q;
    map<int,vector<int> > hq, vq; // horizontal/vertical query: time -> position
    repeat (i,q) {
        int t, d, x; cin >> t >> d >> x;
        -- x;
        (d ? hq : vq)[t].push_back(x);
    }
    int y = min_steps(h, hq);
    int x = min_steps(w, vq);
    cout << (y == inf or x == inf ? -1 : x + y) << endl;
    return 0;
}

参考