11.Surrounded Regions
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.
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
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.
Solution : (BFS)
Approach: Iterate all the edges and mark all the '0' connected with the edges Mark all the rest '0' as 'X'
class Solution
{
public:
void bfs(vector<vector<char>> &board, int a, int b)
{
int n = board.size();
int m = board[0].size();
queue<pair<int, int>> q;
board[a][b] = '1';
q.push({a, b});
while (!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
if (j - 1 >= 0 && board[i][j - 1] == 'O')
{
q.push({i, j - 1});
board[i][j - 1] = '1';
}
if (j + 1 <= m - 1 && board[i][j + 1] == 'O')
{
q.push({i, j + 1});
board[i][j + 1] = '1';
}
if (i - 1 >= 0 && board[i - 1][j] == 'O')
{
q.push({i - 1, j});
board[i - 1][j] = '1';
}
if (i + 1 <= n - 1 && board[i + 1][j] == 'O')
{
q.push({i + 1, j});
board[i + 1][j] = '1';
}
}
return;
}
void solve(vector<vector<char>> &board)
{
int n = board.size();
if (n == 0)
{
return;
}
int m = board[0].size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
{
if (board[i][j] == 'O')
{
bfs(board, i, j);
}
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == '1')
{
board[i][j] = 'O';
}
else if (board[i][j] == 'O')
{
board[i][j] = 'X';
}
}
}
return;
}
};
Time Complexity: O(N * M)
Last updated
Was this helpful?