surrounded regions

请问下，这道题为什么用递归会Run time error呢？代码：

1. void dfs(vector<string>& board, int m, int n, int i, int j, vector<vector<bool> >& visited) {
   
2.         if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' || visited[i][j] == true) return;
   
3.         visited[i][j] = true;
   
4.         dfs(board, m, n, i - 1, j, visited);
   
5.         dfs(board, m, n, i, j - 1, visited);
   
6.         dfs(board, m, n, i + 1, j, visited);
   
7.         dfs(board, m, n, i, j + 1, visited);
   
8. }
   
9. 
   
10. bool validSide(vector<string>& board, int i, int j, vector<vector<bool> >& visited) {
    
11.         if (board[i][j] != 'O' || visited[i][j] == false) return true;
    
12.         return false;
    
13. }
    
14. 
    
15. void solve(vector<string>& board) {
    
16.         if (board.empty()) return;
    
17.         int m = board.size();
    
18.         int n = board[0].size();
    
19.         if (m < 3 || n < 3) return;
    
20.         vector<vector<bool> > visited(m, vector<bool>(n, false));
    
21.         // top boundary: dfs
    
22.         for (int j = 0; j < n; ++j) {
    
23.                 if (board[0][j] == 'O' && visited[0][j] == false)
    
24.                         dfs(board, m, n, 0, j, visited);
    
25.         }
    
26.         // right boundary: dfs
    
27.         for (int i = 1; i < m; ++i) {
    
28.                 if (board[i][n - 1] == 'O' && visited[i][n - 1] == false)
    
29.                         dfs(board, m, n, i, n - 1, visited);
    
30.         }
    
31.         // bottom boundary: dfs
    
32.         for (int j = n - 2; j >= 0; --j) {
    
33.                 if (board[m - 1][j] == 'O' && visited[m - 1][j] == false)
    
34.                         dfs(board, m, n, m - 1, j, visited);
    
35.         }
    
36.         // left boundary: dfs
    
37.         for (int i = m - 2; i > 0; --i) {
    
38.                 if (board[i][0] == 'O' && visited[i][0] == false)
    
39.                         dfs(board, m, n, i, 0, visited);
    
40.         }
    
41.         // matrix inner part
    
42.         for (int i = 1; i < m - 1; ++i) {
    
43.                 for (int j = 1; j < n - 1; ++j) {
    
44.                         if ( board[i][j] == 'O' && visited[i][j] == false &&
    
45.                                  validSide(board, i - 1, j, visited) && validSide(board, i, j - 1, visited) &&
    
46.                                  validSide(board, i + 1, j, visited) && validSide(board, i, j + 1, visited) )
    
47.                                         board[i][j] = 'X';
    
48.                 }
    
49.         }
    
50. }

复制代码

谢谢。

stack overflow?

因为你4-7行会把边缘再加入递归的stack里。 改成这样就行了：
        if (i-1 > 0) dfs(board, m, n, i - 1, j, visited);
        if (j-1 > 0) dfs(board, m, n, i, j - 1, visited);
        if (i+1 < m-1) dfs(board, m, n, i + 1, j, visited);
        if (j+1 < n-1) dfs(board, m, n, i, j + 1, visited);

totolin 发表于 2015-7-19 10:02
因为你4-7行会把边缘再加入递归的stack里。 改成这样就行了：
        if (i-1 > 0) dfs(board, m, n, i - ...

你可以试试优化一下， 把和边缘链接的O改成Y， 然后再把剩余O改成X，把Y再改回O，这样就不用visited。

totolin 发表于 2015-7-19 10:02
因为你4-7行会把边缘再加入递归的stack里。 改成这样就行了：
        if (i-1 > 0) dfs(board, m, n, i - ...

把4-7行修改后确实AC了。可是还是不太懂额，即使把边界上的点加到递归栈里，在递归的下一层，它应该会在递归基出弹出啊，为什么还是会越界呢

谢谢！你说的优化的方法，后来上网查过，蛮好使的。

还是用BFS吧

1. class Solution {
   
2. public:
   
3.     void bfs(vector<vector<char> > &board, int x, int y) {
   
4.         int lenx = board.size(), leny = board[0].size();
   
5.         int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
   
6.         queue<pair<int, int> > que;
   
7.         board[x][y] = '1';
   
8.         que.push(make_pair(x, y));
   
9.         while (!que.empty()) {
   
10.             int x1 = que.front().first, y1 = que.front().second;
    
11.             que.pop();
    
12.             for (int i = 0; i < 4; i ++) {
    
13.                 int x2 = x1 + dx[i], y2 = y1 + dy[i];
    
14.                 if (x2 >= 0 && x2 < lenx && y2 >= 0 && y2 < leny && board[x2][y2] == 'O') {
    
15.                     board[x2][y2] = '1';
    
16.                     que.push(make_pair(x2, y2));
    
17.                 }
    
18.             }
    
19.         }
    
20.     }
    
21.     void solve(vector<vector<char> >& board) {
    
22.         if (board.empty() || board[0].empty()) return;
    
23.         int lenx = board.size(), leny = board[0].size();
    
24.         for (int i = 0; i < lenx; i ++) {
    
25.             if (board[i][0] == 'O') bfs(board, i, 0);
    
26.             if (board[i][leny - 1] == 'O')  bfs(board, i, leny - 1);
    
27.         }
    
28.         for (int i = 0; i < leny; i ++) {
    
29.             if (board[0][i] == 'O') bfs(board, 0, i);
    
30.             if (board[lenx - 1][i] == 'O') bfs(board, lenx - 1, i);
    
31.         }
    
32.         for (int i = 0; i < lenx; i ++) {
    
33.             for (int j = 0; j < leny; j ++) {
    
34.                 if (board[i][j] == 'O') board[i][j] = 'X';
    
35.             }
    
36.         }
    
37.         for (int i = 0; i < lenx; i ++) {
    
38.             for (int j = 0; j < leny; j ++) {
    
39.                 if (board[i][j] == '1') board[i][j] = 'O';
    
40.             }
    
41.         }
    
42.     }
    
43. };

复制代码

matrixmaster 发表于 2015-7-19 10:23
把4-7行修改后确实AC了。可是还是不太懂额，即使把边界上的点加到递归栈里，在递归的下一层，它应该会在 ...

你原先的code可以用的，只是会在N大的时候才出现问题。在N很大的时候如果每个边界上的点都再加一次到stack里的话会把容量撑大不少， 所以在leetcode才过不了。