首页 > 代码库 > [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
Solution:
通过对四条边上的点进行遍历来判断边缘上是否有‘O’，
1. 如果四条边上都没有‘O’，说明‘O‘(如果有)都被‘X‘给包围了，遍历整个二维数组直接将‘O’改为‘X’即可。
2. 如果发现了‘O’，沿着该‘O’的上下左右方向，分别判断是否是‘O’，如果是，加入队列。
public class Solution { public void solve(char[][] board) { if (board == null || board.length == 0) return; if (board[0].length == 0) return; int row = board.length; int col = board[0].length; for (int i = 0; i < row; ++i) { bfs(board, i, 0); bfs(board, i, col - 1); } for (int i = 1; i < col - 1; ++i) { bfs(board, 0, i); bfs(board, row - 1, i); } for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (board[i][j] == ‘O‘) board[i][j] = ‘X‘; } } for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (board[i][j] == ‘D‘) board[i][j] = ‘O‘; } } } private void bfs(char[][] board, int x, int y) { if(board[x][y]!=‘O‘) return; board[x][y]=‘D‘; Queue<Integer> queue=new LinkedList<Integer>(); queue.add(x*board[0].length+y); while (!queue.isEmpty()) { int code=queue.poll(); int row=code/board[0].length; int col=code%board[0].length; if(row-1>=0&&board[row-1][col]==‘O‘){ queue.add((row-1)*board[0].length+col); board[row-1][col]=‘D‘; } if(row+1<board.length&&board[row+1][col]==‘O‘){ queue.add((row+1)*board[0].length+col); board[row+1][col]=‘D‘; } if(col-1>=0&&board[row][col-1]==‘O‘){ queue.add(row*board[0].length+col-1); board[row][col-1]=‘D‘; } if(col+1<board[0].length&&board[row][col+1]==‘O‘){ queue.add(row*board[0].length+col+1); board[row][col+1]=‘D‘; } } }}
[Leetcode] Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。