C++實現LeetCode(130.包圍區域)

Posted on by

[LeetCode] 130. Surrounded Regions 包圍區域

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 同步地址：

https://github.com/grandyang/leetcode/issues/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

到此這篇關於C++實現LeetCode(130.包圍區域)的文章就介紹到這瞭,更多相關C++實現包圍區域內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：