130. Surrounded Regions -M

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

A:

用图像里的growing思想呗。 每碰到一个 o  就开始检测。直到出了边界或者确认包围（转换成X）  嗯，首先是把边界的设 为 标识 @ ， 然后grow，
 虽然，也用了小技巧，来提速，但是，这个的实现,还是有点儿慢了。 具体实现，在最后（learned section的下面）

下面这个方法，是利用grow un-surrouned O, 方法。
简单来讲，就是先从四周开始，一层层地剥开。
但是，这样的假设是不成立的， 原因在于， 无法回溯到 zig-zag形式的。

哎，还是回到前面的思路， 考虑到，我们是对200*200的一个巨大的0闭环内没有通过。
我们考虑从四周开始grow un-surrouned region(也就是把上面的2个思路并起来。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m==0)
            return;
        int n = board[0].size();        
        vector<vector<int> > stack;
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if((i==0 || i==m-1 || j==0 || j==n-1 ) && board[i][j] =='O')
                    stack.push_back(vector<int>{i,j});
        // change boundary 'O' --> 'A',
        while(not stack.empty())
        {
            vector<vector<int>> newS;
            for(auto tmp : stack)
            {
                int i = tmp[0], j = tmp[1];
                board[i][j] = 'A';
                if(i>0 && board[i-1][j] =='O')
                    newS.push_back(vector<int>{i-1,j});
                if(i+1<m && board[i+1][j] =='O')
                    newS.push_back(vector<int>{i+1,j});
                if(j>0 && board[i][j-1] =='O')
                    newS.push_back(vector<int>{i,j-1});
                if(j+1<n && board[i][j+1] =='O')
                    newS.push_back(vector<int>{i,j+1});
            }
            stack = newS;
        }
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if(board[i][j]=='O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'A')
                    board[i][j] = 'O';
        
    }
};

Mistakes:
2： 处于速度考虑，我们search的时候，尽量通过从4个边来，从内往里search???
3: 还是有一些拼写错误，  主要来自于copy 上面的代码（因为重复性太多）

----------------------------这个更改，删掉了copy vector这个步骤, 节省了空间-------------

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m==0)
            return;
        int n = board[0].size();        
        vector<vector<int> > posList;
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if((i==0 || i==m-1 || j==0 || j==n-1 ) && board[i][j] =='O')
                    posList.push_back(vector<int>{i,j});
        // change boundary 'O' --> 'A',
        for(int cur = 0;cur<posList.size();++cur)
        {
            int i = posList[cur][0], j = posList[cur][1];
            board[i][j] = 'A';
            if(i>0 && board[i-1][j] =='O')
                posList.push_back(vector<int>{i-1,j});
            if(i+1<m && board[i+1][j] =='O')
                posList.push_back(vector<int>{i+1,j});
            if(j>0 && board[i][j-1] =='O')
                posList.push_back(vector<int>{i,j-1});
            if(j+1<n && board[i][j+1] =='O')
                posList.push_back(vector<int>{i,j+1});
        }
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
                if(board[i][j]=='O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'A')
                    board[i][j] = 'O';
    }
};

Learned:
1: 在将就效率的时候，就不要搞些递归， 尽量用interative,  来存储中间数据。


--------------下面的这个，too  slow----------coz  we have use too many dfs ---------

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        int m = board.length;
        int n = board[0].length;
        // DFS track the border
        // for first and last rows
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        // for most left and most right columns
        for (int i = 1; i < m - 1; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        // flip all inner O into X , and boarder @ into O
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '@')
                    board[i][j] = 'O';
    }

    private void dfs(char[][] board, int i, int j) {
        if (board[i][j] != 'O')
            return;
        board[i][j] = '@'; // set as a flag
        int m = board.length;
        int n = board[0].length;

        if (i - 1 >= 0 && board[i - 1][j] == 'O')// up
            dfs(board, i - 1, j);
        if (i + 1 < m && board[i + 1][j] == 'O')// down
            dfs(board, i + 1, j);
        if (j - 1 >= 0 && board[i][j - 1] == 'O')// left
            dfs(board, i, j - 1);
        if (j + 1 < n && board[i][j + 1] == 'O')// right
            dfs(board, i, j + 1);
    }
}