[LeetCode]Surrounded Regions,解题报告

目录前言

最近这两天为了解决Android Rom适配一个底层的问题，天天熬夜到2点，导致原定了LeetCode刷题计划都受到了影响。昨晚终于熬夜搞定，补充一道LeetCode解题报告。

题目

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

思路1_DFS

这道题目给出的提示是用广度优先搜索(BFS)，但是我憋了半天没思路，因为平时我一般都是用BFS解决一些迷宫的题目。

于是，我还是想到换个思路，既然BFS不行，那就DFS（深度优先搜索）。思路如下：

DFS代码如下：

{[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};(char[][] board) {int row = board.length;if (row < 2) {return ;}int column = board[0].length;if (column < 2) {return;}for (int j = 0; j < board[0].length; j ++) {if (board[0][j] == ‘O’) {dfsBoard(board, 0, j);}}for (int i = 1; i < board.length; i ++) {if (board[i][column – 1] == ‘O’) {dfsBoard(board, i, column – 1);}}for (int j = column – 2; j >= 0; j –) {if (board[row – 1][j] == ‘O’) {dfsBoard(board, row – 1, j);}}for (int i = row – 2; i >= 0; i –) {if (board[i][0] == ‘O’) {dfsBoard(board, i, 0);}}for (int i = 0; i < row; i ++) {for (int j = 0; j < column; j ++) {board[i][j] = board[i][j] == ‘K’ ? ‘O’ : ‘X’;}}}(char[][] board, int x, int y) {board[x][y] = ‘K’;for (int i = 0; i < directions.length; i ++) {int new_x = x + directions[i][0];int new_y = y + directions[i][1];if (new_x < 0 || new_x >= board.length || new_y < 0 || new_y >= board[0].length || board[new_x][new_y] != ‘O’) {continue;}dfsBoard(board, new_x, new_y);}}}

本来以为结果会TLE，没想到出乎我的意料，，结果是Runtime Error，递归栈被爆掉了。

思路2_BFS

DFS爆栈充分说明题目的提示还是很管用的，必须要用BFS啊。但是，上面DFS的方法给我们提供了很好的思路。爆栈的原因是：DFS栈深度不够，那我们直接将这里的DFS遍历换成BFS不就可以了。

思路更改的地方：

每次最外层遍历的过程中，如果发现有‘O’，那我们可以尝试进行上下左右四个方向的遍历，如果再次发现有’O’，将当前节点放入队列中。放入队列中的‘O’也是不会被‘X’包围的，将这种‘O’转换为‘K’即可。（ps：其实就是将栈实现改为队列实现）

直接上AC代码了：

{{private int x, y;public BoardPoint(int x, int y) {this.x = x;this.y = y;}() {return x;}() {return y;}}[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };(char[][] board) {int row = board.length;if (row < 2) {return;}int column = board[0].length;if (column < 2) {return;}for (int j = 0; j < board[0].length; j++) {if (board[0][j] == ‘O’) {bfsBoard(board, 0, j, row, column);}}for (int i = 1; i < board.length; i++) {if (board[i][column – 1] == ‘O’) {bfsBoard(board, i, column – 1, row, column);}}for (int j = column – 2; j >= 0; j–) {if (board[row – 1][j] == ‘O’) {bfsBoard(board, row – 1, j, row, column);}}for (int i = row – 2; i >= 0; i–) {if (board[i][0] == ‘O’) {bfsBoard(board, i, 0, row, column);}}for (int i = 0; i < row; i++) {for (int j = 0; j < column; j++) {board[i][j] = board[i][j] == ‘K’ ? ‘O’ : ‘X’;}}}(char[][] board, int x, int y, int row, int col) {ArrayDeque<BoardPoint> queue = new ArrayDeque<BoardPoint>();queue.push(new BoardPoint(x, y));while (!queue.isEmpty()) {BoardPoint point = queue.poll();board[point.getX()][point.getY()] = ‘K’;for (int i = 0; i < directions.length; i++) {int new_x = point.getX() + directions[i][0];int new_y = point.getY() + directions[i][1];if (new_x >= 0 && new_x < row && new_y >= 0 && new_y < col && board[new_x][new_y] == ‘O’) {queue.push(new BoardPoint(new_x, new_y));}}}}}

更重要的是心理上的完全自由和放松，