关于dfs

时间:2021-10-31 00:18:10

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;
}