首页 > 代码库 > leetcode--Surrounded Regions
leetcode--Surrounded Regions
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 XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX 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); } } } } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。