Surrounded Regions

                                            
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty()) {
            return;
        }

        int rows = board.size();
        int cols = board[0].size();

        queue<pair<int, int>> q;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();

            if (i >= 0 && i < rows && j >= 0 && j < cols && board[i][j] == 'O') {
                board[i][j] = 'B';

                q.push({i - 1, j});
                q.push({i + 1, j});
                q.push({i, j - 1});
                q.push({i, j + 1});
            }
        }

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'B') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

                                            
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = '*';
        
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

                                            
class Solution(object):
    def solve(self, board):
        def dfs(i, j):
            if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == 'O':
                board[i][j] = 'S'
                dfs(i+1, j)
                dfs(i-1, j)
                dfs(i, j+1)
                dfs(i, j-1)
        
        if not board or not board[0]:
            return
        
        rows, cols = len(board), len(board[0])
        
        for i in range(rows):
            dfs(i, 0)
            dfs(i, cols-1)
        
        for j in range(cols):
            dfs(0, j)
            dfs(rows-1, j)
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'S':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'

                                            
void solve(char** board, int boardSize, int* boardColSize) {
    
    if (board == NULL || boardSize == 0 || *boardColSize == 0) {
        return;
    }
    
    // Helper function to mark 'O's connected to border as safe
    void markSafe(int row, int col) {
        if (row < 0 || row >= boardSize || col < 0 || col >= *boardColSize || board[row][col] != 'O') {
            return;
        }
        
        board[row][col] = 'S'; // Mark as safe
        
        markSafe(row - 1, col); // Check North
        markSafe(row + 1, col); // Check South
        markSafe(row, col - 1); // Check West
        markSafe(row, col + 1); // Check East
    }
    
    // Mark 'O's connected to border as safe starting from border cells
    for (int i = 0; i < boardSize; i++) {
        markSafe(i, 0); // Left border
        markSafe(i, *boardColSize - 1); // Right border
    }
    
    for (int j = 0; j < *boardColSize; j++) {
        markSafe(0, j); // Top border
        markSafe(boardSize - 1, j); // Bottom border
    }
    
    // Flip 'O's to 'X's and revert 'S's back to 'O's
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < *boardColSize; j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == 'S') {
                board[i][j] = 'O';
            }
        }
    }
}

                                            
public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) return;
        
        int rows = board.Length;
        int cols = board[0].Length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
                    DFS(board, i, j);
                }
            }
        }
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '1') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void DFS(char[][] board, int i, int j) {
        if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = '1';
        DFS(board, i + 1, j);
        DFS(board, i - 1, j);
        DFS(board, i, j + 1);
        DFS(board, i, j - 1);
    }
}

                                            
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place 
instead.
 */
var solve = function(board) {
    const dfs = (i, j) => {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== 'O') {
            return;
        }
        
        board[i][j] = '-';
        
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };
    
    const rows = board.length;
    const cols = board[0].length;
    
    for (let i = 0; i < rows; i++) {
        dfs(i, 0);
        dfs(i, cols - 1);
    }
    
    for (let j = 0; j < cols; j++) {
        dfs(0, j);
        dfs(rows - 1, j);
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] === '-') {
                board[i][j] = 'O';
            }
        }
    }
};

                                            
/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
    const dfs = (i: number, j: number) => {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== 'O') {
            return;
        }
        
        board[i][j] = 'T'; // Temporarily mark 'O' as 'T'
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };
    
    const m = board.length;
    const n = board[0].length;
    
    for (let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    
    for (let j = 0; j < n; j++) {
        dfs(0, j);
        dfs(m - 1, j);
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] === 'T') {
                board[i][j] = 'O';
            }
        }
    }
};

                                            
class Solution {
    /**
     * @param String[][] $board
     * @return NULL
     */
    function solve(&$board) {
        $rows = count($board);
        $cols = count($board[0]);
        
        for ($i = 0; $i < $rows; $i++) {
            for ($j = 0; $j < $cols; $j++) {
                if (($i == 0 || $i == $rows - 1 || $j == 0 || $j == $cols - 1) && $board[$i][$j] == 'O') {
                    $this->dfs($board, $i, $j);
                }
            }
        }
        
        for ($i = 0; $i < $rows; $i++) {
            for ($j = 0; $j < $cols; $j++) {
                if ($board[$i][$j] == 'O') {
                    $board[$i][$j] = 'X';
                } elseif ($board[$i][$j] == '#') {
                    $board[$i][$j] = 'O';
                }
            }
        }
    }
    
