一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 329|回复: 6
收起左侧

[Leetcode] surrounded regions

[复制链接] |试试Instant~ |关注本帖
matrixmaster 发表于 2015-7-19 03:54:42 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 matrixmaster 于 2015-7-19 03:56 编辑

请问下,这道题为什么用递归会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. bool validSide(vector<string>& board, int i, int j, vector<vector<bool> >& visited) {
  10.         if (board[i][j] != 'O' || visited[i][j] == false) return true;
  11.         return false;
  12. }

  13. void solve(vector<string>& board) {
  14.         if (board.empty()) return;
  15.         int m = board.size();
  16.         int n = board[0].size();
  17.         if (m < 3 || n < 3) return;
  18.         vector<vector<bool> > visited(m, vector<bool>(n, false));
  19.         // top boundary: dfs
  20.         for (int j = 0; j < n; ++j) {
  21.                 if (board[0][j] == 'O' && visited[0][j] == false)
  22.                         dfs(board, m, n, 0, j, visited);
  23.         }
  24.         // right boundary: dfs
  25.         for (int i = 1; i < m; ++i) {
  26.                 if (board[i][n - 1] == 'O' && visited[i][n - 1] == false)
  27.                         dfs(board, m, n, i, n - 1, visited);
  28.         }
  29.         // bottom boundary: dfs
  30.         for (int j = n - 2; j >= 0; --j) {
  31.                 if (board[m - 1][j] == 'O' && visited[m - 1][j] == false)
  32.                         dfs(board, m, n, m - 1, j, visited);
  33.         }
  34.         // left boundary: dfs
  35.         for (int i = m - 2; i > 0; --i) {
  36.                 if (board[i][0] == 'O' && visited[i][0] == false)
  37.                         dfs(board, m, n, i, 0, visited);
  38.         }
  39.         // matrix inner part
  40.         for (int i = 1; i < m - 1; ++i) {
  41.                 for (int j = 1; j < n - 1; ++j) {
  42.                         if ( board[i][j] == 'O' && visited[i][j] == false &&
  43.                                  validSide(board, i - 1, j, visited) && validSide(board, i, j - 1, visited) &&
  44.                                  validSide(board, i + 1, j, visited) && validSide(board, i, j + 1, visited) )
  45.                                         board[i][j] = 'X';
  46.                 }
  47.         }
  48. }
复制代码
谢谢。
handsomecool 发表于 2015-7-19 06:08:01 | 显示全部楼层
stack overflow?
回复 支持 反对

使用道具 举报

totolin 发表于 2015-7-19 10:02:42 | 显示全部楼层
因为你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);

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

totolin 发表于 2015-7-19 10:05:36 | 显示全部楼层
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。
回复 支持 反对

使用道具 举报

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

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

谢谢!你说的优化的方法,后来上网查过,蛮好使的。
回复 支持 反对

使用道具 举报

iFighting 发表于 2015-7-19 11:01:21 | 显示全部楼层
还是用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. };
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 20:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表