C++實(shí)現(xiàn)LeetCode之包圍區(qū)域的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)C++實(shí)現(xiàn)LeetCode之包圍區(qū)域的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

[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 很類似，都可以用 DFS 來解。剛開始我的思路是 DFS 遍歷中間的O，如果沒有到達(dá)邊緣，都變成X，如果到達(dá)了邊緣，將之前變成X的再變回來。但是這樣做非常的不方便，在網(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 無法通過 OJ 的最后一個(gè)大數(shù)據(jù)集合，博主開始也不知道其中奧秘，直到被另一個(gè)網(wǎng)友提醒在本地機(jī)子上可以通過最后一個(gè)大數(shù)據(jù)集合，于是博主也寫了一個(gè)程序來驗(yàn)證，請(qǐng)參見驗(yàn)證 LeetCode Surrounded Regions 包圍區(qū)域的DFS方法，發(fā)現(xiàn) j > 0 是正確的，可以得到相同的結(jié)果。神奇的是，現(xiàn)在用 j > 0  也可以通過 OJ 了。

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

解法二：

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即可，參見代碼如下：

解法三：

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';
            }
        }
    }
};

關(guān)于“C++實(shí)現(xiàn)LeetCode之包圍區(qū)域的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。