ARC031 B問題 埋め立て

Atcoder Regular Contest B - 埋め立て

問題リンク

問題文

とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、
つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。 マス マスのこの島国の地図が与えられるので、 マスを埋め立てた時に つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。

入力

(割愛)

• 島国の地図が行にわたって与えられる。
• 各行は文字からなり、oは陸地を、xは海を表す。
• 少なくともマスは陸地があることが保証される。
• 少なくともマスは海があることが保証される。

出力

海をマスだけ陸地にすることで全体を つの島にできるなら YES 、できないなら NO を出力せよ。出力の末尾には改行をつけること。ただし、元からつの島だった場合も YES を出力せよ。

アプローチ

埋め立てるのはマスで良いから各海マスについてそこを陸地と見なし、隣接する陸地マスの数を数えてみる。得られた数が最初の陸地のマス数+1なら全ての島が繋がったと言えるはず。
陸地マスの数はDFSで数える。マスしかないのでスタックオーバーフローの心配はない。

解答

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const string YES = "YES";
const string NO = "NO";

// 上下左右を調べるやつ
const int dy[] = {1, -1, 0, 0};
const int dx[] = {0, 0, 1, -1};

int land_count = 1; // 埋め立て分で1

//行けるとこか判定
bool is_valid(const vector<vector<char>> &A, const vector<vector<bool>> &is_checked, int y, int x) {
    if(y >= 10 || x >= 10 || y < 0 || x < 0) return false;
    if(A[y][x] == 'x' || is_checked[y][x]) return false;

    return true;
}

// 連結している陸地の数を数える再帰関数
int connected_count(const vector<vector<char>> &A, vector<vector<bool>> &is_checked, int y, int x) {
    is_checked[y][x] = true;
    int count = 1; // 自身

    // 上下左右について調べる
    for(int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(is_valid(A, is_checked, ny, nx)) {
            count += connected_count(A, is_checked, ny, nx);
        }
    }

    return count;
}

bool check_matched(const vector<vector<char>> &A, int y, int x) {
    vector<vector<bool>> is_checked(10, vector<bool>(10, false));
    int count = connected_count(A, is_checked, y, x);

    return count == land_count;
}

void solve(const vector<vector<char>> &A){
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            // 陸地はスキップ
            if(A[i][j] == 'o') continue;

            // このマスA(i, j)を埋め立てたら全ての陸地に行けるか試す。
            if(check_matched(A, i, j)) {
                cout << YES << endl;
                return;
            }
        }
    }
    cout << NO << endl;
}

int main(){
    vector<vector<char>> A(10, vector<char>(10));
    for(int i = 0 ; i < 10 ; i++){
        for(int j = 0; j < 10; j++) {
            cin >> A[i][j];
            if(A[i][j] == 'o') land_count++;
        }
    }
    solve(A);
    return 0;
}