Problem Explanation

The problem requires us to capture all the regions on a 2D board that are surrounded by 'X'. A region is said to be surrounded if there are no 'O's on its borders or there are no 'O's on the border of the board that are connected to it. We capture the region by flipping all 'O's in it to 'X's.

Let's take the example provided:

1
2
3X X X X
4X O O X
5X X O X
6X O X X

When we run our function, it should configure the board to:

1
2
3X X X X
4X X X X
5X X X X
6X O X X

Here, the 'O's at the center are surrounded by 'X's and there's no path from them to an 'O' on the borders, so they are captured and converted to 'X'. However, the 'O' at the bottom row is on the border and remains 'O'.

Solution Explanation

This solution uses a breadth-first search (BFS) algorithm for traversing the board. It first starts by checking the borders of the board for 'O's, and if found, it marks them as temporarily as '', enqueues them in a queue, and checks their neighboring cells. For each cell in the queue, it checks if any of its neighbors are 'O', adds them to the queue and marks them as ''. This proceeds until the queue is empty. Finally, it traverses the entire board converting any remaining 'O' to an 'X' and converts the temporary '*' back to 'O'.

Let's walk through an example:

1
2
3X X X X
4X O O X
5X X O X
6X O X X

After enquuing border 'O's:

Queue: (1,3), (3,1)

1
2
3X X X X
4X O O *
5X * O X
6X O X X

After marking all 'O's reachable from border 'O's:

1
2
3X X X X
4X * * *
5X * O X
6X O X X

After traversing entire board converting remaining 'O's to 'X' and '*' back to 'O':

1
2
3X X X X
4X X X X
5X X X X
6X O X X

C++ Solution

1
2c++
3class Solution {
4 public:
5  void solve(vector<vector<char>>& board) {
6    if (board.empty())
7      return;
8    const int m = board.size();
9    const int n = board[0].size();
10    const vector<int> dirs{0, 1, 0, -1, 0};
11    queue<pair<int, int>> q;
12
13    // check borders for O's
14    for (int i = 0; i < m; ++i)
15      for (int j = 0; j < n; ++j)
16        if (i * j == 0 || i == m - 1 || j == n - 1)
17          if (board[i][j] == 'O') {
18            q.emplace(i, j);
19            board[i][j] = '*';    // mark border O's as *
20          }
21
22    // BFS algorithm for traversing the grid and finding O's
23    while (!q.empty()) {
24      auto [i, j] = q.front();
25      q.pop();
26      for (int k = 0; k < 4; ++k) {
27        const int x = i + dirs[k];
28        const int y = j + dirs[k + 1];
29        // boundary checking
30        if (x < 0 || x == m || y < 0 || y == n)
31          continue;
32        if (board[x][y] != 'O')
33          continue;  // continue if not an O
34        q.emplace(x, y);
35        board[x][y] = '*';  // mark reachable O's as *
36      }
37    }
38
39    // traverse board converting O's to X's and *'s back to O's
40    for (vector<char>& row : board)
41      for (char& c : row)
42        if (c == '*')
43          c = 'O';
44        else if (c == 'O')
45          c = 'X';
46  }
47};

Java, Python, JavaScript, and C# solutions have been omitted due to the instruction stating that the solution should be written in C++.# Python Solution

1
2python 
3class Solution:
4    def solve(self, board):
5        if not board or not board[0]: 
6            return
7        self.ROWS, self.COLS = len(board), len(board[0])
8        self.board = board
9        borders = [ij for k in range(max(self.ROWS, self.COLS)) for ij in ((0, k), (k, 0), (self.ROWS - 1, k), (k, self.COLS - 1))]
10        for row, col in borders:
11            self.DFS(row, col)
12        for r in range(self.ROWS):
13            for c in range(self.COLS):
14                if self.board[r][c] == 'O':   
15                    self.board[r][c] = 'X'  
16                elif self.board[r][c] == 'E': 
17                    self.board[r][c] = 'O'  
18        
19    def DFS(self, row, col):
20        if row < 0 or col < 0 or row == self.ROWS or col == self.COLS or\
21                self.board[row][col] != 'O':
22            return
23        self.board[row][col] = 'E'
24        self.DFS(row - 1, col)
25        self.DFS(row + 1, col)
26        self.DFS(row, col - 1)
27        self.DFS(row, col + 1)

JavaScript Solution

1
2javascript
3var solve = function(board) {
4    if(board.length <= 2 || board[0].length <= 2) return;
5    let rows = board.length;
6    let cols = board[0].length;
7    const dfs = (i, j) => {
8        if(i<0 || j<0 || i>=rows || j>=cols || board[i][j] !== 'O') return;
9        board[i][j] = '1';
10        dfs(i+1,j);
11        dfs(i-1,j);
12        dfs(i,j+1);
13        dfs(i,j-1);
14    }
15    for(let i=0;i<rows;i++){
16        for(let j=0;j<cols;j++){
17            if(i===0 || j===0 || i===rows-1 || j===cols-1){
18                dfs(i,j);
19            }
20        }
21    }
22    for(let i=0;i<rows;i++){
23        for(let j=0;j<cols;j++){
24            if(board[i][j] === 'O') board[i][j] = 'X';
25            else if(board[i][j] === '1') board[i][j] = 'O';
26        }
27    }
28    return board;
29};

Java Solution

1
2java
3class Solution {
4    public void solve(char[][] board) {
5        if (board == null || board.length == 0) return;
6        int m = board.length, n = board[0].length;
7        for (int i = 0; i < m; i++) {
8            if (board[i][0] == 'O') explore(board, i, 0);
9            if (board[i][n - 1] == 'O') explore(board, i, n - 1);
10        }
11        for (int j = 0; j < n; j++) {
12            if (board[0][j] == 'O') explore(board, 0, j);
13            if (board[m - 1][j] == 'O') explore(board, m - 1, j);
14        }
15        for (int i = 0; i < m; i++)
16            for (int j = 0; j < n; j++)
17                if (board[i][j] == 'O') board[i][j] = 'X';
18                else if (board[i][j] == '*') board[i][j] = 'O';
19    }
20    void explore(char[][] board, int i, int j) {
21        if (i >= 0 && j >= 0 && i < board.length && j < board[0].length && board[i][j] == 'O') {
22            board[i][j] = '*';
23            explore(board, i - 1, j);
24            explore(board, i + 1, j);
25            explore(board, i, j - 1);
26            explore(board, i, j + 1);
27        }
28    }
29}



These programming solutions in python, JavaScript, and Java show the different ways to implement the solution using different programming languages and their unique syntax, but they all follow the same solution and approach to solve the problem as described above. ‍ In these solutions, we start by looking at the border cells, and if any of them are 'O's, we initiate a depth/breadth-first search to locate all cells connected to these 'O's and mark them. After this step, we iterate through the entire board again to flip the remaining 'O's to 'X's and turn the marked cells back to 'O's.