B - 埋め立て

コメント歓迎です。
深さ優先探索を使った塗りつぶしで解きました。

前回とほぼ同様のコードでACできました。

前回：A - 深さ優先探索 - 思考する三角形▽

問題

AtCoder 版！蟻本 (初級編) - Qiita より

beta.atcoder.jp

方針

この問題では、海('x')のうちひとつを埋め立てて陸('o')とし、島が陸続きになるか判定します。

島が陸続きになっているかを判定するために深さ優先探索を使います。

深さ優先探索で新たに埋め立てた陸('o')から島の部分を探索していき、移動するたびそこを('x')に置き換えてきます。

探索が終わったあとすべての位置が'x'となっていれば島は陸続きということになります。

島が陸続きでなければ、探索でたどり着けない'o'が残るからです。

陸続きになっていれば定められた"YES"、なっていなければ"NO"を出力します。
出力の一部が小文字になっていて何度かWAしました…。

処理の詳細はコード中のコメントに記載しましたので、それを参照してください。

コード(AC)

#include <iostream>
using namespace std;

// 変数定義
string A[10]; // 最大10行
string COPY[10]; // Aのコピー

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

// 深さ優先探索 陸を'x'に塗り替えていく
void dfs(int x, int y) {
  // 一度通った場所は'x'に置き換える
  A[x][y] = 'x';
  // 上下左右1つずつ移動
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i]; // 移動先のx座標
    int ny = y + dy[i]; // 移動先のy座標
    // 進んだ先がエリアからはみ出してたら処理をスキップ
    if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10) continue;
    // 進んだ先が海だったら処理をスキップ
    if (A[nx][ny] == 'x') continue;
    // 進んだ先が陸だったら深さ優先探索継続
    dfs(nx, ny);
  }
  // 進める先がなくなったら戻る
  return;
}

// すべて10x10のマスがすべて'x'なら島が陸続きと判断
bool judge(){
  for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 10; j++) {
      if (A[i][j] == 'o') return false;
    }
  }
  return true;
}

// Aを初期化
void A_init() {
  for (int i = 0; i < 10; i++) {
    A[i] = COPY[i];
  }
}

int main() {
  // 入力
  for (int i = 0; i < 10; i++) {
    cin >> A[i];
    COPY[i] = A[i]; // Aの初期状態を保持
  }

  // 島が陸続きか判定する変数
  bool ans;

  // 'x'を'o'に埋め立てた位置をstart地点として深さ優先探索を開始
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (A[i][j] == 'x') {
        A[i][j] = 'o'; // 埋め立て
        dfs(i, j);     // 深さ優先探索
        ans = judge();
        // 島が陸続きになったらループを抜ける
        if (ans == true) break;
        A_init();
      }
    if (ans == true) break;
    }
  }

  // 出力
	cout << (ans ? "YES" : "NO") << endl;
	return 0;
}