130. Surrounded Regions -M

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

 

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

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 ---------

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        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';
                }
            }
        }
    }
private:
    void dfs(vector<vector<char>>& board, int i, int j) {
        int m = board.size(), n = board[0].size();
        if (board[i][j] != 'O')
            return;
        vector<vector<int>> Steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        board[i][j] = 'A';
        for (auto diff : Steps) {
            int x = i + diff[0], y = j + diff[1];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                dfs(board, x, y);
        }
    }
};