AOJ 2382 King Slime - mayoko’s diary

問題

H*W のグリッド上に N 個の頂点がある。各頂点は, 上下左右いずれかの方向に移動でき, 移動する際は壁にぶつかるか別の頂点にぶつかるまで動き続ける。別の頂点にぶつかった場合, ぶつかった頂点同士は合体する。

この移動を何回か行うことにより, 全ての頂点を合体させたい。最小の移動回数はいくらか。

解法

一回の移動で高々一つの頂点しか減りません。また, 減る場合は動かした頂点は別の頂点に衝突しています。
これを考えると, 「頂点の動きとして, 壁にぶつけるような頂点の動かし方を最小化したい」というように問題を言い換えることができます。

X 座標, もしくは Y 座標が一致している場合, それらの頂点はぶつけ合うことで必ず一つの頂点にすることができます(グラフで辺をつないだ連結成分というイメージ)。この連結成分の頂点数が n の場合, これらを一つの頂点にするのに必要な操作回数は n-1 です。

このようにしてすべての連結成分の頂点数を 1 にした場合, 残りの頂点は X 座標も Y 座標も一致していないので, どこかの壁にぶつけてから合体させるしかないです。この際, すでに壁と接している頂点があった場合は操作を 1 回さぼれます。基本的には 2*(連結成分の個数)-1 回かかります。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

const int MAXN = 100100;
int X[MAXN], Y[MAXN];
vi Xp[MAXN], Yp[MAXN];
bool done[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, H, W;
    cin >> N >> W >> H;
    int flag = 0;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        Xp[X[i]].push_back(i);
        Yp[Y[i]].push_back(i);
        if (X[i] == 1 || Y[i] == 1 || X[i] == W || Y[i] == H) flag = 1;
    }
    UnionFind uf(N);
    for (int i = 0; i < MAXN; i++) {
        for (int j = 1; j < Xp[i].size(); j++)
            uf.unite(Xp[i][j], Xp[i][0]);
        for (int j = 1; j < Yp[i].size(); j++)
            uf.unite(Yp[i][j], Yp[i][0]);
    }
    int ans = 0;
    int sz = 0;
    for (int i = 0; i < N; i++) {
        int p = uf.find(i);
        if (!done[p]) {
            done[p] = true;
            sz++;
            ans += uf.count(p)-1;
        }
    }
    if (sz > 1) {
        if (flag) ans += 2*(sz-1);
        else ans += 2*sz-1;
    }
    cout << ans << endl;
    return 0;
}