# Solution For Surrounded Regions

Surrounded Regions problem on leetcode:

Given an m x n matrix board containing ‘X’ and ‘O’, flip all ‘O’s which are surrounded by ‘X’s to ‘X’.

A region is considered to be surrounded by ‘X’s if all the cells in the region that are in the border of the matrix are ‘X’s.

Example:

Input: board = [

[‘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’ from the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Approach:

1. We will be using a DFS traversal to find all the ‘O’s which are not surrounded by ‘X’s.

2. First, we initialize the borders of the matrix and add them to the queue. We won’t be changing any ‘O’ on the borders. If any ‘O’ is found on the borders, we can assume it is not surrounded by ‘X’s.

3. We traverse every cell in the matrix and if ‘O’ is found, we push it to the queue and mark it as ‘visited’ by changing it to ‘N’ (because it will now be surrounded by ‘X’s).

4. Now, we will run a DFS until the queue is empty. In the DFS function, for every ‘O’ present in the queue, we will mark it as ‘visited’ by changing it to ‘N’ (because it will now be surrounded by ‘X’s) and add its neighbouring cells to the queue.

5. After the DFS is completed, we iterate through the matrix again and change all ‘O’s to ‘X’s and all ‘N’s to ‘O’s.

Code:

class Solution {

public:

void solve(vector

int m = board.size();

if(m==0) return;

int n = board[0].size();

queue

// Adding elements on the borders to the queue

for(int i=0;i<m;i++){

if(board[i][0] == ‘O’) q.push(make_pair(i,0));

if(board[i][n-1] == ‘O’) q.push(make_pair(i,n-1));

}

for(int j=0;j

q.pop();

int x = curr.first, y = curr.second;

if(x>=0 && x

board[x][y] = ‘N’; // Marking all ‘O’ as ‘N’ as it is no longer surrounded by ‘X’

q.push(make_pair(x-1,y)); // Up

q.push(make_pair(x+1,y)); // Down

q.push(make_pair(x,y-1)); // Left

q.push(make_pair(x,y+1)); // Right

}

}

// Changing all ‘O’ to ‘X’ and all ‘N’ to ‘O’

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] == ‘N’) board[i][j] = ‘O’;

}

}

}

};

Time complexity: O(m*n) as we are iterating through every cell in the matrix.

Space complexity: O(m+n) as the maximum size of the queue can be m+n (for a boundary cell).

## Step by Step Implementation For Surrounded Regions

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++) { for (int j = 0; j < n; j++) { // start from the edges and use dfs to mark all the connected 'O's as '#' if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') { dfs(board, i, j); } } } // flip all the 'O's to 'X's and all the '#'s to 'O's 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 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') { return; } // mark the current cell as '#' board[i][j] = '#'; // check all the adjacent cells dfs(board, i + 1, j); dfs(board, i - 1, j); dfs(board, i, j + 1); dfs(board, i, j - 1); } }

class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ #Base case if not board: return #Get the dimensions of the board rows = len(board) cols = len(board[0]) #Create a visited 2D array to keep track of which cells have been visited visited = [[False for i in range(cols)] for j in range(rows)] #Do a DFS from every 'O' cell on the boundary of the board for i in range(rows): for j in range(cols): #If the current cell is 'O' and it's on the boundary of the board, do a DFS from that cell if board[i][j] == 'O' and (i == 0 or j == 0 or i == rows-1 or j == cols-1): self.DFS(board, i, j, visited) #After the DFS, every 'O' cell that was reachable from the boundary will be marked as visited #So, we can now go through the whole board again and change every 'O' cell to 'X' that isn't visited for i in range(rows): for j in range(cols): if board[i][j] == 'O' and not visited[i][j]: board[i][j] = 'X' def DFS(self, board, i, j, visited): #Mark the current cell as visited visited[i][j] = True #Get the dimensions of the board rows = len(board) cols = len(board[0]) #Recursively call DFS on all unvisited 'O' cells reachable from the current cell #(i.e. all 'O' cells that are adjacent to the current cell) if i > 0 and board[i-1][j] == 'O' and not visited[i-1][j]: self.DFS(board, i-1, j, visited) if i < rows-1 and board[i+1][j] == 'O' and not visited[i+1][j]: self.DFS(board, i+1, j, visited) if j > 0 and board[i][j-1] == 'O' and not visited[i][j-1]: self.DFS(board, i, j-1, visited) if j < cols-1 and board[i][j+1] == 'O' and not visited[i][j+1]: self.DFS(board, i, j+1, visited)

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. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X

class Solution { public: void solve(vector>& board) { //check if the first and last row have any 'O's. If they do, change them and all their connected 'O's to '*'s for(int i = 0; i < board.size(); i++){ for(int j = 0; j < board[0].size(); j++){ //if we find an 'O' on the first or last row if((i == 0 || i == board.size() - 1) && board[i][j] == 'O'){ //change it to a '*' board[i][j] = '*'; //call our helper function on this 'O' to change all its connected 'O's to '*'s flip(board, i, j); } } } //check if the first and last column have any 'O's. If they do, change them and all their connected 'O's to '*'s for(int i = 0; i < board.size(); i++){ for(int j = 0; j < board[0].size(); j++){ //if we find an 'O' on the first or last column if((j == 0 || j == board[0].size() - 1) && board[i][j] == 'O'){ //change it to a '*' board[i][j] = '*'; //call our helper function on this 'O' to change all its connected 'O's to '*'s flip(board, i, j); } } } //go through the entire board and change all 'O's to 'X's and all '*'s back to 'O's for(int i = 0; i < board.size(); i++){ for(int j = 0; j < board[0].size(); j++){ if(board[i][j] == 'O'){ board[i][j] = 'X'; } else if(board[i][j] == '*'){ board[i][j] = 'O'; } } } } //a helper function that takes in the board and the coordinates of an 'O'. //It then changes all connected 'O's to '*'s void flip(vector >& board, int i, int j){ //if we are out of bounds or if the current element is not an 'O', return if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){ return; } //change the current element to a '*' board[i][j] = '*'; //call our helper function on all adjacent elements flip(board, i + 1, j); flip(board, i - 1, j); flip(board, i, j + 1); flip(board, i, j - 1); } };

class Solution { public void Solve(char[][] board) { if (board == null || board.Length == 0) return; int m = board.Length, n = board[0].Length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // only consider 'O' on the border bool isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1; if (isEdge && board[i][j] == 'O') { DFS(board, i, j); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } 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] == 'X' || board[i][j] == '#') return; board[i][j] = '#'; DFS(board, i - 1, j); DFS(board, i + 1, j); DFS(board, i, j - 1); DFS(board, i, j + 1); } }