DFS
关于dfs，我的理解就是深度搜索，找到所有与入口相连的路径，可以用于迷宫求出口，利用递归的思想，进行搜索返回所有值。
比如，给你两个值分别表示迷宫的长和宽，迷宫有一个入口，一个出口，判断能否从迷宫出来，入口用”s“表示，出口用“e“表示，墙壁用”#“表示，路用”.“表示
输入：3 4
s...
.##.
#..e
4 4
s...
..##
#.##
###e
输出：You can gou out!
Trapped!
#include "pch.h"
#include <cstdio>
#include <cstring>
#include <queue>
#include<cstdio>
#include <algorithm>
#include <iostream>
#include <istream>
using namespace std;
int n, m, si, sj, ei, ej;
char ditu[30][30];
int flag[30][30];
int s = 0;
void sou(int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= m || flag[x][y] == 1)
return;
if (x == ei && y == ej)
s = 1;
//把使用的地方标记为1，防止下次再用
flag[x][y] = 1;
//四个方向
sou(x + 1, y);
sou(x - 1, y);
sou(x, y + 1);
sou(x, y - 1);
}
int main()
{
int i, j;
while (cin >> n >> m)
{
getchar();
s = 0;
memset(flag, 0, sizeof(flag));//还原flag，flag用来标记墙壁并且标记使用过的地方
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
cin >> ditu[i][j];//输入地图
if (ditu[i][j] == 's')
{
si = i;
sj = j;
}
if (ditu[i][j] == 'e')
{
ei = i;
ej = j;
}
if (ditu[i][j] == '#')
flag[i][j] = 1;
}
getchar();
}
sou(si, sj);//查找
if (s == 0)
cout << "Trapped!" << endl;
else
cout << "You can go out!" << endl;
}
return 0;
}
转载于:https://www.cnblogs.com/monster-blog/p/10758918.html
