深搜算法实例:老鼠走迷宫(一)

  1. 云栖社区>
  2. 博客>
  3. 正文

深搜算法实例:老鼠走迷宫(一)

谙忆 2015-08-22 11:56:00 浏览515
展开阅读全文

这个是简单的深搜,应该输入深搜中抛砖型的,联系下代码,回顾一下深搜的思想。
本题的要求是,在开始点(1,1)和终点(5,5)放一只老鼠,让老鼠找到一条路径走出去(暂时不考虑最短路径),找到后输出路径。
最简单的想法就是对于上下左右四个进行刨根型的搜索,找到就返回输出,进入死胡同了就原路返回,找最近的有其他路径的点,继续搜索,知道找出为止。
下面是代码部分。


#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 1
#define FAIL 0

int visit(int,int);
void map();
void route();

int maze[7][7]={
    {2,2,2,2,2,2,2},
    {2,0,0,0,0,0,2},
    {2,0,0,0,2,0,2},
    {2,0,0,0,0,2,2},
    {2,2,0,2,0,2,2},
    {2,0,0,0,0,0,2},
    {2,2,2,2,2,2,2}};

int start_i=1,start_j=1;
int end_i=5,end_j=5;
int flag=FAIL;

int main(void)
{
    map();
    route();
    return 0;
}

void map()
{
    int i,j;
    printf("显示迷宫:\n");
    for(i=0;i<7;i++)
    {
        for(j=0;j<7;j++)
            if(maze[i][j]==2)
                printf("*");
            else
                printf(" ");
        printf("\n");
    }
}

void route()
{
    int i,j;
    if(visit(start_i,start_j)==FAIL)
        printf("\n此路不同!换个地图!");
    else{
            printf("\n显示路径:\n");
            for(i=0;i<7;i++)
            {
                for(j=0;j<7;j++)
                    if(maze[i][j]==2)
                        printf("*");
                    else if(maze[i][j]==1)
                        printf("@");
                    else
                        printf(" ");
                printf("\n");
            }
        }
}

int visit(int i,int j)
{
    maze[i][j]=1;
    if(i==end_i && j==end_j)
        flag=SUCCESS;
    if(flag==FAIL && maze[i][j+1]==0)
        visit(i,j+1);
    if(flag==FAIL && maze[i+1][j]==0)
        visit(i+1,j);
    if(flag==FAIL && maze[i-1][j]==0)
        visit(i-1,j);
    if(flag==FAIL && maze[i][j-1]==0)
        visit(i,j-1);
    if(flag==FAIL)
        maze[i][j]=0;
    return flag;
}

从上面的分析中我们只看visit()函数
我们用了0,1,2三个数表示地图某一点的状态:

1.0表示无障碍
2.1表示通路中的一点
3.2表示障碍

并用一个数组保存
我们看到,在visit()函数中进行了函数自身调用(可以看做是递归),这里是先朝着右边搜索,然后是上,下,左,如果还能往下走就接着往下走,走到不能再走为止。如果是死胡同,则就退到上一节点(这就是回溯了,在代码中的maze[i][j]=0表现),在新的节点继续试探,看有没有能一直走到终点的路线,一旦找到就马上返回(在flag=SUCCESS这里说明,找到一条就不再找别的路线了),没有的话就接着深搜,直到遍历完所有的节点发现到底有没有通路存在。
总的来说这个作为深搜的入门挺不错,没有难度,还有点小趣,同时还能再回顾下递归的思想

网友评论

登录后评论
0/500
评论
谙忆
+ 关注