1
class Solution {
2
 public:
3
  int n, m;
4
  int visited[201][201] = {0};
5
  // Breadth First Search
6
  // Flood Fill Algorithm
7
  void bfs(vector<vector<char>> &board, int x, int y) {
8
    queue<int> q;
9
    q.push(m * x + y);
10
    visited[x][y] = 1;
11
    int curr, i, j;
12
    while (!q.empty()) {
13
      curr = q.front();
14
      q.pop();
15
      i = curr / m;
16
      j = curr % m;
17
      board[i][j] = 'O';
18
      if (i > 0 && !visited[i - 1][j] && board[i - 1][j] == 'C') {
19
        visited[i - 1][j] = 1;
20
        q.push(m * (i - 1) + j);
21
      }
22
      if (i < n - 1 && !visited[i + 1][j] && board[i + 1][j] == 'C') {
23
        visited[i + 1][j] = 1;
24
        q.push(m * (i + 1) + j);
25
      }
26
      if (j > 0 && !visited[i][j - 1] && board[i][j - 1] == 'C') {
27
        visited[i][j - 1] = 1;
28
        q.push(m * i + j - 1);
29
      }
30
      if (j < m - 1 && !visited[i][j + 1] && board[i][j + 1] == 'C') {
31
        visited[i][j + 1] = 1;
32
        q.push(m * i + j + 1);
33
      }
34
    }
35
  }
36
  void solve(vector<vector<char>> &board) {
37
    n = board.size();
38
    m = board[0].size();
39
    // Marking the regions to capture
40
    // mark all the O to C
41
    for (int i = 0; i < n; i++) {
42
      for (int j = 0; j < m; j++) {
43
        if (board[i][j] == 'O') board[i][j] = 'C';
44
      }
45
    }
46
    // if we have found C on the outer edges, then all the connected C to it
47
    // should be converted to O as they can't be captured
48
    for (int i = 0; i < m; i++) {
49
      if (board[0][i] == 'C' && !visited[0][i]) bfs(board, 0, i);
50
      if (board[n - 1][i] == 'C' && !visited[n - 1][i]) bfs(board, n - 1, i);
51
    }
52
    for (int i = 1; i < n - 1; i++) {
53
      if (board[i][0] == 'C' && !visited[i][0]) bfs(board, i, 0);
54
      if (board[i][m - 1] == 'C' && !visited[i][m - 1]) bfs(board, i, m - 1);
55
    }
56
    // capturing the regions
57
    // now remaining C can be capture
58
    for (int i = 0; i < n; i++) {
59
      for (int j = 0; j < m; j++) {
60
        if (board[i][j] == 'C') board[i][j] = 'X';
61
      }
62
    }
63
  }
64
};
65
static const auto speedup = []() {
66
  std::ios::sync_with_stdio(false);
67
  std::cin.tie(nullptr);
68
  std::cout.tie(nullptr);
69
  return 0;
70
}();