The Wayback Machine - https://web.archive.org/web/20230316081146/https://github.com/grandyang/leetcode/issues/130
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[LeetCode] 130. Surrounded Regions #130

Open
grandyang opened this issue May 30, 2019 · 2 comments
Open

[LeetCode] 130. Surrounded Regions #130

grandyang opened this issue May 30, 2019 · 2 comments

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019 •
edited

 

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.

 

这是道关于 XXOO 的题，有点像围棋，将包住的O都变成X，但不同的是边缘的O不算被包围，跟之前那道 Number of Islands 很类似，都可以用 DFS 来解。刚开始我的思路是 DFS 遍历中间的O，如果没有到达边缘，都变成X，如果到达了边缘，将之前变成X的再变回来。但是这样做非常的不方便，在网上看到大家普遍的做法是扫矩阵的四条边，如果有O，则用 DFS 遍历，将所有连着的O都变成另一个字符，比如 $，这样剩下的O都是被包围的，然后将这些O变成X，把$变回O就行了。代码如下：

 

解法一：

class Solution {
public:
    void solve(vector<vector<char> >& board) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if ((i == 0 || i == board.size() - 1 || j == 0 || j == board[i].size() - 1) && board[i][j] == 'O')
                    solveDFS(board, i, j);
            }
        }
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
    void solveDFS(vector<vector<char> > &board, int i, int j) {
        if (board[i][j] == 'O') {
            board[i][j] = '$';
            if (i > 0 && board[i - 1][j] == 'O') 
                solveDFS(board, i - 1, j);
            if (j < board[i].size() - 1 && board[i][j + 1] == 'O') 
                solveDFS(board, i, j + 1);
            if (i < board.size() - 1 && board[i + 1][j] == 'O') 
                solveDFS(board, i + 1, j);
            if (j > 0 && board[i][j - 1] == 'O') 
                solveDFS(board, i, j - 1);
        }
    }
};

 

很久以前，上面的代码中最后一个 if 中必须是 j > 1 而不是 j > 0，为啥 j > 0 无法通过 OJ 的最后一个大数据集合，博主开始也不知道其中奥秘，直到被另一个网友提醒在本地机子上可以通过最后一个大数据集合，于是博主也写了一个程序来验证，请参见验证 LeetCode Surrounded Regions 包围区域的DFS方法，发现 j > 0 是正确的，可以得到相同的结果。神奇的是，现在用 j > 0  也可以通过 OJ 了。

下面这种解法还是 DFS 解法，只是递归函数的写法稍有不同，但是本质上并没有太大的区别，参见代码如下：

 

解法二：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        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) {
                    if (board[i][j] == 'O') dfs(board, i , j);
                }
            }   
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector<vector<char>> &board, int x, int y) {
        int m = board.size(), n = board[0].size();
        vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
        board[x][y] = '$';
        for (int i = 0; i < dir.size(); ++i) {
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if (dx >= 0 && dx < m && dy > 0 && dy < n && board[dx][dy] == 'O') {
                dfs(board, dx, dy);
            }
        }
    }
};

 

我们也可以使用迭代的解法，但是整体的思路还是一样的，在找到边界上的O后，然后利用队列 queue 进行 BFS 查找和其相连的所有O，然后都标记上美元号。最后的处理还是先把所有的O变成X，然后再把美元号变回O即可，参见代码如下：

 

解法三：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        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) continue;
                if (board[i][j] != 'O') continue;
                board[i][j] = '$';
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(), x = t / n, y = t % n; q.pop();
                    if (x >= 1 && board[x - 1][y] == 'O') {board[x - 1][y] = '$'; q.push(t - n);}
                    if (x < m - 1 && board[x + 1][y] == 'O') {board[x + 1][y] = '$'; q.push(t + n);}
                    if (y >= 1 && board[x][y - 1] == 'O') {board[x][y - 1] = '$'; q.push(t - 1);}
                    if (y < n - 1 && board[x][y + 1] == 'O') {board[x][y + 1] = '$'; q.push(t + 1);}
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
};

 

Github 同步地址：

#130

 

类似题目：

Number of Islands

Walls and Gates

 

参考资料：

https://leetcode.com/problems/surrounded-regions/

https://leetcode.com/problems/surrounded-regions/discuss/41895/Share-my-clean-Java-Code

https://leetcode.com/problems/surrounded-regions/discuss/41825/Simple-BFS-solution-easy-to-understand

https://leetcode.com/problems/surrounded-regions/discuss/41612/A-really-simple-and-readable-C%2B%2B-solutionuff0conly-cost-12ms

 

LeetCode All in One 题目讲解汇总(持续更新中...)
@yasinSun
Copy link

根据大佬的第一种写法做了一个实现，没有遇到 j>1 什么的奇怪问题

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rows = board.size();
        if(rows == 0){
            return;
        }
        int cols = board[0].size();
        for(int row = 0; row < rows; row++){//遍历四条边
            solveCore(board, row, 0);
            solveCore(board, row, cols-1);
        }
        for(int col = 0; col < cols; col++){
            solveCore(board, 0, col);
            solveCore(board, rows-1, col);
        }
        for(vector<char>& eles: board){
            for(char& ele: eles){
                if(ele == 'O'){
                    ele = 'X';
                }
                if(ele == '$'){
                    ele = 'O';
                }
            }
        }
    }
private:
    void solveCore(vector<vector<char>>& board, int i, int j){
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){
            return;
        }
        board[i][j] = '$';
        solveCore(board, i+1, j);
        solveCore(board, i-1, j);
        solveCore(board, i, j+1);
        solveCore(board, i, j-1);
    }
};

@grandyang
Copy link
Owner Author

根据大佬的第一种写法做了一个实现，没有遇到 j>1 什么的奇怪问题

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rows = board.size();
        if(rows == 0){
            return;
        }
        int cols = board[0].size();
        for(int row = 0; row < rows; row++){//遍历四条边
            solveCore(board, row, 0);
            solveCore(board, row, cols-1);
        }
        for(int col = 0; col < cols; col++){
            solveCore(board, 0, col);
            solveCore(board, rows-1, col);
        }
        for(vector<char>& eles: board){
            for(char& ele: eles){
                if(ele == 'O'){
                    ele = 'X';
                }
                if(ele == '$'){
                    ele = 'O';
                }
            }
        }
    }
private:
    void solveCore(vector<vector<char>>& board, int i, int j){
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){
            return;
        }
        board[i][j] = '$';
        solveCore(board, i+1, j);
        solveCore(board, i-1, j);
        solveCore(board, i, j+1);
        solveCore(board, i, j-1);
    }
};

嗯嗯，现在貌似没问题了。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@grandyang @yasinSun