C語言遞歸回溯法迷宮求解

本例將隨機產生一個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");//沒有找到出路
} 

樣例輸出：