用c實作迷宮問題（利用堆疊和遞回）
#include<stdio.h>
#include<stdlib.h>
#define m 6
#define n 8
#define STACK_INIT_SIZE 100
typedef struct
{
int x,y;
}SElemType; //定義結構表示坐標
typedef struct
{
SElemType stack[STACK_INIT_SIZE];
int top;
}SqStack; //堆疊
int maze[m+2][n+2]=
{
/*0,1,2,3,4,5,6,7,8,9*/
/*0*/ {1,1,1,1,1,1,1,1,1,1},
/*1*/ {1,0,1,1,1,0,1,1,1,1},
/*2*/ {1,1,0,1,0,1,1,1,1,1},
/*3*/ {1,0,1,0,0,0,0,0,1,1},
/*4*/ {1,0,1,1,1,0,1,1,1,1},
/*5*/ {1,1,0,0,1,1,0,0,0,1},
/*6*/ {1,0,1,1,0,0,1,1,0,1},
/*7*/ {1,1,1,1,1,1,1,1,1,1},
}; //1表示有障礙 ，0表示可以過
int t[m+2][n+2]={0}; //與迷宮相同的二維陣列，用來表示該條路有沒有走；（很重要！！！）
SElemType Move[8]= //記錄走的方向；
{
{0,1},{1,1},{1,0},{1,-1},
{0,-1},{-1,-1},{-1,0},{-1,1}
};
int sum=0; //記錄有幾條路徑
//列印路徑
void Print(int sum,SqStack a)
{
int i;
printf("迷宮的第%d條路徑如下:\n",sum);
for(i=0;i<=a.top;i++)
printf("(%d,%d)->",a.stack[i].x,a.stack[i].y);
printf("出口\n\n");
printf("\n");
}
//符合規則的壓入堆疊
void Push_SqStack(SqStack *s,SElemType x) //x是經過判斷符合條件的走向
{
if(s->top==STACK_INIT_SIZE-1)
printf("\n堆疊滿!");
else
{
s->top++;
s->stack[s->top]=x;
}
}
//檢查堆疊是否為空
int Empty_SqStack(SqStack *s)
{
if(s->top==-1)
return 1;
else
return 0;
}
//洗掉堆疊頂的元素，退后操作
void Pop_SqStack(SqStack *s)
{
if(Empty_SqStack(s))
{
printf("\n堆疊空!");
exit(0);
}
else
{
s->top--;
}
}
void path(int x,int y,SqStack elem) //找出口的函式 （利用遞回）
{
int i,a,b;
SElemType temp;
if(x==6&&y==8)
{
sum++;
Print(sum,elem);
}
else
{
for(i=0;i<8;i++) //遍歷八個方向
{
a=x+Move[i].x;
b=y+Move[i].y;
if(!maze[a][b]&&!t[a][b]) //用t防止往回走
{
temp.x=a;temp.y=b;
t[a][b]=maze[a][b]=1; //用陣列t,M記錄這個位置已經走過了
Push_SqStack(&elem,temp);
path(a,b,elem); //此處開始遞回！（遞回的出口要么走到出口，要么回圈走完也沒走下一步，即走入死路需回溯）
t[a][b]=maze[a][b]=0; //回溯之后需要將這個位置清空，表示這條路沒有走過
Pop_SqStack(&elem);
}
}
}
}
int main()
{
SqStack *s;
s=(SqStack *)malloc(sizeof(SqStack));
s->stack[0].x=1;
s->stack[0].y=1;
s->top=0;
t[1][1]=maze[1][1]=1;
path(1,1,*s);
return 0;
}
//代碼參考CSDN某大佬
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/280761.html
標籤：新手樂園
上一篇：有沒大佬教我指標，學了一學期的C語言，前面還好，直到指標就不知道咋辦了。差點掛科了
下一篇：鏈表問題