# Surrounded Regions ## Problem Statement Given a 2D board containing `'X'` and `'O'` (**the letter O**), capture all regions surrounded by `'X'`. A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region. Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically. ## Testcases ``` Example 1: Input: X X X X X O O X X X O X X O X X Output: X X X X X X X X X X X X X O X X Explanation: Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically. ``` ## Problem Explanation In this problem, we must analyse the condition which allows a cell to be converted from `'O'` to `'X'`. According to the problem, if a cell on the border (row or column) is an `'O'` then it cannot be converted to `'X'`. The problem also stipulates that if a cell with an `'O'` is connected to a border cell with an `'O'` then it cannot be converted to `'X'`either. **Example**: In the first example, none of the cells with `'O'` can be converted to `'X'`. This is because the cell at position `[1][2]` contains an `'O'` and is on the border of the board. The other cells which contain an `'O'` are connected to this cell, so according to the given constraints, these cells cannot be converted to `'X'`. Therefore, if a chain of adjacent `'O's` are connected to an `'O'` on a boundary, then it cannot be converted. {% code title="'O' cannot be converted to 'X'" %} ``` [X O X X X] [X O O O X] [X O X X X] [X X X X X] ``` {% endcode %} In this example, the cells containing an `'O'` are not located on the border of the board so the cells can be converted to `'X'`. {% code title="'O' can be converted to 'X'" %} ``` [X X X X X] [X O O O X] [X O X X X] [X X X X X] ``` {% endcode %} ## Prerequisite Knowledge ### Depth-First-Search The Depth-First-Search (DFS) algorithm is used to traverse or search for elements in a tree or graph. The traversal takes place in a depth-wise manner such that we start at a particular node and travel as far as possible down the particular branch associated with that node before *backtracking* and traversing through the remaining branches. The basic idea behind DFS is to start from the root node or any arbitrary node and mark the node as visited. Then, we move to the adjacent unmarked node and continue this process until there is no unmarked adjacent node remaining. We then backtrack and check for other unmarked nodes and traverse through them. Finally, the nodes that have been traversed in the path will be printed. {% code title="Algorithm" %} ``` Create a recursive function that takes the index of node and a visited array. Mark the current node as visited and print the node. Traverse all the adjacent and unmarked nodes and call the recursive function with index of adjacent node. ``` {% endcode %} ![Source: https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-MA72cye5AZawUlFFKVd%2F-MA77DPgKQLgCWHL3fNI%2Fdfs.jpg?alt=media\&token=a4eaf874-81c0-4654-9065-a191f1ccb212) ## Algorithm ### Depth-First-Search Approach 1. Iterate over the row and column boundaries of the board until an 'O' is encountered. 2. Perform depth-first-search using the DFS helper function every time an 'O' is encountered, from its position. 3. Convert all of the encountered 'O's during the DFS operation to '#' in order to mark the cells that cannot be converted to 'X'. 4. When the DFS has been completed, there are three elements remaining on the board: a. 'X' - Do not make any changes. b. 'O' - Convert to 'X', since they are not connected to any boundary and therefore can be converted to 'X'. c. '#' - Convert back to 'O' since they are connected to some boundary and therefore cannot be converted to 'X'. {% hint style="info" %} Time Complexity: O(MN) {% endhint %} ## Code {% code title="DFS Helper Function" %} ```cpp void check(vector>& board, int i, int j, int row, int col) { // Invalid conditions if(i < 0 || j < 0 || i >= row || j >= col || board[i][j] != 'O') return; // Cells with the value '#' cannot be converted to 'O' board[i][j] = '#'; // Check all adjacent cells check(board, i - 1, j, row, col); check(board, i + 1, j, row, col); check(board, i, j - 1, row, col); check(board, i, j + 1, row, col); } ``` {% endcode %} {% code title="Solve Board Function" %} ```cpp void solve(vector>& board) { int row = board.size(); // Empty board if(row == 0) return; int col = board[0].size(); // Border column check for(int i = 0; i < row; i++) { // Move over the first column if(board[i][0] == 'O') { check(board, i, 0, row, col); } // Move over the last column if(board[i][col - 1] == 'O') { check(board, i, col - 1, row, col); } } // Border row check for(int j = 0; j < col; j++) { // Move over the first row if(board[0][j] == 'O') { check(board, 0, j, row, col); } // Move over the last row if(board[row - 1][j] == 'O') { check(board, row - 1, j, row, col); } } // Convert to 'X' for(int i = 0; i < row; i++) { for(int j = 0; j < col; j++) { // If the cell has remained as 'O', we can convert to 'X' if(board[i][j] == 'O') { board[i][j] = 'X'; } // If the cell has changed to '#', we cannot convert to 'X' if(board[i][j] == '#') { board[i][j] = 'O'; } } } } ``` {% endcode %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-3/surrounded-regions.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.