130 - Surrounded Regions

Surrounded Regions

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

Hide Tags
Breadth-first Search Union Find
Hide Similar Problems
(M) Number of Islands

这道题难倒不难，但意料之外地花了不少时间。
刚开始沿着200 - Number of Islands惯性地从对中间元素进行遍历，如果能走到边上，则置为某个别的字符，表示不必清除。
后来发现这样似乎耗时太久，尤其有个200 X 200 的大集合，第一圈是 O，第二圈是 X，里面全是 O，直接超时。
这才意识到方向错了，既然不清除的只能是连通到四个边上的集合，那么只要以外面四个边上的 O 为起点遍历就好了啊！
遍历得到的就置个标记，遍历不到的自然还是原样子，然后把这些玩意清除掉，把置位的恢复原值不就好了么！
这样显然比处理中间要省时间多了嘛，咋早没想到呐！

但事情显然没有这么easy。。。
显示习惯性地写了个 dfs 的思路，擦，居然大集合超时。。。？
以为是有什么剪枝没处理，搞了好久没有什么改善，翻看网上的帖子，用帖子里的 dfs 就没问题…，怪异。
仔细看了半天才发现，在 dfs 的时候，y-1 也就是向上 dfs 的时候，居然条件是 y>1？没道理啊？
试来试去，发现还真是这么回事，y>0 就 runtime error，y>1 就可以通过。
但诡异的是，在自己的虚拟机上没有一点问题，秒出结果啊？！

想来想去想不出个所以然，跟大家讨论的结果是，可能是栈击穿了，别的确实想不出有啥问题了。
在本地没有问题，可能是因为本地的环境调用栈的深度限制比 leetcode 的环境宽松。
为了证实这个猜想，首先调用系统函数 system("ulimit -a"); 查看了 leetcode 的limits，然后对照自己环境的，
果不其然，leetcode 的stack的限制远远小于我的虚拟机！

leetcode 的 limits
time(seconds)        1
file(blocks)         2048
data(kbytes)         unlimited
stack(kbytes)        971--------------------------------------> 971 k
coredump(blocks)     unlimited
memory(kbytes)       unlimited
locked memory(kbytes) 64
process              20
nofiles              1048576
vmemory(kbytes)      unlimited
locks                unlimited


我的虚拟机的 limitscore file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 15744
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192---------------------> 8 M
cpu time               (seconds, -t) unlimited
max user processes              (-u) 15744
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

顺便统计了一下递归调用的深度，最大的时候竟然达到了 31376 层之多，
看起来应该是 leetcode 的 limit 不能承受这么深的栈，溢出了。。。
从这个角度来看，难怪 hit 的标签里只有 BFS，而没有 DFS！
估计第五低的 acceptance 跟着一点很有关系吧！

为了进一步证实 y>1 不是正确结果的充要条件，另外又写了一个 BFS ，
果不其然，完全不需要 y>1 的保护，就可以达到同样的结果，16 ms. （queue的 pop 应该也有点费时间吧）
不过在 BFS 的调试中，也有一个小插曲：
如果在取得 queue 头之后再修改字符的值，可能会因此造成不必要的冗余 push 操作，最终导致超时。
将它改成 push 之前就改掉该字符，这样就下一次过来就不会重复压入这个节点了，避免无意义的耗时。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int count=0, sz=board.size(), zz=sz?(board[0].size()):0;
       
        for(int ii=0; ii<sz; ++ii)
        {
            if('O' == board[ii][0])
                bfs(board, sz, zz, ii, 0);

            if('O' == board[ii][zz-1])
                bfs(board, sz, zz, ii, zz-1);
        }

        for(int ii=0; ii<zz; ++ii)
        {
            if('O' == board[0][ii])
                bfs(board, sz, zz, 0, ii);

            if('O' == board[sz-1][ii])
                bfs(board, sz, zz, sz-1, ii);
        }

        for(int ii=0; ii<sz; ++ii)
        {
            for(int jj=0; jj<zz; ++jj)
            {
                if('O'==board[ii][jj])
                    board[ii][jj] = 'X';
                if('A'==board[ii][jj])
                    board[ii][jj] = 'O';
            }
        }
        return;
    }

    void dfs(vector<vector<char> >& g, int sz, int zz, int x, int y)
    {
        if(0>x || sz<=x || 0>y || zz<=y )
            return;
        if('O'!=g[x][y])
            return;

        g[x][y] = 'A';

        //actually y>1 is not reasonable, but without it will lead to runtime error
        //probably because of the deepth limitation of call stack
        //can check it by "system("ulimit -a");"
        if(y>1)
            dfs(g, sz, zz, x, y-1);

        dfs(g, sz, zz, x-1, y);
        dfs(g, sz, zz, x+1, y);
        dfs(g, sz, zz, x, y+1);
    }
   
    void bfs(vector<vector<char> >& g, int sz, int zz, int x, int y)
    {
        queue<pair<int, int>> q;
        g[x][y] = 'A';                  //set 1st element to 'A' before pushing to avoid TLE
        q.push({x,y});

        while(q.size())
        {
            int xx = q.front().first;
            int yy = q.front().second;
            //g[xx][yy] = 'A';          //set to 'A' here could lead to TLE
            q.pop();
           
            if(xx>0 && 'O'==g[xx-1][yy])
                g[xx-1][yy] = 'A', q.push({xx-1, yy});  //set to 'A' before pushing to avoid TLE
            if(yy>0 && 'O'==g[xx][yy-1])
                g[xx][yy-1] = 'A', q.push({xx, yy-1});  //set to 'A' before pushing to avoid TLE
            if(xx<sz-1 && 'O'==g[xx+1][yy])
                g[xx+1][yy] = 'A', q.push({xx+1, yy});  //set to 'A' before pushing to avoid TLE
            if(yy<zz-1 && 'O'==g[xx][yy+1])
                g[xx][yy+1] = 'A', q.push({xx, yy+1});  //set to 'A' before pushing to avoid TLE
        }
    }
};
16 ms, 16 ms.