[TIOJ]1420. 地雷區 (Mine)

題目連結：http://tioj.ck.tp.edu.tw/problems/1420

要看這個地雷有沒有和別的地雷有重疊到的地方，其實就是看這個地雷的周圍24塊，並用disjoint set維護。

#include <bits/stdc++.h>
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> Pair;
bitset<50004> is;
int n,m,c;
int gx[24] = {0,0,1,-1,1,1,-1,-1,2,2,2,2,2,-2,-2,-2,-2,-2,1,0,-1,1,0,-1},
    gy[24] = {1,-1,0,0,-1,1,-1,1,0,1,2,-1,-2,0,1,2,-1,-2,2,2,2,-2,-2,-2};
struct DJS{
    int p[50004];
    void init(){for(int i = 0 ; i < 50004 ; i++)p[i] = i;}
    int query(int x){return p[x] == x ? x : p[x] = query(p[x]);}
    void unite(int x,int y){x = query(x);y = query(y);p[x] = y;} 
    int count(){
        int ans = 0;
        for(int i = 1 ; i <= c; i++ ){
            int tmp = query(i);
            if(!is[tmp])ans++;
            is[tmp] = 1;
        }
        return ans;
    }
}djs;
map<Pair,int> mp;
int X[50004],Y[50004];
int main(){jizz
    djs.init();
    cin >> n >> m >> c;
    int ans = c;
    for(int j = 1 ;j <= c; j++){
        cin >>X[j]>>Y[j];
        mp[{X[j],Y[j]}] = j;
        for(int i = 0 ; i < 24 ; i++){
            int tx = X[j]+gx[i],ty = Y[j]+gy[i];
            if(tx < 1 || tx > n || ty < 1 || ty > m)continue;
            if(mp[{tx,ty}]){
                djs.unite(j,mp[{tx,ty}]);
            }
        }
    }
    cout << djs.count() <<endl;
    return 0;
}