LeetCode 130: Submit Solution会报Runtime Error，但我把那个例子复制下来单独Run Code没问题~

Question

由于没有在界面上找到“回复”这个功能选项，所以我就干脆重新在问题这儿编辑了，也不知道bobo老师能不能看到~

前几天用bfs得到了一个accepted之后，还是想着能不能改进一下dfs的代码，然后发现，我之前的那段代码的逻辑是存在问题的！！！

比如一个很简单的测试用例：

1 2 3 4

XXXX                              XXXX                XXXX XOOX   用原问题中的代码会得到        XOXX  正确的应该是  XOOX XOXX   ---------------------->    XOXX  ------------> XOXX XOXX                              XOXX                XOXX

也就是说有一些"O"点会被误认为是被surrounded的点，具体的和d[4][2]中的值的顺序有关，但不管顺序如何，都会有这种情况发生。

所以，还是得从边界出发来往内部dfs，虽然这样遍历的情况会变多，但也没办法，下面是我改进后的代码，虽然仍旧无法解决栈溢出的问题，但至少这次的逻辑应该是没问题了~

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

class Solution { private:     int m;     int n;     vector<vector<bool>> visited;     int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};   private:     bool inArea(int x, int y){         return x >= 0 && y >= 0 && x < m && y < n;     }           void dfs(vector<vector<char>> &board, int x, int y){         visited[x][y] = true;         for (int i = 0; i < 4; i++){             int newX = x + d[i][0];             int newY = y + d[i][1];             if (!inArea(newX, newY))                 continue;             if (board[newX][newY] == 'O' && !visited[newX][newY])                 dfs(board, newX, newY);         }         return;     }       public:     void solve(vector<vector<char>>& board) {         m = board.size();         if (m <= 2)             return;         n = board[0].size();         if (n <= 2)             return;                   visited = vector<vector<bool>>(m, vector<bool>(n, false));                   for (int i = 1; i < m - 1; i++){             if (board[i][0] == 'O' && !visited[i][0])                 dfs(board, i, 0);             if (board[i][n - 1] == 'O' && !visited[i][n - 1])                 dfs(board, i, n - 1);         }                   for (int i = 1; i < n - 1; i++){             if (board[0][i] == 'O' && !visited[0][i])                 dfs(board, 0, i);             if (board[m - 1][i] == 'O' && !visited[m - 1][i])                 dfs(board, m - 1, i);         }                   for (int i = 1; i < m - 1; i++){             for (int j = 1; j < n - 1; j++){                 if (board[i][j] == 'O' && !visited[i][j])                     board[i][j] = 'X';             }         }         return;     } };

-------------------------------------------原问题如下-------------------------------------------

如题，Submit Solution会报Runtime Error，但我把那个例子复制下来单独Run Code没问题~

不知道是怎么回事，代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

class Solution { private:     int m;     int n;     vector<vector<bool>> visited;     int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};   private:     bool inArea(int x, int y){         return x >= 0 && y >= 0 && x < m && y < n;     }           bool dfs(vector<vector<char>> &board, int x, int y){         visited[x][y] = true;         board[x][y] = 'X';         for (int i = 0; i < 4; i++){             int newX = x + d[i][0];             int newY = y + d[i][1];             if (!inArea(newX, newY)){                 board[x][y] = 'O';                 return false;             }             if (board[newX][newY] == 'O' && !dfs(board, newX, newY)){                 board[x][y] = 'O';                 return false;             }         }         return true;     }       public:     void solve(vector<vector<char>>& board) {         m = board.size();         if (m <= 0)             return;         n = board[0].size();                   visited = vector<vector<bool>>(m, vector<bool>(n, false));                   int changedRegion = 0;                   for (int i = 0; i < m; i++){             for (int j = 0; j < n; j++){                 if (board[i][j] == 'O' && !visited[i][j])                     if(dfs(board, i, j))                         changedRegion++;             }         }         return;     } };

Answer 1

liuyubobobo 2017-07-14 09:32:34

这个问题真的很赞！

我在准备这个课程的时候，按照类别把所有的题目读了一遍，并且根据我的课程规划进行了题目的分类。时间原因，我没有将所有的题目都做一遍，所以对于个别题目中可能存在的“坑”，或许在我录这个课程的时候没有意识到。要意识到了我一定会着重强调。所以抱歉！你遇到的这个问题我在课程中没有提及。

另一方面，据我观察，leetcode的测试用例其实是在逐渐加强的。最早leetcode的测试用例非常非常弱，现在leetcode的测试用例越来越强了。这也让leetcode题库的价值更大了：）

言归正传，你遇到了一个很有意思的问题，我也想了很久才想明白：）

首先，你写的逻辑非常赞，可以看出来对递归已经有很深刻的认识了。事实上，你的逻辑没有任何问题，真的很赞！但在一种情况下，会导致递归层数太深从而栈溢出。这种情况就是，如果给出的board很大且其中的O组成了一条由X分隔开的单一路径。下面是一个例子，说明这种情况，你要想象，有一个很大的board具有这种pattern:

1 2 3 4 5 6 7 8 9 10

OOOOOOOOO XXXXXXXXO OOOOOOOXO OXXXXXOXO OXOOOXOXO OXOXOXOXO OXOXXXOXO OXOOOOOXO OXXXXXXXO OOOOOOOOO

上面的例子是一个10*9的矩阵，你可以看出来，其中的O构建成了一条路径。你可以想象，如果从(0,0)点的O开始进行dfs的过程，这个矩阵里有多少个O，我们的dfs就要向下递归多少层。递归层数的数量级是O(n*m)的。当我们的board的n和m非常大的时候，递归深度就太大了！递归深度过大造成了系统栈的溢出，导致了Runtime Error!

事实上，这个测试用例非常好地反映了递归进行dfs遍历的缺点。如何解决？你需要将dfs改成bfs。改为bfs即可获得Accepted：）

好赞的题目！感谢你的问题：）

继续加油！

• 提问者 zjuPeco #1

  多谢bobo老师这么详尽的回答，我去试一下bfs ：）波波老师的课让我对算法有了更深的理解~

• liuyubobobo 回复 提问者 zjuPeco #2

  那就太好啦！加油！再次感谢你的好问题：）