快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(130.包圍區(qū)域)

更新時(shí)間：2021年07月27日 15:53:01 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(130.包圍區(qū)域),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 130. Surrounded Regions 包圍區(qū)域

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.

這是道關(guān)于 XXOO 的題，有點(diǎn)像圍棋，將包住的O都變成X，但不同的是邊緣的O不算被包圍，跟之前那道 Number of Islands 很類(lèi)似，都可以用 DFS 來(lái)解。剛開(kāi)始我的思路是 DFS 遍歷中間的O，如果沒(méi)有到達(dá)邊緣，都變成X，如果到達(dá)了邊緣，將之前變成X的再變回來(lái)。但是這樣做非常的不方便，在網(wǎng)上看到大家普遍的做法是掃矩陣的四條邊，如果有O，則用 DFS 遍歷，將所有連著的O都變成另一個(gè)字符，比如 \$，這樣剩下的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);
        }
    }
};

很久以前，上面的代碼中最后一個(gè) if 中必須是 j > 1 而不是 j > 0，為啥 j > 0 無(wú)法通過(guò) OJ 的最后一個(gè)大數(shù)據(jù)集合，博主開(kāi)始也不知道其中奧秘，直到被另一個(gè)網(wǎng)友提醒在本地機(jī)子上可以通過(guò)最后一個(gè)大數(shù)據(jù)集合，于是博主也寫(xiě)了一個(gè)程序來(lái)驗(yàn)證，請(qǐng)參見(jiàn)驗(yàn)證 LeetCode Surrounded Regions 包圍區(qū)域的DFS方法，發(fā)現(xiàn) j > 0 是正確的，可以得到相同的結(jié)果。神奇的是，現(xiàn)在用 j > 0 也可以通過(guò) OJ 了。

下面這種解法還是 DFS 解法，只是遞歸函數(shù)的寫(xiě)法稍有不同，但是本質(zhì)上并沒(méi)有太大的區(qū)別，參見(jiàn)代碼如下：

解法二：

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后，然后利用隊(duì)列 queue 進(jìn)行 BFS 查找和其相連的所有O，然后都標(biāo)記上美元號(hào)。最后的處理還是先把所有的O變成X，然后再把美元號(hào)變回O即可，參見(jiàn)代碼如下：

解法三：

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

類(lèi)似題目：

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

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(130.包圍區(qū)域)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)包圍區(qū)域內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: