8
算法系列:优先遍历
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.
主要收录深度优先遍历和宽度优先遍历,深度优先遍历一般可以与回溯、递归、树等方法联用,达到优雅遍历的效果,而宽度优先搜索可以用到最短路问题的求解中。
- 为什么不用 bfs 去遍历?第一是因为 bfs 写起来麻烦,不如 dfs 直观。第二是在某些查找到满足情况即可退出的应用而言,bfs 需要一层一层的去检查,效率很低。
- 为什么不用 dfs 去求最短路?如上所示,bfs 可以一层一层的检查,相对 dfs 更容易查到最短路。
130. 被围绕的区域
给你一个 m x n
的矩阵 board
,由若干字符 'X'
和 'O'
,找到所有被 'X'
围绕的区域,并将这些区域里所有的 'O'
用 'X'
填充。
- 那么如何填充内部的
O
呢?这里就要用到dfs
,首先遍历board
,如果遇到了O
,那个和这个O
相邻的O
也要被填充,此时就要使用dfs
来查找相邻的O
- 由于只填充被
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);
}
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK