深搜

2019-11-17

深度优先搜索（DFS）

属于图算法的一种，英文缩写为DFS即Depth First Search.

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次；

深度优先遍历图的思想是，从图中某顶点v出发：

（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

深搜通过向下深入，向上回溯的方式搜索，类似栈它的空间效率高，然则找到的不必定是最优解，所以一些深搜需要高效的剪枝（优化）

深搜是通过函数的递归实现，所以递归次数过多，可能造成爆栈和超时，一般通过用栈模拟深搜过程防止爆栈，通过剪枝的方式防止超时。

2777: Hero in Maze 简单版

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte 总提交: 2145 测试通过:785

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。请你判断他是否能救出心爱的公主。(假设有路可以通到公主那就可以找到公主)。

输入

题目包括多组测试数据。
每组测试数据以两个整数n,m(0<n, m≤20)开头，分别代表迷宫的长和高。紧接着有m行，n列字符，由”.”，”*”，”P”，”S”组成。其中
“.” 代表能够行走的空地。
“*” 代表墙壁，Jesse不能从此通过。
“P” 是公主所在的位置。
“S” 是Jesse的起始位置。
Jesse只能选择上、下、左、右任意一方向走一步。
输入以0 0结束。

输出

如果能救出公主输出YES，否则输出NO。

样例输入

4 4

….
….
….
S**P
4 4
….
….

****

S**P

0 0

样例输出

YES

#include <bits/stdc++.h>
using namespace std;
char q[25][25];
int sx,sy,px,py;     
int f,n,m;
int x[]={1,-1,0,0};
int y[]={0,0,1,-1};
void dfs(int xx,int yy){
    if(xx==px && yy==py )   //如果找到返回
    {
        f=1;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int dx=xx+x[i];
        int dy=yy+y[i];
        if(dx<n && dx>=0 && dy<m && dy>=0 && q[dx][dy]!='*')  //在图内且能走
        {
            q[dx][dy]='*';          //图上修改为不能走
            ///printf("%d %d\n",dx,dy);
            dfs(dx,dy);            //递归
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m),n||m)
    {
        f=0;
        for(int i =0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                q[i][j]=getchar();
                if(q[i][j]=='S')sx=i,sy=j;
                else if(q[i][j]=='P')px=i,py=j;
            }
        }
        dfs(sx,sy);
        printf("%s\n",(f? "YES":"NO"));
    }
    return 0;
}