    function dfs(&$board, $i, $j) {
        if ($i < 0 || $i >= count($board) || $j < 0 || $j >= count($board[0]) || $board[$i][$j] != 'O') {
            return;
        }
        
        $board[$i][$j] = '#';
        
        $this->dfs($board, $i + 1, $j);
        $this->dfs($board, $i - 1, $j);
        $this->dfs($board, $i, $j + 1);
        $this->dfs($board, $i, $j - 1);
    }
}

                                            
class Solution {
    func solve(_ board: inout [[Character]]) {
        let rows = board.count
        let cols = board[0].count
        
        func dfs(_ i: Int, _ j: Int) {
            if i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != "O" {
                return
            }
            
            board[i][j] = "#"
            
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        }
        
        // Iterate over the borders and mark the connected 'O's as safe
        for i in 0..<rows {
            dfs(i, 0)
            dfs(i, cols - 1)
        }
        
        for j in 0..<cols {
            dfs(0, j)
            dfs(rows - 1, j)
        }
        
        // Flip 'O's to 'X's and restore '#' to 'O'
        for i in 0..<rows {
            for j in 0..<cols {
                if board[i][j] == "O" {
                    board[i][j] = "X"
                } else if board[i][j] == "#" {
                    board[i][j] = "O"
                }
            }
        }
    }
}

                                            
class Solution {
    fun solve(board: Array<CharArray>): Unit {
        fun dfs(board: Array<CharArray>, i: Int, j: Int) {
            if (i < 0 || j < 0 || i >= board.size || j >= board[0].size || board[i][j] != 'O') return
            board[i][j] = 'Y'
            dfs(board, i + 1, j)
            dfs(board, i - 1, j)
            dfs(board, i, j + 1)
            dfs(board, i, j - 1)
        }
        
        for (i in board.indices) {
            for (j in board[i].indices) {
                if ((i == 0 || j == 0 || i == board.size - 1 || j == board[i].size - 1) && board[i][j] == 'O') {
                    dfs(board, i, j)
                }
            }
        }
        
        for (i in board.indices) {
            for (j in board[i].indices) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X'
                } else if (board[i][j] == 'Y') {
                    board[i][j] = 'O'
                }
            }
        }
    }
}

                                            
class Solution {
  void solve(List<List<String>> board) {
      if (board.isEmpty) return;
      
      int rows = board.length;
      int cols = board[0].length;
      
      for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
          if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
            _dfs(board, i, j);
          }
        }
      }
      
      for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
          if (board[i][j] == 'O') {
            board[i][j] = 'X';
          } else if (board[i][j] == '#') {
            board[i][j] = 'O';
          }
        }
      }
    }
    
    void _dfs(List<List<String>> board, int i, int j) {
      if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
        return;
      }
      
      board[i][j] = '#';
      _dfs(board, i + 1, j);
      _dfs(board, i - 1, j);
      _dfs(board, i, j + 1);
      _dfs(board, i, j - 1);
    }
}

                                            
func solve(board [][]byte) {
    if len(board) == 0 {
        return
    }
    
    m, n := len(board), len(board[0])
    
    var dfs func(int, int)
    dfs = func(i, j int) {
        if i < 0 || j < 0 || i >= m || j >= n || board[i][j] != 'O' {
            return
        }
        
        board[i][j] = 'A'
        
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    }
    
    for i := 0; i < m; i++ {
        dfs(i, 0)
        dfs(i, n-1)
    }
    for j := 0; j < n; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == 'A' {
                board[i][j] = 'O'
            }
        }
    }
}

                                            
# @param {Character[][]} board
# @return {Void} Do not return anything, modify board in-place instead.
def solve(board)
    if board.empty? || board[0].empty?
        return
    end

    rows, cols = board.length, board[0].length

    for i in 0..rows-1
        dfs(board, i, 0)
        dfs(board, i, cols-1)
    end

    for j in 0..cols-1
        dfs(board, 0, j)
        dfs(board, rows-1, j)
    end

    for i in 0..rows-1
        for j in 0..cols-1
            if board[i][j] == 'O'
                board[i][j] = 'X'
            elsif board[i][j] == 'E'
                board[i][j] = 'O'
            end
        end
    end
end

def dfs(board, i, j)
    if i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O'
        return
    end

    board[i][j] = 'E'

    dfs(board, i+1, j)
    dfs(board, i-1, j)
    dfs(board, i, j+1)
    dfs(board, i, j-1)
end

                                            
object Solution {
    def solve(board: Array[Array[Char]]): Unit = {
        def dfs(board: Array[Array[Char]], i: Int, j: Int): Unit = {
            if (i < 0 || i >= board.length || j < 0 || j >= board(0).length || board(i)(j) != 'O') {
                return
            }
            board(i)(j) = '#'
            dfs(board, i + 1, j)
            dfs(board, i - 1, j)
            dfs(board, i, j + 1)
            dfs(board, i, j - 1)
        }

        for (i <- board.indices) {
            dfs(board, i, 0)
            dfs(board, i, board(0).length - 1)
        }
        for (j <- board(0).indices) {
            dfs(board, 0, j)
            dfs(board, board.length - 1, j)
        }

        for {
            i <- board.indices
            j <- board(0).indices
        } yield {
            board(i)(j) match {
                case 'O' => board(i)(j) = 'X'
                case '#' => board(i)(j) = 'O'
                case _ =>
            }
        }
    }
}

                                            
impl Solution {
    pub fn solve(board: &mut Vec<Vec<char>>) {
        let m = board.len();
        let n = board[0].len();
        
        for i in 0..m {
            for j in 0..n {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O' {
                    Self::dfs(board, i as i32, j as i32);
                }
            }
        }
        
