k-tokitoh

2019-07-29

AtCoder Beginner Contest 031 B

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;
}

学んだこと