最近做了一個用C語言迷宮求解的題目，來分享一下。
題目要求：//迷宮的布局放入到一個二維的數組中 1代表該地方走不通為牆，0代表該地方可以走通，打印出來走的順序
//0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
const int mizu[10][10] = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1, //0
1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1, //1
1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1, //2
1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1, //3
1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1, //4
1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1, //5
1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1, //6
1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1, //7
1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1, //8
1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 //9
} ;
分析：
1、可以利用C語言的棧來實現，起點坐標為（1,1），如果該步能走通，把該步的坐標入棧，且對該坐標進行標記，代表已經走過。
2、然後以該坐標（x，y）為中心進行，對該坐標的上(x,y-1)、右（x+1,y）、下(x,y-1)、左(x-1,y)的坐標順時針進行判斷可否走通（可否走通的條件為：該坐標的值為0，同時該步沒有走過），尋找下一步坐標，如果找到了下一步，就接著入棧。
3、如果判斷出來該坐標的四周的四個坐標（上、右、下、左）都不能夠走通，則把該坐標出棧。
4、如果棧不空則接著往下找，如果棧空，則結束，沒有可行的通路。
5、這樣一直進行，找到出口坐標則結束，找到可行的通路
下面是我寫的代碼：有問題大家多交流。
#include <stdio.h>
#include <stdlib.h>
//迷宮的布局放入到一個二維的數組中
//0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
const int mizu[10][10] = {1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1, //0
1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1, //1
1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1, //2
1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1, //3
1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1, //4
1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1, //5
1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1, //6
1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1, //7
1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1, //8
1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 //9
} ;
int flag[10][10] = {0} ;
typedef int TypeData ;
typedef struct node{
TypeData datax ;
TypeData datay ;
struct node* next ;
}Node , *LinkList ;
typedef struct stack{
LinkList top ;
}STACK ;
//************************函數聲明******************************
int stackInit(STACK* s ) ;
int pushStack(STACK* s ,TypeData x , TypeData y) ;
void popStack(STACK* s , TypeData* x , TypeData* y) ;
int isStackEmpty(STACK* s) ;
int mizePath(STACK* s ,TypeData end_x , TypeData end_y ) ;
int passMizu(TypeData x , TypeData y ) ;
//**********************************************************
//鏈棧的初始化
int stackInit(STACK* s )
{
LinkList p = (LinkList)malloc(sizeof(Node)) ;
if(!p) return -1 ;
p->next = NULL ;
p->datax = -1 ;
p->datay = -1 ;
s->top = p ;
return 1 ;
}
//入棧操作
int pushStack(STACK* s ,TypeData x , TypeData y)
{
LinkList p = (LinkList)malloc(sizeof(Node)) ;
if(!p) return -1 ; //分配內存失敗
p->datax = x ;
p->datay = y ;
p->next = s->top ;
s->top = p ;
return 1 ;
}
//出棧的操作
void popStack(STACK* s , TypeData* x , TypeData* y)
{
LinkList p = s->top ;
s->top = p->next ;
(*x) = p->datax ;
(*y) = p->datay ;
free(p) ;
}
//判斷棧是否為空
//1 空 0 不空
int isStackEmpty(STACK* s)
{
if(s->top->datax == -1) //棧空
return 1 ;
return 0 ;
}
//找到最佳路徑
//end_x , end_y為結束的坐標
//上 、右、下、左尋找方式
int mizePath(STACK* s ,TypeData end_x , TypeData end_y )
{
pushStack(s , 1 ,1) ; //初始坐標壓棧
TypeData nowx = 1 , nowy = 1 ;
flag[nowx][nowy] = 1 ; //該坐標已經被占用不能再通過
while(!isStackEmpty(s)) //當棧不空的時候
{
if((nowx == end_x)&&(nowy == end_y))
{
return 1 ;
}
// printf("nowx = %d nowy = %d\n",nowx , nowy) ;
// system("PAUSE") ;
if(passMizu(nowx , nowy-1)) //先向上尋找
{
nowy = nowy - 1 ; //坐標更改
pushStack(s , nowx , nowy) ; //把該坐標壓棧
flag[nowy][nowx] = 1 ; //該坐標已經被占用不能再通過
}
else if(passMizu(nowx+1 , nowy)) //向右尋找
{
nowx = nowx + 1 ;
pushStack(s , nowx , nowy) ; //把該坐標壓棧
flag[nowy][nowx] = 1 ; //該坐標已經被占用不能再通過
}
else if(passMizu(nowx , nowy+1)) //向下尋找
{
nowy = nowy + 1 ;
pushStack(s , nowx , nowy) ; //把該坐標壓棧
flag[nowy][nowx] = 1 ; //該坐標已經被占用不能再通過
}
else if(passMizu(nowx-1 , nowy)) //向左尋找
{
nowx = nowx - 1 ;
pushStack(s , nowx , nowy) ; //把該坐標壓棧
flag[nowy][nowx] = 1 ; //該坐標已經被占用不能再通過
}
else //都行不通
{
popStack(s , &nowx , &nowy) ;
}
} //while(!isStackEmpty(s)) //當棧不空的時候
return 0 ;
}
//判斷該位置是否可通
int passMizu(TypeData x , TypeData y )
{
if((x > 9)||(y > 9))
return 0 ; //越界不可通
if(mizu[y][x])
return 0 ; //該位置是牆，不可通
if(flag[y][x])
return 0 ; //該坐標已經被占用，不能通過
return 1 ;
}
//打印棧中的數據
int printStackData(STACK s)
{
STACK temp ; //新建一個臨時的棧
stackInit(&temp) ;
if(s.top->datax == -1) return 0 ; //棧為空
while(s.top->datax != -1)
{
pushStack(&temp,s.top->datax,s.top->datay);
s.top = s.top->next ;
}
while(temp.top->datax != -1)
{
printf("(%d,%d)\n",temp.top->datax , temp.top->datay) ;
temp.top = temp.top->next ;
}
return 1 ;
}
int main()
{
STACK mi_stack ;
int i = 0 , j = 0 ;
stackInit(&mi_stack) ;
if(mizePath(&mi_stack , 8 , 8))
{
printStackData(mi_stack) ; //把坐標倒敘打印出來
}
else printf("沒有通路！\n") ;
return 0 ;
}
