ARC 031 B

今回はこの問題です。

arc031.contest.atcoder.jp

10*10マスがあります。それぞれのマスにはoかxになっています。このうちxのマスをひとつだけoに変更することによって、すべてのoマスが連結するようにできるかどうかを判断しなさい、という問題です。ただし連結とは上下左右いずれかでつながっていることです。

回答はこちら。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    char a[10][10];
    int result[10][10] = {};
    int sum = 0;
     
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
     
    bool count(int x, int y, int cnt)
    {
        if(result[x][y] != 0) return false;
        bool ischecked[10][10];
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                ischecked[i][j] = false;
            }
        }
        ischecked[x][y] = true;
        int ans = 1;
        queue<int> xqu, yqu;
        xqu.push(x);
        yqu.push(y);
        while(!xqu.empty()){
            int nowx = xqu.front();
            int nowy = yqu.front();
            xqu.pop();
            yqu.pop();
            if(result[nowx][nowy] != 0){
                result[x][y] = result[nowx][nowy];
                return false;
            }
            for(int i = 0; i < 4; i++){
                int nx = nowx + dx[i], ny = nowy + dy[i];
                if(nx < 0 || ny < 0 || nx > 9 || ny > 9 || a[nx][ny] == 'x' || ischecked[nx][ny]) continue;
                xqu.push(nx);
                yqu.push(ny);
                ischecked[nx][ny] = true;
                ans++;
            }
        }
        result[x][y] = cnt;
        return true;
    }
     
     
    int main()
    {
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                cin >> a[i][j];
            }
        }
        int cnt = 1;
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(a[i][j] != 'x' && count(i, j, cnt)) cnt++;
                // cout << result[i][j] << " ";
            }
            // cout << endl;
        }
        if(cnt > 5){
            cout << "NO" << endl;
            return 0;
        }
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(a[i][j] == 'o') continue;
                set<int> nowans;
                nowans.insert(0);
                for(int k = 0; k < 4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx < 0 || ny < 0 || nx > 9 || ny > 9) continue;
                    nowans.insert(result[nx][ny]);
                }
                if(nowans.size() == cnt){
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
        cout << "NO" << endl;
        return 0;
        // cout << sum << endl;
    }

cntが領域の数を表します。領域に番号をつけていきます。ひとつひとつのマスについて、幅優先探索で領域を調べていきます。探索中にすでに番号が割り振られたマスにたどり着いた場合は、このマスと同じ番号を割り当てておきます。そうでないときは、新たな番号を割り当てます。
領域が5つ以上ある際は、どうやっても全てを連結させることはできないのでNOを出力して終了します。
そうでない場合はすべてのxのマスに対して、oにかえたときすべての領域を連結させられるかをしらべます。nowansは隣接している領域の番号の集合になります。集合のサイズで比較するので、最初に0を加えておきます。集合の大きさとcntの値を比較して、一致すればYESを出力して終了します。
全てのxマスに対して調べ終わったら、全て連結させることはできないということになるのでNOを出力します。

同じ領域に含まれるマスを判断するのがちょっと大変でした。