ARC044 C問題 ビーム

すごい面白い問題だった。
ビームがx, y方向に打たれるので頑張って最小の動きで逃げようという問題。
ビームがx方向に打たれるものとy方向に打たれるものがあるが、結局動きのコストはマンハッタン距離なのでx,y独立に考えてもいいよね、というのが根幹となる発想。

dp用の配列の更新が面白い。
どうやったら上手くdpを更新できるのかと思ったが、ビームが来たらそこを避けるように一つ次のマスに移動する動作をとればいい。それを上から下、下から上の二回やって、最小値を出せばおｋ。わざわざ一回の走査でやろうとすると闇。

x,yで全く同じコードなので、関数化すれば良かった…

const int INF = 1e9;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int W, H, Q; cin >> W >> H >> Q;
    map<int, vector<P> > mp;
    rep(i, Q){
        int t, d, x; cin >> t >> d >> x; x--;
        mp[t].push_back(P(d, x));
    }
    int dpx[W], dpy[H];
    memset(dpx, 0, sizeof(dpx));
    memset(dpy, 0, sizeof(dpy));
    for(auto it=mp.begin(); it!= mp.end(); it++){
        auto& vv = it->second;
        vector<int> vx, vy;
        for(auto& v : vv){
            if(v.first == 0){
                vx.push_back(v.second);
            }else if(v.first == 1){
                vy.push_back(v.second);
            }
        }
        sort(vx.begin(), vx.end());
        sort(vy.begin(), vy.end());
        for(int i=0; i<len(vx); i++){
            int nx = vx[i]+1;
            if(nx < W) dpx[nx] = min(dpx[nx], dpx[vx[i]]+1);
        }
        for(int i=len(vx)-1; i>=0; i--){
            int nx = vx[i]-1;
            if(nx >= 0) dpx[nx] = min(dpx[nx], dpx[vx[i]]+1);
        }
        for(int i=0; i<len(vx); i++){
            dpx[vx[i]] = INF;
        }
        for(int i=0; i<len(vy); i++){
            int ny = vy[i]+1;
            if(ny < H) dpy[ny] = min(dpy[ny], dpy[vy[i]]+1);
        }
        for(int i=len(vy)-1; i>=0; i--){
            int ny = vy[i]-1;
            if(ny >= 0) dpy[ny] = min(dpy[ny], dpy[vy[i]]+1);
        }
        for(int i=0; i<len(vy); i++){
            dpy[vy[i]] = INF;
        }
    }
    int resx = INF;
    for(int i=0; i<W; i++){
        resx = min(resx, dpx[i]);
    }
    int resy = INF;
    for(int i=0; i<H; i++){
        resy = min(resy, dpy[i]);
    }
    int res = resx+resy;
    if(resx == INF || resy == INF){
        res = -1;
    }
    cout << res << endl;
}