关于dfs

佚名 6年前 (2019-04-24) 随笔 581人围观抢沙发百度已收录

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