DFS与BFS题解：[kaungbin]带你飞简单搜索解题报告

DFS and BFS

在解题前我们还是大致讲一下dfs与bfs的。（我感觉我不会bfs）

1.DFS

dfs(深度优先算法) 正如其名，dfs是相当的深度，不走到最深处绝不回头的那种。

深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。

而使用递归可以很好地实现深度优先搜索。

在使用递归时，系统会调用一个叫系统栈的东西来存放递归中每一层的状态，因此使用递归来实现DFS的本质其实还是栈。

下面DFS的模版：

void dfs()  {  //参数用来表示状态

    if(到达终点状态)  {

        ...//根据题意添加

        return;

    }

    if(越界或者是不合法状态)

        return;

    if(特殊状态)//剪枝

        return ;

    for(扩展方式)  {

        if(扩展方式所达到状态合法)  {

            修改操作;//根据题意来添加

            标记；

            dfs（）；

            (还原标记)；

            //是否还原标记根据题意

            //如果加上（还原标记）就是 回溯法

        }

    }

}

然后开始今天的题解

题目来自https://vjudge.net/problem/POJ-3984

迷宫问题

1.题目描述：2

定义一个二维数组：


int maze[5][5] = {


	0, 1, 0, 0, 0,


	0, 1, 0, 1, 0,


	0, 0, 0, 0, 0,


	0, 1, 1, 1, 0,


	0, 0, 0, 1, 0,


};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

2.题目分析
这道题就属于搜索中的基础题了，即给你一个地图，让你在地图中找出最短的路径.
而在搜索题中我们可以用上面所讲到的dfs(深度优先算法)，还有一种就是bfs(广度优先算法)。两种方法都可以。
但是这道题是遍历迷宫的顺序，所以dfs不太好用，所以我们选择bfs，通过使用队列结构来存储路径。

下面是代码：

#include<stdio.h>

struct node{

    int x; //x坐标

    int y; //y坐标

    int pre; //来出发点

};

int book[6][6];  //用来记录点是否访问过

int map[6][6];   //记录图

struct node queue[20]; //存储路径的队列

void print(struct node a) //实现路径输出的函数

{

    if(a.pre==-1)

    {

        printf("(%d, %d)\n",a.x,a.y);

        return ;

    }

    else

    {

        print(queue[a.pre]);

        printf("(%d, %d)\n",a.x,a.y);

    }

}

int main()

{

    int i,j,k,m,n,x,y;

    int head,tail;

    for(i=0;i<5;i++)

    {

        for(j=0;j<5;j++)

        {

            scanf("%d",&map[i][j]);

        }

    }

    head=0;

    tail=0;

    queue[tail].x=0;

    queue[tail].y=0;

    queue[tail].pre=-1;

    book[0][0]=1;

    tail++;

    while(head<tail) //当队列为空时跳出，说明搜索没有找到可行路径

    {

        int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //定义出四个方向

        int flag=0;

        for(i=0;i<4;i++)  //从当前点往四周探索

        {

            int nextx=queue[head].x+next[i][0];

            int nexty=queue[head].y+next[i][1]; //实现移动

            if(nextx<0||nextx>5||nexty<0||nexty>5) //超出了边界则跳出

            {

                continue;

            }

            if(book[nextx][nexty]==0&&map[nextx][nexty]==0) //当点未被访问过且是可行点才入队

            {

                book[nextx][nexty]=1;

                queue[tail].x=nextx;

                queue[tail].y=nexty;

                queue[tail].pre=head;

                tail++;

            }

            if(nextx==4&&nexty==4) //到达了目的地，毫无疑问地跳出结束循环

            {

                flag=1;

                break;

            }

        }

        if(flag) //到达目的地后调用函数输出路径

        {

            print(queue[tail-1]);

            break;

        }

        head++; //出队

    }

    return 0;

}

主要注意的是队列的使用，其他都ok

巴特西

DFS与BFS题解：[kaungbin]带你飞简单搜索解题报告

迷宫问题

最新文章

热门文章

巴特西

DFS与BFS题解：[kaungbin]带你飞 简单搜索 解题报告

迷宫问题

最新文章

热门文章

DFS与BFS题解：[kaungbin]带你飞简单搜索解题报告