C++算法
C++ 算法：DFS 与 BFS 详解及经典例题
C++ 中深度优先搜索（DFS）和广度优先搜索（BFS）的核心思想、实现方式及适用场景。DFS 基于栈结构，适合路径探索、回溯问题；BFS 基于队列，保证无权图最短路径。文章通过八皇后、迷宫、马的遍历、岛屿数量等经典例题对比两种算法的差异，并涵盖多源最短路、拓扑排序等进阶应用。
C++ 中深度优先搜索（DFS）和广度优先搜索（BFS）的核心思想、实现方式及适用场景。DFS 基于栈结构，适合路径探索、回溯问题；BFS 基于队列，保证无权图最短路径。文章通过八皇后、迷宫、马的遍历、岛屿数量等经典例题对比两种算法的差异，并涵盖多源最短路、拓扑排序等进阶应用。
DFS（Depth-First Search）是一种通过递归或显式栈结构实现的搜索算法，其核心思想是'一条路走到黑，不撞南墙不回头'。它会沿着某条分支尽可能深入，直到无法继续时回溯到上一个分叉点。
非递归实现（显式栈）
void dfs_iterative(int start, vector<vector<int>>& graph) {
stack<int> st;
vector<bool> visited(graph.size(), false);
st.push(start);
visited[start] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
st.push(v);
}
}
}
}
递归实现（以图的遍历为例）
void dfs(int u, vector<bool>& visited, vector<vector<int>>& graph) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, visited, graph);
}
}
}
思路：二进制来表示
代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
using namespace std;
int n;
#define MASK(n) ((1 << (n + 1)) - 2)
// 如 6 得到的是 1000 0000 -> 111 1110,零位上的 1 不用
unordered_map<int, int> ind;
int tot = 3;
int arr[20];
void out() {
for (int i = 1; i <= n; i++) {
if (i > 1) cout << " ";
printf("%d", arr[i]);
}
printf("\n");
tot--;
return;
}
int dfs(int i, int t1, int t2, int t3) {
if (i > n) {
if (tot) out();
return 1;
}
int ans = 0;
for (int t = t1; t; t -= (-t & t)) {
int j = ind[-t & j];
if ((t2 & (1 << (i + j - 1))) && (t3 & (1 << (i - j + n)))) // 正斜线和反斜线
{
arr[i] = j;
ans += dfs(i + 1, t1 ^ (1 << j), t2 ^ (1 << (i + j - 1)), t3 ^ (1 << (i - j + n)));
// 把 t1 中的 j 标记为 0，然后向左移动一位
}
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < 2 * n; i++) ind[1 << i] = i;
int ans = dfs(1, MASK(n), MASK(2 * n - 1), MASK(2 * n - 1)); // 列，正斜边，反斜边
cout << ans << "\n";
return 0;
}
题目链接：P1135 奇怪的电梯 - 洛谷
思路：
dis[] 和 to[]，分别表示到某层的最少按钮数和按键，dfs(k, a) 中 k 表示使用的按钮数目，a 表示到某一层，当 dis[] 记录到的到某层的最少按钮数小于等于 k 时，就可递归返回。代码如下：
#include <iostream>
using namespace std;
const int N = 205;
int to[N], dis[N]; // 起点到每个点最短距离
int n;
void dfs(int k, int a) {
if (dis[a] <= k) return;
dis[a] = k; // 刷新到 a 的最短距离
if (a + to[a] <= n) dfs(k + 1, a + to[a]);
if (a - to[a] >= 1) dfs(k + 1, a - to[a]);
}
int main() {
int a, b;
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
cin >> to[i]; // 输入每个按钮的值
dis[i] = n + 1;
}
dfs(0, a);
printf("%d\n", dis[b] == n + 1 ? -1 : dis[b]);
return 0;
}
思路：
dfs(u, ind, sum) 分别表示当前已经选择了几个数，当前这一层可以选择的最小数字，所选当前的和值，is_prime() 函数则用来判断是否为质数。代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 25;
int a[N];
int n, k;
long long ans = 0; // 计算素数的数量
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) return false;
}
return true;
}
void dfs(int u, int ind, int sum) {
if (u == k) {
if (is_prime(sum)) ans++;
return;
}
for (int i = ind; i <= n; i++) {
dfs(u + 1, i + 1, sum + a[i]);
}
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(0, 1, 0);
printf("%lld\n", ans);
return 0;
}
题目链接：P1605 迷宫 - 洛谷
思路：
代码如下：
#include <iostream>
using namespace std;
const int N = 7;
int g[N][N];
int n, m, t, sx, sy, ex, ey;
int ans = 0; // 记录方法的数量
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void dfs(int x, int y) {
if (x == ex && y == ey) {
ans++;
return;
}
g[x][y] = 0; // 表示当前点遍历过
for (int i = 0; i < 4; i++) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (g[dx][dy] == 0) continue;
dfs(dx, dy);
}
g[x][y] = 1;
}
int main() {
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) g[i][j] = 1;
}
cin >> sx >> sy >> ex >> ey;
for (int i = 0; i < t; i++) {
int x, y;
cin >> x >> y;
g[x][y] = 0;
}
dfs(sx, sy);
cout << ans << "\n";
return 0;
}
题目链接：P1433 吃奶酪 - 洛谷
思路：
dp[next_t][to] 表示达到当前状态，最后一个吃掉的奶酪编号时的最小距离。代码如下：
#include <iostream>
#include <cmath>
using namespace std;
const int N = 17;
double ans = 1e9;
int n;
double x[N], y[N];
double dis[N][N]; // dis[i][j] 表示从第 i 个奶酪到第 j 个奶酪的距离
double dp[70000][20]; // 2^16, 第一个位置表示状态编码，第二个位置表示达到当前状态，最后一个吃掉的奶酪编号
int ind[70000]; // 权值映射
double d(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
void dfs(int t, int now, double s) {
if (t == 0) { // 吃掉了所有奶酪
if (s < ans) ans = s;
return;
}
for (int k = t; k; k -= (k & -k)) {
int to = ind[k & -k], next_t = t - (1 << to);
double l = s + dis[now][to];
if (dp[next_t][to] != 0 && dp[next_t][to] <= l) continue;
dp[next_t][to] = l;
if (ans <= l) continue;
dfs(next_t, to, l);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
x[0] = y[0] = 0; // 小老鼠位置
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
for (int i = 0; i <= n; i++) {
for (int j = i; j <= n; j++) dis[i][j] = dis[j][i] = d(i, j);
}
for (int k = 1, i = 0; i <= N; i++, k *= 2) ind[k] = i; // 权值到下标映射
dfs((1 << (n + 1)) - 2, 0, 0); // 当前位置状态码，所在奶酪下标，到达状态所走总路程
printf("%.2lf\n", ans);
return 0;
}
思路：
if (dfs(board, word, i, j, 0)) return true;，而不是 return dfs(board, word, i, j, 0);代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m;
bool st[505][505];
bool dfs(vector<vector<char>>& board, string word, int x, int y, int pos) {
if (pos == word.size()) return true;
// 向量的方式，定义上下左右四个位置
for (int i = 0; i < 4; i++) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < m && board[dx][dy] == word[pos] && !st[dx][dy]) {
st[dx][dy] = true;
if (dfs(board, word, dx, dy, pos + 1)) return true;
st[dx][dy] = false;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == word[0]) {
st[i][j] = true;
if (dfs(board, word, i, j, 1)) return true;
st[i][j] = false;
}
}
}
return false;
}
BFS（Breadth-First Search）通过队列逐层扩展搜索，保证先访问离起点最近的节点。其核心是'地毯式搜索，层层推进'。
标准实现（以图的遍历为例）
void bfs(int start, vector<vector<int>>& graph) {
queue<int> q;
vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
题目链接：P1443 马的遍历 - 洛谷
思路：
| （-1，-2） | （1，-2） | |||
|---|---|---|---|---|
| （-2，-1） | （2，-1） | |||
| （x，y） | ||||
| （-2，1） | （2，1） | |||
| （-1，2） | （1，2） |
这题如果用之前的 dfs（step，x，y）来表示则会超时，因此我们应该使用 BFS 算法层序遍历，遍历每一层，如果遍历了某个节点时，那么后续遍历这个节点绝对比之前找的 step 要大，层序遍历更适合求最短步长。
代码如下：
#include <iostream>
#include <queue>
using namespace std;
const int N = 405;
int dir[8][2] = { // 偏移量
{2, 1}, {-2, 1}, {2, -1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};
int dis[N][N];
int n, m;
struct Node {
Node(int x, int y, int s) : x(x), y(y), s(s) {}
int x, y, s;
};
void bfs(int a, int b) {
queue<Node> q;
q.push(Node(a, b, 0));
dis[a][b] = 0; // 从当前节点扩展到其他点
while (!q.empty()) {
Node now = q.front();
q.pop();
for (int k = 0; k < 8; k++) {
int dx = now.x + dir[k][0], dy = now.y + dir[k][1];
if (dx < 1 || dx > n) continue;
if (dy < 1 || dy > m) continue;
if (dis[dx][dy] != -1) continue;
q.push(Node(dx, dy, now.s + 1));
dis[dx][dy] = now.s + 1;
}
}
}
int main() {
int a, b;
cin >> n >> m >> a >> b;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dis[i][j] = -1; // 赋初值
}
}
bfs(a, b); // 到达当前点所花步数，(a,b) 表示当前所在位置
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << dis[i][j] << " ";
}
cout << "\n";
}
return 0;
}
思路：
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int n = maze.size(), m = maze[0].size();
queue<pair<int, int>> q;
q.push({entrance[0], entrance[1]});
vector<vector<int>> vis(n, vector<int>(m));
vis[entrance[0]][entrance[1]] = true;
int ans = 0;
while (!q.empty()) {
ans++;
int size = q.size();
while (size--) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int dx = x + dir[k][0], dy = y + dir[k][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && maze[dx][dy] == '.') {
if (dx == 0 || dx == n - 1 || dy == 0 || dy == m - 1) return ans;
q.push({dx, dy});
vis[dx][dy] = true;
}
}
}
}
return -1;
}
思路：
代码如下：
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> vis;
unordered_set<string> hash(bank.begin(), bank.end());
if (startGene == endGene) return 0;
if (!hash.count(endGene)) return -1;
string change = "ACGT";
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret = 0;
while (!q.empty()) {
ret++;
int size = q.size();
while (size--) {
string t = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
string tmp = t;
for (int j = 0; j < change.size(); j++) {
tmp[i] = change[j];
if (hash.count(tmp) && !vis.count(tmp)) {
if (tmp == endGene) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
思路：
代码如下：
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> hash(wordList.begin(), wordList.end());
unordered_set<string> vis;
if (hash.count(endWord) == 0) return 0;
queue<string> q;
q.push(beginWord);
vis.insert(beginWord);
int ret = 1;
while (!q.empty()) {
ret++;
int size = q.size();
while (size--) {
string t = q.front();
q.pop();
for (int i = 0; i < t.size(); i++) {
string tmp = t;
for (char ch = 'a'; ch <= 'z'; ch++) {
tmp[i] = ch;
if (hash.count(tmp) && !vis.count(tmp)) {
if (tmp == endWord) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
思路：
代码如下：
int m, n;
bool vis[55][55];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey) {
if (bx == ex && by == ey) return 0;
queue<pair<int, int>> q;
memset(vis, 0, sizeof(vis));
q.push({bx, by});
vis[bx][by] = true;
int step = 0;
while (!q.empty()) {
step++;
int size = q.size();
while (size--) {
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = a + dir[i][0], y = b + dir[i][1];
if (x >= 0 && x < n && y >= 0 && y < m && forest[x][y] && !vis[x][y]) {
if (x == ex && y == ey) return step;
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
// 1. 找出砍树顺序 (从小到大)
n = forest.size(), m = forest[0].size();
vector<pair<int, int>> trees;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (forest[i][j] > 1) {
trees.push_back({i, j});
}
}
}
sort(trees.begin(), trees.end(), [&](const pair<int, int> x, const pair<int, int> y) {
return forest[x.first][x.second] < forest[y.first][y.second];
});
// 2. 按照顺序砍树 -- 相邻树的最短距离
int bx = 0, by = 0;
int ret = 0;
for (auto& [a, b] : trees) {
int step = bfs(forest, bx, by, a, b);
if (step == -1) return -1;
ret += step;
bx = a, by = b;
}
return ret;
}
对于求的最终结果，我们有两种方式:
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
// dist[i][j] == -1 没有搜索过
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
// 1. 把所有点放入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
q.push({i, j});
}
}
}
// 2. 一层一层扩展
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1) {
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
}
return dist;
}
思路（正难则反）：
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int numEnclaves(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> vis(n, vector<bool>(m));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && grid[i][j] == 1) {
q.push({i, j});
vis[i][j] = true;
}
}
}
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid[x][y] == 1) {
q.push({x, y});
vis[x][y] = true;
}
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !vis[i][j]) ret++;
}
}
return ret;
}
思路：
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int n = isWater.size(), m = isWater[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (isWater[i][j]) {
dist[i][j] = 0;
q.push({i, j});
}
}
}
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1) {
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
}
return dist;
}
思路：
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int maxDistance(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j]) { // 所有陆地
dist[i][j] = 0;
q.push({i, j});
}
}
}
int ret = -1;
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1) {
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
ret = max(ret, dist[x][y]);
}
}
}
return ret;
}
思路：BFS 解决拓扑排序即可
代码如下：
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> d(numCourses, 0);
queue<int> q;
for (auto e : prerequisites) {
int u = e[0], v = e[1];
adj[u].emplace_back(v);
d[v]++;
}
for (int i = 0; i < numCourses; i++) {
if (d[i] == 0) q.push(i);
}
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (auto v : adj[u]) {
if (--d[v] == 0) q.push(v);
}
}
return cnt == numCourses;
}
思路：和上面类似。
代码如下：
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> d(numCourses, 0);
for (auto e : prerequisites) {
int v = e[0], u = e[1]; // e[0] <- e[1]
adj[u].push_back(v);
d[v]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (d[i] == 0) q.push(i);
}
vector<int> ans;
while (!q.empty()) {
int u = q.front();
q.pop();
ans.push_back(u);
for (auto v : adj[u]) {
if (--d[v] == 0) q.push(v);
}
}
return ans.size() != numCourses ? vector<int>() : ans;
}
题目链接：LCR 114. 火星词典 - 力扣
思路：将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以用拓扑排序解决。 如何搜集信息 (如何建图)
代码如下：
unordered_map<char, unordered_set<char>> edges;
unordered_map<char, int> in; // 入度
bool add(string &s1, string &s2) {
int n = min(s1.size(), s2.size());
int i = 0;
for (; i < n; i++) {
if (s1[i] != s2[i]) {
char a = s1[i], b = s2[i]; // a -> b
if (!edges.count(a) || !edges[a].count(b)) {
edges[a].insert(b);
in[b]++;
}
break;
}
}
if (i == s2.size() && i < s1.size()) return true;
return false;
}
string alienOrder(vector<string>& words) {
// 1. 建图 + 初始化入度
for (auto &s : words) {
for (auto &ch : s) {
in[ch] = 0;
}
}
// 2. 连接
int n = words.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (add(words[i], words[j])) return "";
}
}
// 3. 拓扑排序
queue<char> q;
for (auto &[a, b] : in) {
if (b == 0) q.push(a);
}
string ret;
while (!q.empty()) {
char t = q.front();
q.pop();
ret += t;
for (auto ch : edges[t]) {
if (--in[ch] == 0) q.push(ch);
}
}
for (auto &[a, b] : in) {
if (b != 0) return "";
}
return ret;
}
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归/非递归） | 队列 |
| 空间复杂度 | O(H)（路径深度） | O(V)（存储所有节点） |
| 最短路径 | 不保证（可能找到非最短解） | 保证（无权图最短路径） |
| 适用场景 | 路径存在性、回溯问题 | 最短路径、层级遍历 |
| 内存消耗 | 较低（适合深树） | 较高（适合宽图） |
思路：
DFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
typedef pair<int, int> PII;
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int target = image[sr][sc];
if (target == color) return image;
int m = image.size(), n = image[0].size();
queue<PII> q;
q.push({sr, sc});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
image[a][b] = color;
for (int i = 0; i < 4; i++) {
int x = a + dir[i][0], y = b + dir[i][1];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target) {
q.push({x, y});
}
}
}
return image;
}
BFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
typedef pair<int, int> PII;
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int target = image[sr][sc];
if (target == color) return image;
int m = image.size(), n = image[0].size();
queue<PII> q;
q.push({sr, sc});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
image[a][b] = color;
for (int i = 0; i < 4; i++) {
int x = a + dir[i][0], y = b + dir[i][1];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target) {
q.push({x, y});
}
}
}
return image;
}
思路：
DFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m;
bool vis[505][505]; // 标记该点是否用过
void dfs(vector<vector<char>>& grid, int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == '1') {
dfs(grid, dx, dy);
}
}
}
int numIslands(vector<vector<char>>& grid) {
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j] && grid[i][j] == '1') {
ret++;
dfs(grid, i, j);
}
}
}
return ret;
}
BFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool vis[305][305];
int m, n;
void bfs(vector<vector<char>>& grid, int i, int j) {
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = true;
while (q.size()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]) {
q.push({x, y});
vis[x][y] = true;
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !vis[i][j]) {
ret++;
bfs(grid, i, j); // 把这块陆地全部标记一下
}
}
}
return ret;
}
思路：
DFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m, cnt;
bool vis[505][505]; // 标记该点是否用过
void dfs(vector<vector<int>>& grid, int x, int y) {
vis[x][y] = true;
cnt++; // 记录每块岛屿的面积
for (int i = 0; i < 4; i++) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == 1) {
dfs(grid, dx, dy);
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
int ret = 0; // 统计最大数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j] && grid[i][j] == 1) {
cnt = 0;
dfs(grid, i, j);
ret = max(cnt, ret);
}
}
}
return ret;
}
BFS 方法如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool vis[51][51];
int m, n;
int bfs(vector<vector<int>>& grid, int i, int j) {
int count = 0;
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = true;
count++;
while (q.size()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int x = a + dir[k][0], y = b + dir[k][1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
q.push({x, y});
vis[x][y] = true;
count++;
}
}
}
return count;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !vis[i][j]) {
ret = max(ret, bfs(grid, i, j));
}
}
}
return ret;
}
使用场景如下：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online