LeetCode 130: Submit Solution会报Runtime Error，但我把那个例子复制下来单独Run Code没问题~
由于没有在界面上找到“回复”这个功能选项，所以我就干脆重新在问题这儿编辑了，也不知道bobo老师能不能看到~
前几天用bfs得到了一个accepted之后，还是想着能不能改进一下dfs的代码，然后发现，我之前的那段代码的逻辑是存在问题的！！！
比如一个很简单的测试用例：
XXXX XXXX XXXX XOOX 用原问题中的代码会得到 XOXX 正确的应该是 XOOX XOXX ----------------------> XOXX ------------> XOXX XOXX XOXX XOXX
也就是说有一些"O"点会被误认为是被surrounded的点，具体的和d[4][2]中的值的顺序有关，但不管顺序如何，都会有这种情况发生。
所以，还是得从边界出发来往内部dfs，虽然这样遍历的情况会变多，但也没办法，下面是我改进后的代码，虽然仍旧无法解决栈溢出的问题，但至少这次的逻辑应该是没问题了~
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没问题~
不知道是怎么回事，代码如下：
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;
}
};正在回答
1回答
这个问题真的很赞！
我在准备这个课程的时候，按照类别把所有的题目读了一遍，并且根据我的课程规划进行了题目的分类。时间原因，我没有将所有的题目都做一遍，所以对于个别题目中可能存在的“坑”，或许在我录这个课程的时候没有意识到。要意识到了我一定会着重强调。所以抱歉！你遇到的这个问题我在课程中没有提及。
另一方面，据我观察，leetcode的测试用例其实是在逐渐加强的。最早leetcode的测试用例非常非常弱，现在leetcode的测试用例越来越强了。这也让leetcode题库的价值更大了：）
言归正传，你遇到了一个很有意思的问题，我也想了很久才想明白：）
首先，你写的逻辑非常赞，可以看出来对递归已经有很深刻的认识了。事实上，你的逻辑没有任何问题，真的很赞！但在一种情况下，会导致递归层数太深从而栈溢出。这种情况就是，如果给出的board很大且其中的O组成了一条由X分隔开的单一路径。下面是一个例子，说明这种情况，你要想象，有一个很大的board具有这种pattern:
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：）
好赞的题目！感谢你的问题：）
继续加油！
相似问题
登录后可查看更多问答，登录/注册
