深度优先搜索（深搜）——Deep First Search【例题：迷宫】

深度优先搜索

　　基本思想：先选择一种可能情况向前探索，在探索过程中，一点那发现原来的选择是错误的，就退回一步重新选择，继续向前探索，（回溯）反复进行。

思路：先随意选择一个方向，一步步向前试探，如果碰到死胡同说明该前进方向已经无路可走，这时首先看别的方向还是否有路可走，若有路可走，则该方向再次向前试探，若没有，则退回上一步，再看其他方向是否有路可走，，按此原则不断回溯和探索，知道找到入口为止。

框架：

int search(int ......)
{
    ;i<=方向总数;i++)
    if(满足条件)
    {
        保存结果;
        if(到达目的地)
            输出解;
        );
        恢复：保存结果之前的状态{回溯一步};
    }
}

具体代码实现如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 20
using namespace std;
int map[MAXN][MAXN];//表示迷宫地图
bool temp[MAXN][MAXN];//标记是否走过
]={,,,-};//横坐标的上下左右
]={-,,,};//纵坐标的上下左右
int m,n,total,sx,sy,fx,fy,l,r,t;//m,n:地图的长宽，total：方案总数，sx,sy起点的横纵坐标，fx,fy：终点的横纵坐标，t:障碍总数，l,r:障碍坐标
void search(int x,int y)//x,y:现在所在的点的坐标
{
    if(x==fx&&y==fy)//到达终点
    {
        total++;//方案总数
        return;    //返回继续寻找
    }
    ;i<=;i++)
        &&map[x+dx[i]][y+dy[i]]==)//判断下面要走的路是否有障碍
        &&y+dy[i]>=&&x+dx[i]<=n&&y+dy[i]<=m)//判断是否超越迷宫边界
        {
            temp[x+dx[i]][y+dy[i]]=;
            search(x+dx[i],y+dy[i]);
            temp[x+dx[i]][y+dy[i]]=;//回溯一步
        }
}
int main()
{
    cin>>n>>m>>t;
    ;i<=n;i++)
    ;j<=m;j++)
    map[i][j]=;
    cin>>sx>>sy;
    cin>>fx>>fy;
    ;i<=t;i++)
    {
        cin>>l>>r;
        map[l][r]=;
    }
    map[sx][sy]=;
    search(sx,sy);
    printf("%d",total);
    ;
}

巴特西

深度优先搜索（深搜）——Deep First Search【例题：迷宫】

最新文章

热门文章