10

算法系列：优先遍历

 3 years ago
source link: https://muyuuuu.github.io/2022/05/30/dfs-bfs/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

主要收录深度优先遍历和宽度优先遍历，深度优先遍历一般可以与回溯、递归、树等方法联用，达到优雅遍历的效果，而宽度优先搜索可以用到最短路问题的求解中。

  • 为什么不用 bfs 去遍历？第一是因为 bfs 写起来麻烦，不如 dfs 直观。第二是在某些查找到满足情况即可退出的应用而言，bfs 需要一层一层的去检查，效率很低。
  • 为什么不用 dfs 去求最短路？如上所示，bfs 可以一层一层的检查，相对 dfs 更容易查到最短路。

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

  1. 那么如何填充内部的 O 呢？这里就要用到 dfs，首先遍历 board，如果遇到了 O，那个和这个 O 相邻的 O 也要被填充，此时就要使用 dfs 来查找相邻的 O
  2. 由于只填充被 X 包围的 O，因此，边界上的 O 不能被填充。那么我们预先把和边界相连的 O 都填充为其他符号，在处理完 board 内部的 O 的时候，在把其他符号替换为 O 即可。
class Solution {
public:
    int n, m;
    void solve(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        // 替换边界
        for (int i = 0; i < n; i++) {
            dfs(i, 0, board, '+');
            dfs(i, m-1, board, '+');
        }
        for (int i = 0; i < m; i++) {
            dfs(0, i, board, '+');
            dfs(n-1, i, board, '+');
        }
        // 填充内部的 O
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {
                    dfs(i, j, board, 'X');
                }
            }
        }
        // 替换回来
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                }
            }
        }
    }

// dfs 查找相连的 O
    void dfs(int r, int c, vector<vector<char>>& board, char pad) {
        if (r < 0 || c < 0 || r >= n || c >= m) {
            return;
        }
        if (board[r][c] == 'O') {
            board[r][c] = pad;
            dfs(r + 1, c, board, pad);
            dfs(r - 1, c, board, pad);
            dfs(r, c + 1, board, pad);
            dfs(r, c - 1, board, pad);
        }
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK