深度优先搜索
DFS是可用于遍历树或者图的搜索算法,DFS与回溯法类似,一条路径走到底后需要返回上一步,搜索第二条路径。在树的遍历中,首先一直访问到最深的节点,然后回溯到它的父节点,遍历另一条路径,直到遍历完所有节点。图也类似,如果某个节点的邻居节点都已遍历,回溯到上一个节点。
深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用栈数据结构来辅助实现DFS算法。根据深度深度优先搜索的特点,采用递归函数实现比较简单。但也可以不采用递归。
例题 【题解】
本文代码严格按照Linux C++标准编写,空格、缩进符合标准。
1.[入门] 扫地机器人
// [入门] 扫地机器人 // Author:mxdyeah Date:20240529 #include <bits/stdc++.h> using namespace std; const int maxn = 101; int n, m; int a[maxn][maxn]; int fx[5] = {0, 0, 1, 0, -1}; int fy[5] = {0, 1, 0, -1, 0}; void p1554(int x, int y, int k) { a[x][y] = k; int tx, ty; for (int i = 1; i <= 4; i++) { tx = x + fx[i]; ty = y + fy[i]; if (tx >= 1 and tx <= n and ty >= 1 and ty <= m and a[tx][ty] == 0) { p1554(tx, ty, k + 1); } } } int main() { cin >> n >> m; p1554(1, 1, 1); int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (a[i][j] < 10) { cout << " "; } cout << " "; cout << a[i][j]; } cout << endl; } return 0; }
2.【基础】迷宫出口
// 【基础】迷宫出口 // Author:mxdyeah Date:20240529 #include<bits/stdc++.h> using namespace std; int a[110][110]; int n, s1, s2, e1, e2; bool f = false; void mxdyeah(int x, int y) { int fx[5] = {0, 0, 1, 0, -1}; int fy[5] = {0, 1, 0, -1, 0}; a[x][y] = 1; int tx, ty; for (int i = 1; i <= 4; i++) { tx = x + fx[i]; ty = y + fy[i]; if (tx >= 1 and tx <= n and ty >= 1 and ty <= n and a[tx][ty] == 0) { if (tx == e1 && ty == e2) { f = true; } else { mxdyeah(tx, ty); } } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } cin >> s1 >> s2 >> e1 >> e2; if (a[s1][s2] == 1 or a[e1][e2] == 1) { cout << "NO"; } else { mxdyeah(s1, s2); if (f == true) { cout << "YES"; } else { cout << "NO"; } } return 0; }
3.数池塘(四方向) USACO
// Author:mxdyeah Date:20240529 #include<bits/stdc++.h> using namespace std; int n, m, ans; int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; char a[105][105]; int vis[105][105]; void dfs(int xx, int yy) { vis[xx][yy] = 1; for (int i = 0; i < 4; i++) { int x = xx + dx[i], y = yy + dy[i]; if (x >= 0 && y >= 0 && x < n && y < m && !vis[x][y] && a[x][y] == 'W') { dfs(x, y); } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!vis[i][j] && a[i][j] == 'W') { ans++; dfs(i, j); } } } cout << ans << endl; return 0; }
4.数池塘(八方向)
//Author:mxdyeah #include <bits/stdc++.h> using namespace std; int fx[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1}; int fy[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1}; int n, m, cnt = 0; char a[110][110]; void mxd(int x, int y) { a[x][y] = '.'; int tx, ty; for (int i = 1 ; i <= 8 ; i++) { tx = x + fx[i]; ty = y + fy[i]; if (a[tx][ty] == 'W') mxd(tx, ty); } } int main() { scanf("%d%d", &n, &m); for (int i = 1 ; i <= n ; i++) for (int j = 1 ; j <= m ; j++) cin >> a[i][j]; for (int i = 1 ; i <= n ; i++) for (int j = 1 ; j <= m ; j++) if (a[i][j] == 'W') { cnt++; mxd(i, j); } printf("%d", cnt); return 0; }
5.奶牛和草丛 USACO
//Author:mxdyeah # include <bits/stdc++.h> using namespace std; int n, m; char a[104][104]; long long num; void dg(int x, int y) { if (x < 1 || x > n || y < 1 || y > m) return ; if (a[x][y] == '#') { a[x][y] = '.'; dg(x + 1, y); dg(x - 1, y); dg(x, y + 1); dg(x, y - 1); } return ; } int main() { cin >> n >> m; for (int u = 1; u <= n; u++) { for (int v = 1; v <= m; v++) { cin >> a[u][v]; } } for (int u = 1; u <= n; u++) { for (int v = 1; v <= m; v++) { if (a[u][v] == '#') { dg(u, v); num += 1; } } } cout << num; return 0; }