手机版
你好,游客 登录 注册
背景:
阅读新闻

C语言递归回溯法迷宫求解

[日期:2017-01-12] 来源:Linux社区  作者:superxinyu [字体: ]

本例将随机产生一个10*10的迷宫输出后,在下面输出此迷宫的解法。

解法为从坐标(1,1)处进入,从(8,8,)出去,优先线路为先右后下再上最后为左。

不少人求解此题时运用的栈的相关知识,本例寻找线路的过程不运用进栈出栈,而是用回溯法“抹去”判断不行的线路。

话不多说,上代码。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>//包括根据当前时间产生随机数的函数
static int maze[10][10];
//创建迷宫
int creatmaze()
{
    srand((unsigned)time(NULL));
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            if((i==1&&j==1)||(i==8&&j==8))
                maze[i][j]=0;
            else
                maze[i][j]=rand()%3;//为保证墙的数目较少,产生的随机数1为墙,0和2为路
            if(maze[i][j]==2)
                maze[i][j]=0;
            if(maze[i][j]==1||i==0||i==9||j==0||j==9)//迷宫框架为墙
            {
                maze[i][j]=1;
                printf(" O ");
            }
            else
                printf("   ");
        }
        printf("\n");
    }
    printf("\n");
}
//输出线路(结果)
void printroute()
{
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            if(maze[i][j]==1)
                printf(" O ");
            else if(maze[i][j]==0)
                printf("   ");
            else if(maze[i][j]==2)
                printf(" X ");
        }
        printf("\n");
    }
}
//寻找线路
void findroute(int i,int j)
{
    if(i==8&&j==8)//边界条件,即找到出路
    {
        printroute();
        exit(0);
    }
    else
    {
        if(maze[i][j+1]!=1&&maze[i][j+1]!=2)//判断当前位置右边是否为墙(下同理)
        {
            maze[i][j]=2;//将2作为线路的标志
            j++;
            findroute(i,j);//递归
            j--;//回溯
            maze[i][j]=0;
        }
        if(maze[i+1][j]!=1&&maze[i+1][j]!=2)//
        {
            maze[i][j]=2;
            i++;
            findroute(i,j);
            i--;
            maze[i][j]=0;
        }
        if(maze[i-1][j]!=1&&maze[i-1][j]!=2)//
        {
            maze[i][j]=2;
            i--;
            findroute(i,j);
            i++;
            maze[i][j]=0;
        }
        if(maze[i][j-1]!=1&&maze[i][j-1]!=2)//
        {
            maze[i][j]=2;
            j--;
            findroute(i,j);
            j++;
            maze[i][j]=0;
        }
        if(i==1&&j==1&&maze[1][2]==1&&maze[2][1]==1)//此处用于判断入口右方和下方是否为通路,若两处均有墙则直接输出无路
        {
            printf("no way\n");
            exit(0);
        }
    }
}

int main()
{
    creatmaze();
    findroute(1,1);
    printf("no way\n");//没有找到出路

样例输出:

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-01/139480.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款