首页 > 代码库 > 【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 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
参考:http://blog.csdn.net/ojshilu/article/details/22600449#reply
两点:
1、从边缘入手,因为和边缘上的‘O’相连的‘O’都不会变,所以找出所有这样的‘O’,剩下的‘O’就是被完全包围的,把它们全部变为‘X’。
2、DFS过程中,暂时把遍历过的‘O‘用另外一个符号’#‘代替,最后把被包围的’O‘变成’X‘后,在把‘#’恢复成‘O’。
public class Solution { public void solve(char[][] board) { int row = board.length; if (row < 3) return; int col = board[0].length; if (col < 3) return; // first column and last column for (int i = 0; i < row; i++) { if (board[i][0] == 'O') { board[i][0] = '#'; dfs(board, i, 0); } if (board[i][col - 1] == 'O') { board[i][col - 1] = '#'; dfs(board, i, col - 1); } } // first row and last row for (int j = 0; j < col; j++) { if (board[0][j] == 'O') { board[0][j] = '#'; dfs(board, 0, j); } if (board[row - 1][j] == 'O') { board[row - 1][j] = '#'; dfs(board, row - 1, j); } } // change 'O' to 'X', restore '#' to 'O' for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } else if (board[i][j] == '#') { board[i][j] = 'O'; } } } } public void dfs(char[][] board, int i, int j) { int row = board.length; int col = board[0].length; // up if (i > 1 && board[i - 1][j] == 'O') { board[i - 1][j] = '#'; dfs(board, i - 1, j); } // below if (i < row - 2 && board[i + 1][j] == 'O') { board[i + 1][j] = '#'; dfs(board, i + 1, j); } // left if (j > 1 && board[i][j - 1] == 'O') { board[i][j - 1] = '#'; dfs(board, i, j - 1); } // right if (j < col - 2 && board[i][j + 1] == 'O') { board[i][j + 1] = '#'; dfs(board, i, j + 1); } } }
注意,当行或列少于3时,不可能有被包围的‘O’。
这种思路简单易于理解,代码也很整洁,很适合初学者理解。
这个思路是从边缘向内部找连通的‘O’的,所以DFS时,就没必要在判断边缘上的字母了,因此DFS中,i 和 j 的条件为:i > 1, i < row - 2; j > 1, j < col - 2。(为什么?如果是 i = 1 时,那么 dfs(board, i - 1, j) 就是判断 [0, j] 了,而而边缘上的字母会被遍历判断的,这样就重复判断了,会导致栈溢出)。
DFS递归太深,容易栈溢出,这个代码可谓险过,最好还是用BFS。
【BFS】
参考:http://blog.sina.com.cn/s/blog_b9285de20101j1dt.html
public class Solution { char[][] board; int row; int col; Queue<Integer> queue = new LinkedList<Integer>(); public void solve(char[][] board) { this.board = board; row = board.length; if (row < 3) return; col = board[0].length; if (col < 3) return; // traverse first column and last column for (int i = 0; i < row; i++) { bfs(i, 0); bfs(i, col - 1); } // traverse first row and last row for (int j = 0; j < col; j++) { bfs(0, j); bfs(row - 1, j); } // change 'O' to 'X', restore '#' to 'O' for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } else if (board[i][j] == '#') { board[i][j] = 'O'; } } } } public void bfs(int i, int j) { fill(i, j); while (!queue.isEmpty()) { int pos = queue.poll(); int x = pos / col; int y = pos % col; fill(x - 1, y); fill(x + 1, y); fill(x, y - 1); fill(x, y + 1); } } public void fill(int i, int j) { if (i < 0 || j < 0 || i > row - 1 || j > col - 1) return; if (board[i][j] != 'O') return; queue.offer(i * col + j); board[i][j] = '#'; } }
DFS的实现是函数递归,BFS的实现是利用一个Queue。
关键的一点是,把 [i, j] 转化为 i * col + j 存储到Queue<Integer>里。
【LeetCode】Surrounded Regions 解题报告