Algoogle

Algorithm for Programming Contest

AOJ 2382 King Slime

Category: AOJ Tag: union-find

King Slime

問題概要


スライムは一度の移動で上下左右いずれかの方向に何かにぶつかるまで移動できる.
スライム同士がぶつかるとくっつく.
すべてのスライムがくっつくまでの最小の移動回数を求めよ.

解法


もともとの位置のX座標, Y座標のいずれかが他のスライムと同じだった場合, それらは1ステップでくっつくことができる.
くっつく順番はそれらを繋ぐ木を考えれば無視してよいことがわかる.
最終的に連結でないスライムがある場合, それらをすべて同じ壁に寄せてくっつける.
すでに壁に隣接しているスライムがある場合は, その壁に寄せる.
くっついているかどうかはunion-find木で管理すればよい.

全体のステップ数はN-1+壁に寄せる数になる

コード


(2382.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int MAX = 40010;

struct union_find{
    int rnk[MAX], par[MAX];
    union_find(int n){ for(int i = 0; i < n; i++) rnk[i] = 1, par[i] = i;}
    int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]);}
    void unite(int x, int y){
        if((x = find(x)) == (y = find(y))) return;
        if(rnk[x] > rnk[y]) par[y] = x;
        else{ par[x] = y; if(rnk[x] == rnk[y]) rnk[y]++;}
    }
};

int N, W, H, X[3*MAX], Y[3*MAX], wall;

int solve(){
    union_find uf(N);
    memset(X,-1,sizeof(X)); memset(Y,-1,sizeof(Y));
    wall = 0;
    rep(i,N){
        int x, y; cin >> x >> y;
        wall |= (x==W) | (x==1) | (y==H) | (y==1);
        if(X[x] < 0) X[x] = i;
        else uf.unite(i,X[x]);
        if(Y[y] < 0) Y[y] = i;
        else uf.unite(i,Y[y]);
    }
    set<int> cnt;
    rep(i,W+1) if(X[i] >= 0) cnt.insert(uf.find(X[i]));
    return N-1+(cnt.size()>1? cnt.size()-wall: 0);
}

int main(){
    cin >> N >> W >> H;
    cout << solve() << endl;
    return 0;
}

Comments