        for i in 0..m {
            for j in 0..n {
                if board[i][j] == 'O' {
                    board[i][j] = 'X';
                } else if board[i][j] == '*' {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    fn dfs(board: &mut Vec<Vec<char>>, i: i32, j: i32) {
        if i < 0 || i >= board.len() as i32 || j < 0 || j >= board[0].len() as i32 || board[i as usize][j as usize] != 'O' {
            return;
        }
        
        board[i as usize][j as usize] = '*';
        
        Self::dfs(board, i - 1, j);
        Self::dfs(board, i + 1, j);
        Self::dfs(board, i, j - 1);
        Self::dfs(board, i, j + 1);
    }
}

To solve this coding challenge involving surrounded regions in an m x n board containing 'X' and 'O', we'll use a Depth-First Search (DFS) approach. Through DFS, we'll identify and mark the 'O's that are connected to the border and hence should not be flipped. The rest of the 'O's will be converted to 'X's.

Explanation

The challenge requires that any 'O' not on the border and not connected to an 'O' on the border be flipped to 'X'. Here's a detailed approach to achieve this:

Initialization :

If the board is empty, simply return.
Determine the number of rows and columns in the board.

DFS Marking :

We will define a DFS function that marks 'O's connected to the border with a temporary character, say 'S'.
Traverse through the border of the board and apply the DFS function to mark all 'O's connected to the border.

Region Conversion :

Iterate through the entire board. If a cell contains 'O', it means it's surrounded and will be converted to 'X'.
If a cell contains 'S', change it back to 'O' since it was originally connected to the border.

This solution ensures that all surrounded regions are accurately captured.

Let's break this down into pseudocode with detailed comments to illustrate each step.

Pseudocode

Step 1: Initialization

                                            
# Check if the board is empty, if so, return immediately
if board is empty:
return

# Determine the number of rows and columns
number_of_rows = length of board
number_of_columns = length of the first row in board

Step 2: Define the DFS Function

                                            
# Define the DFS function to mark connected 'O's with 'S'
function dfs(row, col):
# Check for base cases: if index is out of bounds or the cell is not 'O'
if row is out of bounds or col is out of bounds or board[row][col] is not 'O':
return

# Mark the cell as 'S' to identify it as connected to the border
board[row][col] = 'S'

# Explore all 4-directionally connected neighbors
dfs(row + 1, col)  # down
dfs(row - 1, col)  # up
dfs(row, col + 1)  # right
dfs(row, col - 1)  # left

Step 3: Mark Border-Connected 'O's

                                            
# Traverse and apply DFS to all 'O's on the border rows and columns
for each row from 0 to number_of_rows - 1:
dfs(row, 0)                   # First column
dfs(row, number_of_columns-1) # Last column

for each column from 0 to number_of_columns - 1:
dfs(0, column)                # First row
dfs(number_of_rows-1, column) # Last row

Step 4: Convert Regions

                                            
# Iterate through the entire board to convert the regions
for each row from 0 to number_of_rows - 1:
for each column from 0 to number_of_columns - 1:
if cell contains 'O':
# This 'O' is surrounded and should be flipped to 'X'
board[row][col] = 'X'
else if cell contains 'S':
# This 'O' was connected to the border, revert it back to 'O'
board[row][col] = 'O'

Step-by-Step Explanation of Detailed Steps in Pseudocode

Initialization :

Check if the board is empty and return if so to avoid any further errors.
Calculate the number of rows and columns in the board to facilitate navigation.

DFS Function :

This function helps mark all connected 'O's starting from any given cell (row, col).
If the cell is out of bounds or is not an 'O', the function returns.
Otherwise, mark the cell as 'S' (a placeholder to indicate it's connected to the border) and recursively apply DFS in all four directions.

Mark Border-Connected 'O's :

Apply the DFS function to all border cells (both on rows and columns).
This step ensures all border-connected 'O's are marked with 'S'.

Convert the Regions :

Iterate through every cell in the board.
Convert 'O's (that are not marked) to 'X' since they are surrounded.
Revert the 'S' cells back to 'O' as they represent the border-connected regions.

This method ensures an optimal approach to solving the problem within the constraints provided.