深度优先搜索
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;
}