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

2017-01-12 07:46:06来源:cnblogs.com作者:还还不走人点击

本例将随机产生一个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");//没有找到出路}

 

 

样例输出:

 

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台