首页 > 代码库 > LeetCode: Surrounded Regions 解题报告
LeetCode: Surrounded Regions 解题报告
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 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
SOLUTION 1:
经典 BFS 题目。如果使用DFS，会超时。
使用队列进行BFS。注意，在判断index越界时，主页君写了2种方法。
（1）可以直接对index在0-x*y之间取。这里有个小的trick，在点在左边缘的时候，index-1会导致我们回到上一行的最右边。当然那个点也是
边缘点，所以不会造成解的错误。
（2）判断点是不是在边缘，判定上下左右还有没有节点。
常出错的点：计算index是i * cols + j 这点要记好了。
1 public class Solution { 2 public void solve(char[][] board) { 3 if (board == null || board.length == 0 || board[0].length == 0) { 4 return; 5 } 6 7 int rows = board.length; 8 int cols = board[0].length; 9 10 // the first line and the last line. 11 for (int j = 0; j < cols; j++) { 12 bfs(board, 0, j); 13 bfs(board, rows - 1, j); 14 } 15 16 // the left and right column 17 for (int i = 0; i < rows; i++) { 18 bfs(board, i, 0); 19 bfs(board, i, cols - 1); 20 } 21 22 // capture all the nodes. 23 for (int i = 0; i < rows; i++) { 24 for (int j = 0; j < cols; j++) { 25 if (board[i][j] == ‘O‘) { 26 board[i][j] = ‘X‘; 27 } else if (board[i][j] == ‘B‘) { 28 board[i][j] = ‘O‘; 29 } 30 } 31 } 32 33 return; 34 } 35 36 public void bfs1(char[][] board, int i, int j) { 37 int rows = board.length; 38 int cols = board[0].length; 39 40 Queue<Integer> q = new LinkedList<Integer>(); 41 q.offer(i * cols + j); 42 43 while (!q.isEmpty()) { 44 int index = q.poll(); 45 46 // Index is out of bound. 47 if (index < 0 || index >= rows * cols) { 48 continue; 49 } 50 51 int x = index / cols; 52 int y = index % cols; 53 54 if (board[x][y] != ‘O‘) { 55 continue; 56 } 57 58 board[x][y] = ‘B‘; 59 q.offer(index + 1); 60 q.offer(index - 1); 61 q.offer(index + cols); 62 q.offer(index - cols); 63 } 64 } 65 66 public void bfs(char[][] board, int i, int j) { 67 int rows = board.length; 68 int cols = board[0].length; 69 70 Queue<Integer> q = new LinkedList<Integer>(); 71 q.offer(i * cols + j); 72 73 while (!q.isEmpty()) { 74 int index = q.poll(); 75 76 int x = index / cols; 77 int y = index % cols; 78 79 if (board[x][y] != ‘O‘) { 80 continue; 81 } 82 83 board[x][y] = ‘B‘; 84 if (y < cols - 1) { 85 q.offer(index + 1); 86 } 87 88 if (y > 0) { 89 q.offer(index - 1); 90 } 91 92 if (x > 0) { 93 q.offer(index - cols); 94 } 95 96 if (x < rows - 1) { 97 q.offer(index + cols); 98 } 99 }100 }101 }
SOLUTION 2:
附上DFS解法：
1 public void dfs(char[][] board, int i, int j) { 2 int rows = board.length; 3 int cols = board[0].length; 4 5 // out of bound or visited. 6 if (i < 0 || i >= rows || j < 0 || j >= cols) { 7 return; 8 } 9 10 if (board[i][j] != ‘O‘) {11 return;12 }13 14 board[i][j] = ‘B‘;15 16 // dfs the sorrounded regions.17 dfs(board, i + 1, j);18 dfs(board, i - 1, j);19 dfs(board, i, j + 1);20 dfs(board, i, j - 1);21 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/bfs/Solve.java
LeetCode: Surrounded Regions 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。