欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[LeetCode] 图的遍历总结(深度优先遍历+广度优先遍历)

程序员文章站 2022-05-20 20:26:17
...

写在前面

图的遍历有两种即深度优先遍历(DFS)和广度优先遍历(BFS),图的遍历算法中DFS最经典的应用是回溯算法,图的经典算法也有多种,最小生成树(Prim Algo. + Krustal Algo.),最短路(Dijkstra Algo. + Floyd Algo.),可见这篇博客的总结。

130. 被围绕的区域

给定一个二维的矩阵,包含 ‘X’ 和 ‘O’(字母 O)。

找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

原题链接

解题思路: 按照题意是要我们找出所有被包围的’O’,然后用’X’填充,正面解题,我们在搜索到中间某个’O’时,往往还需要搜索一下从这个’O’出发是否存在一条全’O’的路径连通到边界,若是则判定为未包围,这种方案比较繁琐,不简洁,那我们反过来想,题目要我们找出被包围的’O’,若我们找出所有未包围的’O’,题目可解。OK,我们从四条边开始向矩阵内部搜索,将遍历到的’O’全部标记(这些都是属于未包围的),最后再扫描一遍矩阵,将未标记的’O’修改为’X’,将标记的’O’恢复。

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