Given a 2D board containing ‘X‘ and ‘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
This is a simple problem, we just need to apply bfs on ‘O‘ elements on the edges of board.
public class Solution {
public void solve(char[][] board) {
int row = board.length;
if(row > 0){
int column = board[0].length;
Set<Integer> alreadyChecked = new HashSet<Integer>();
for(int i = 0; i < column; ++i){
if(board[0][i] == ‘O‘ && !alreadyChecked.contains(i))
bfs(board,0, i, alreadyChecked);
if(board[row - 1][i] == ‘O‘ && !alreadyChecked.contains((row - 1) * column + i))
bfs(board,row - 1, i, alreadyChecked);
}
for(int i = 1; i < row - 1; ++i){
if(board[i][0] == ‘O‘ && !alreadyChecked.contains(i * column))
bfs(board,i, 0, alreadyChecked);
if(board[i][column - 1] == ‘O‘ && !alreadyChecked.contains(i * column + column - 1))
bfs(board,i, column - 1, alreadyChecked);
}
for(int i = 0; i < row; ++i){
for(int j = 0; j < column; ++j){
if(board[i][j] == ‘O‘ && !alreadyChecked.contains(i*column + j))
board[i][j] = ‘X‘;
}
}
}
}
private void bfs(char[][] board, int i, int j, Set<Integer> alreadyChecked) {
int row = board.length;
if(row > 0){
int column = board[0].length;
if(!alreadyChecked.contains(i * column + j)) {
Queue<Integer> current = new LinkedList<Integer>();
alreadyChecked.add(i * column + j);
current.add(i * column + j);
while(current.peek() != null){
int currentCoordinate = current.poll();
int x = currentCoordinate / column;
int y = currentCoordinate % column;
if(x - 1 >= 0 && board[x - 1][y] == ‘O‘ && !alreadyChecked.contains(currentCoordinate - column)){
current.add(currentCoordinate - column);
alreadyChecked.add(currentCoordinate - column);
}
if(x + 1 < row && board[x + 1][y] == ‘O‘ && !alreadyChecked.contains(currentCoordinate + column)){
current.add(currentCoordinate + column);
alreadyChecked.add(currentCoordinate + column);
}
if(y - 1 >= 0 && board[x][y - 1] == ‘O‘ && !alreadyChecked.contains(currentCoordinate - 1)) {
current.add(currentCoordinate - 1);
alreadyChecked.add(currentCoordinate - 1);
}
if(y + 1 < column && board[x][y + 1] == ‘O‘ && !alreadyChecked.contains(currentCoordinate + 1)) {
current.add(currentCoordinate + 1);
alreadyChecked.add(currentCoordinate + 1);
}
}
}
}
}
}
leetcode--Surrounded Regions,布布扣,bubuko.com
原文：http://www.cnblogs.com/averillzheng/p/3825371.html