AtCoder Beginner Contest 031 B

コード

自力でACできた！わーい。

#include <iostream>
#include <string.h>
using namespace std;

char map[10][10];

// あるmapと出発点が与えられたら、そのmapにおいてその出発点から行けるところを'v'で塗りつぶす関数。
void dfs(int i, int j, char copy[10][10]) {
  if (i < 0 || 10 <= i || j < 0 || 10 <= j || copy[i][j] == 'x' || copy[i][j] == 'v') return;
  if (copy[i][j] == 'o') copy[i][j] = 'v';
  
  dfs(i-1, j, copy);
  dfs(i+1, j, copy);
  dfs(i, j-1, copy);
  dfs(i, j+1, copy);
}

// 実験用のコピーされたmapを受け取り、陸地がひとつづきであるかどうかをT/Fで返す関数。
bool unity(char copy[10][10]) {
  bool ret = true;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (copy[i][j] == 'o') ret = false;
    }
  }
  return ret;
}

int main() {
  // mapを読むこむ
  int start[2] = {-1, -1};
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> map[i][j];
      if (start[0] == -1 && map[i][j] == 'o') {
        start[0] = i;
        start[1] = j;
      }
    }
  }

  // 出力する文字列を初期化
  string ret = "NO";

  // 海を1箇所につき1ループ
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (map[i][j] == 'x') {
        // mapのコピーをつくる
        char copy[10][10];
        memcpy(copy, map, sizeof(map));
        // コピーの中の海を1箇所だけ陸にする
        copy[i][j] = 'o';
        // 陸がひとつづきかどうか確認する
        dfs(start[0], start[1], copy);
        // 陸がひとつづきなら、出力する文字列をYESにする
        if (unity(copy)) ret = "YES";
      }
    }
  }

  cout << ret << endl;
}

学んだこと

色んなところを埋め立ててみて、その都度陸地がひとつづきか調べる。そのときに訪問状況を記録する必要があるが、それは毎回まっさらな状態のマップをつかう必要がある。なので標準入力からつくったマップに直接記録をつくるのではなく、都度訪問情報記録用のマップのコピーをつくる。
配列そのものを関数の戻り値にすることはできない。