(X座標Y座標を独立に考える)ARC-044-C-ビーム

問題URL→http://arc044.contest.atcoder.jp/tasks/arc044_c

全然分からなかったので解説とkmjpさんのブログを見た。

求めるものがマンハッタン距離であり、ビームもX軸方向、Y軸方向に飛んでくるので、
X座標Y座標を独立に考えることができる。
↑これ重要

あとはDPをするのだが、このDPが良く分からなかった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int S[2];   //S[0]:W, S[1]:H
int Q;      //ビームが飛んでくる回数
vector<int> E[2][101010];   //E[方向][時刻]
int dp[101010];

signed main()
{
    cin >> S[0] >> S[1] >> Q;
    REP(i,Q) {
        int j;  //ビームが飛んでくる時刻
        int x;  //方向(0:縦、 1:横)
        int y;  //座標
        cin >> j >> x >> y;
        E[x][j].push_back(y-1);
    }

    ll tot = 0;
    REP(j,2) {
        memset(dp, 0, sizeof(dp));

        REP(i,100100) if (E[j][i].size()) {
            sort(E[j][i].begin(), E[j][i].end());
            if (E[j][i].size() == S[j]) {
                cout << -1 << endl;
                return 0;
            }

            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            reverse(E[j][i].begin(), E[j][i].end());
            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            for (int r : E[j][i]) dp[r] = 1 << 30;
        }

        tot += *min_element(dp, dp + S[j]);
    }

    cout << tot << endl;
}