srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC 031 B - 埋め立て

問題

問題概要

盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。

解法

10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部分をUnion Find構造で管理して、最後に、陸の部分でいくつのグループができているかをsetで管理して、その値が1であれば陸の中でグループが1つしかできていないのだから、YESということになる。Union findで管理するものはよく頂点番号で当たられているが、今回のような盤面の問題であっても、番目の左上から右下へ番号を振り、それを頂点番号としてあつかえば同様なことができる。

ミス

classでunion find構造を作っていなくて、同じ配列を使いまわしていて、1WA。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

const int MAX_N = 110;
//Quick Find Weighted
class QuickFindWeighted{
    public:
        int i2g[MAX_N];//i2g[i] := 頂点iが所属するグループ
        vector<int> g2i[MAX_N];//g2i[g]:= グループgに所属する頂点番号

        void init(int n){
            for (int i = 0; i < n; ++i){
                i2g[i] = i;
                g2i[i].push_back(i);
            }
        }
        // 座標iaと座標ibは同じグループに所属しているか?
        bool issame(int ia, int ib){
            return i2g[ia] == i2g[ib];
        }
        // 座標iaの所属するグループと座標ibの所属するグループを1つにする(異なるグループに属するものに)
        void merge(int ia, int ib){
            if(issame(ia, ib)) return;
            //iaの所属するグループがibの所属するグループより小さくならないようにする(一般的マージテク)
            if(g2i[i2g[ia]].size() < g2i[i2g[ib]].size()){
                swap(ia, ib);
            }
            int ga = i2g[ia], gb = i2g[ib];//グループgbの方が要素数が少ない
            for(auto u : g2i[gb]){//uには頂点の番号はいる
                i2g[u] = ga;//グループの番号を更新
            }
            g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());//つなげる
            g2i[gb].clear();
        }
};

string a[10];
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
bool flag = false;

int main(void){
    rep(i, 10) cin >> a[i];

    rep(i, 10)rep(j, 10){
        char t = a[i][j];
        a[i][j] = 'o';
        QuickFindWeighted uf; uf.init(100);
        rep(y, 10)rep(x, 10){//つながっている部分を同じグループにする
            if(a[y][x] == 'x') continue;
            rep(k, 4){
                int ny = y + dy[k], nx = x + dx[k];
                if(!(0 <= ny && ny < 10 && 0 <= nx && nx < 10)) continue;
                if(a[ny][nx] == 'x') continue;
                uf.merge(y * 10 + x, ny * 10 + nx);
            }
        }
        //陸地のグループ数を数える
        set<int> s;
        rep(y, 10)rep(x, 10){
            if(a[y][x] == 'o'){
                s.insert(uf.i2g[y * 10 + x]);
            }
        }
        
        if(s.size() == 1) flag = true;
        a[i][j] = t;
    }

    if(flag) printf("YES\n");
    else printf("NO\n");
    return 0;
}