# 130. Surrounded Regions
Question link is here.
# Question
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example 1:
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 should not 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
Simple BFS search, since we need to replace all the region that is not connected to border, we can start the BFS search at each 'O' at border, and turn them into another state '-'.
After the BFS search at all the points on the border, we iterate through the board again, and turn all 'O' into 'X', and all '-' into 'O'
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def bfs(x, y):
queue = []
queue.append((x,y))
directions = [(-1,0), (1, 0), (0, -1), (0, 1)]
while queue:
x, y = queue.pop(0)
board[x][y] = '-'
for _, __ in directions:
nextX = x + _
nextY = y + __
if(nextX >= 0 and nextY >= 0 and nextX < len(board) and nextY < len(board[0]) and board[nextX][nextY] == 'O'):
board[nextX][nextY] = '-'
queue.append((nextX, nextY))
for i in range(len(board[0])):
if board[0][i] == 'O':
bfs(0, i)
if board[len(board)-1][i] == 'O':
bfs(len(board)-1, i)
for i in range(len(board)):
if board[i][0] == 'O':
bfs(i, 0)
if board[i][len(board[0])-1] == 'O':
bfs(i, len(board[0])-1)
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == '-':
board[i][j] = 'O'
class Solution {
public void solve(char[][] board) {
int height = board.length;
int width = board[0].length;
for(int i = 0; i < width; i++) {
if(board[0][i] == 'O') {
bfs(board, 0, i);
}
if(board[height-1][i] == 'O') {
bfs(board, height-1, i);
}
}
for(int i = 0; i < height; i++) {
if(board[i][0] == 'O')
bfs(board, i, 0);
if(board[i][width-1] == 'O') {
bfs(board, i, width-1);
}
}
for(int i = 0; i < height; i++) {
for(int j = 0; j < width; j++) {
if(board[i][j] == 'O')
board[i][j] = 'X';
if(board[i][j] == '-')
board[i][j] = 'O';
}
}
}
public void bfs(char[][] board, int x, int y) {
Queue<Pair<Integer, Integer>> queue = new ArrayDeque();
queue.offer(new Pair(x, y));
int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(queue.size() != 0) {
Pair<Integer, Integer> temp = queue.poll();
x = temp.getKey();
y = temp.getValue();
board[x][y] = '-';
for(int[] d : dir) {
int nextX = x + d[0];
int nextY = y + d[1];
if(nextX >= 0 && nextY >= 0 && nextX < board.length && nextY < board[0].length && board[nextX][nextY] == 'O') {
board[nextX][nextY] = '-';
queue.offer(new Pair(nextX, nextY));
}
}
}
}
}
Time complexity: where n is the number of cells in the board.