問題概要

次のような、 $10 \times 10$ のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。

あなたは、グリッド内部の文字を 1 つ選んで 'o' に書き換えることができます。

書き換えたあとのグリッドにおいて、文字 'o' が全体として連結 (上下左右への隣接関係によって繋がっていること) になっているかどうかを判定してください。

xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

解法

100 マス分全探索しましょう！

つまり、各マスの文字を順に 'o' にしていって、'o' が全体として連結になるかどうかを調べていきましょう。

そして、'o' が全体として繋がっているどうかを調べたり、'o' の塊が何個あるかを調べたりする方法は、ざっくり次の 3 つの方法があります。

DFS を用いる方法
BFS を用いる方法
Union-Find を用いる方法

1, 2 の方法については、次の Qiita 記事に詳しく書いたので参考にしてもらえたらと思います。

3 の Union-Find を用いた方法については、蟻本・螺旋本・けんちょん本・鉄則本など、さまざまな本に載っています。

コード

ここでは BFS で解きます。

#include <bits/stdc++.h>
using namespace std;

// マス {x, y} を表す
using pint = pair<int,int>;

// 上下左右への移動を表す変数
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
    vector<string> A(10);
    for (int i = 0; i < 10; ++i) cin >> A[i];
    
    // マス (px, py) を順に 'o' にしていく (実装上はしなくて OK)
    for (int px = 0; px < 10; ++px) {
        for (int py = 0; py < 10; ++py) {
            // 頂点 (px, py) を始点とする BFS をする
            queue<pint> que;
            vector<vector<int>> dist(10, vector<int>(10, -1));
            que.push({px, py});
            dist[px][py] = 0;
            while (!que.empty()) {
                auto [x, y] = que.front();
                que.pop();
                for (int dir = 0; dir < 4; ++dir) {
                    int x2 = x + dx[dir], y2 = y + dy[dir];
                    if (x2 < 0 || x2 >= 10 || y2 < 0 || y2 >= 10) continue;
                    if (A[x2][y2] == 'o' && dist[x2][y2] == -1) {
                        que.push({x2, y2});
                        dist[x2][y2] = dist[x][y] + 1;
                    }
                }
            }
            
            // すべての 'o' が訪問済みかを判定する
            bool ok = true;
            for (int x = 0; x < 10; ++x) {
                for (int y = 0; y < 10; ++y) {
                    if (A[x][y] == 'o' && dist[x][y] == -1) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 031 B - 埋め立て (3Q, 試験管緑色)

問題概要

解法

コード