首页 > 代码库 > 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 XAfter running your function, the board should be:X X X XX X X XX X X XX O X X
难度：92。这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
这道题首先四个边缘上的‘O’点都不是被surrounded的，这是很直接能看出的，麻烦的是与这些边界上的‘O’点毗邻的其他‘O’点，这些点由于跟边缘上的‘O‘毗邻，所以也米有被‘X’包裹住。所以我们的想法是：把边界上的‘O’点都找出来，对它们做Flood Fill, 把联通的‘O’区域找出来，把这个区域的点统统由‘O’替换为其他字符比如‘$’。这样没有被替换仍旧为‘O’的那些点，就是被‘X’包裹的。这样整体扫描一次，剩下的所有‘O‘都应该被替换成‘X‘，而‘$‘那些最终应该是还原成‘O‘。
复杂度分析上，我们先对边缘做Flood fill算法，因为只有是‘O‘才会进行，而且会被替换成‘#‘，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所以总的时间复杂度是O(m*n)。
空间上没懂，看了别人的思路。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）
1 public class Solution { 2 public void solve(char[][] board) { 3 if (board==null || board.length==0 || board[0].length==0) return; 4 for (int i=0; i<board[0].length; i++) { 5 if (board[0][i] == ‘O‘) { 6 board[0][i] = ‘$‘; 7 floodFill(board, 0*board[0].length+i); 8 } 9 if (board[board.length-1][i] == ‘O‘) {10 board[board.length-1][i] = ‘$‘;11 floodFill(board, (board.length-1)*board[0].length+i);12 }13 }14 for (int i=0; i<board.length; i++) {15 if (board[i][0] == ‘O‘) {16 board[i][0] = ‘$‘;17 floodFill(board, i*board[0].length+0);18 }19 if (board[i][board[0].length-1] == ‘O‘) {20 board[i][board[0].length-1] = ‘$‘;21 floodFill(board, i*board[0].length+board[0].length-1);22 }23 }24 25 for (int i=0; i<board.length; i++) {26 for (int j=0; j<board[0].length; j++) {27 if (board[i][j] == ‘X‘) continue;28 if (board[i][j] == ‘$‘) {29 board[i][j] = ‘O‘;30 }31 else if (board[i][j] == ‘O‘) {32 board[i][j] = ‘X‘;33 }34 }35 }36 }37 38 public void floodFill(char[][] board, int num) {39 LinkedList<Integer> queue = new LinkedList<Integer>();40 queue.add(num);41 while (queue.size() !=0) {42 int temp = queue.poll();43 int row = temp/board[0].length;44 int col = temp%board[0].length;45 if (row<board.length-1 && board[row+1][col]==‘O‘) {46 board[row+1][col] = ‘$‘;47 queue.add((row+1)*board[0].length + col);48 }49 if (row>0 && board[row-1][col]==‘O‘) {50 board[row-1][col] = ‘$‘;51 queue.add((row-1)*board[0].length + col);52 }53 if (col<board[0].length-1 && board[row][col+1]==‘O‘) {54 board[row][col+1] = ‘$‘;55 queue.add(row*board[0].length + col + 1);56 }57 if (col>0 && board[row][col-1]==‘O‘) {58 board[row][col-1] = ‘$‘;59 queue.add(row*board[0].length + col - 1);60 }61 }62 }63 }
Leetcode: Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。