棧與迷宮問題課程設計

『壹』 【迷宮問題】用堆棧解迷宮

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>


#defineMAXM40
#defineMAXN60
intmaze[MAXM][MAXN];//01-障礙物
intm=40,n=60;//40行60列
intused[MAXM][MAXN];//記錄是否到過


intline[MAXM*MAXN];//記錄迷宮路線
intline_len;
intline_r[MAXM*MAXN];

intd[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//4個方向

voiddfs(intu,intv,intstep)
{
intx,y,i;
if(line_len!=0)
return;
if(u==m-1&&v==n-1)
{
line_len=step;
memcpy(line_r,line,line_len*sizeof(int));
return;
}

for(i=0;i<4;i++)
{
x=u+d[i][0];
y=v+d[i][1];
if(x>=0&&x<m&&y>=0&&y<n&&!used[x][y]&&maze[x][y]==0)
{
used[x][y]=1;
line[step]=x<<16|y;
dfs(x,y,step+1);
//used[x][y]=0;//不用退回來了，因為只需要一條路徑
}
}
}

intmain()
{
inti,j;
//隨機生成迷宮
srand(time(NULL));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=rand()%8==0?1:0;//是1的概率約1/8,通路的概率大些
maze[0][0]=maze[m-1][n-1]=0;//起始點和終端必須為0

line_len=0;
line[0]=0<<16|0;
memset(used,0,sizeof(used));
dfs(0,0,0);//(0,0)->(m-1,n-1)

if(line_len==0)
printf("沒有通路
");
else
{
for(i=0;i<line_len;i++)
printf("(%d,%d)
",(line_r[i]>>16)+1,(line_r[i]&0xffff)+1);
}

return0;
}

你給的那庫實在是沒什麼用的慾望，要最短路徑一般用廣度搜索，上面的代碼應該屬於深度搜索

『貳』 用棧做的迷宮問題，要代碼，急急急

1． 設計棧的抽象數據類型定義：
ADT Stack{
數據對象：D={ai|ai∈CharSet,i=1,2..,n}
數據關系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
基本操作:(這里僅列舉本題中使用的操作)
Creat()
操作結果:構建一個空棧。
Push()
操作結果:在棧頂插入新的元素。
Pop（）
操作結果：將棧頂元素彈出。
Empty（）
判斷棧是否為空
}ADT stack
2． 本程序包含了三個模塊
1） 主程序模塊：
void main()
{
輸入起點，終點；
處理命令；
輸出結果；
}
2） 棧模塊-----實現棧抽象數據類型
3） 迷宮模塊-----找出迷宮中的通路
3.求解迷宮中一條通路的偽碼
設定當前位置的初值為入口位置:
do{
若當前位置可通,
則{ 將當前位置插入棧頂; //納入路徑
若該位置是出口,則輸出迷宮圖,結束; //求得路徑存放在棧中
否則切換當前位置的東鄰方塊為新的當前位置;
}
否則{
若棧不空且棧頂位置尚有其他方向未被探索，
則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；
若棧不空但棧頂位置四周均不可通，
則{刪去棧頂位置； //後退一步，從路徑中刪去該通道
若棧不空，則重新測試新的棧頂位置，
直至找到一個可通的相鄰塊或出棧至棧空；
}
}
}while（棧不空）
（棧空說明沒有路徑存在）
二. 詳細設計
迷宮坐標位置類型
typedef struct maze{
int a;
int b;
int dir;
struct maze *next;
}mazestack;
棧的基本操作實現
1） 棧的初始化
mazestack *creat(){
mazestack * p;
p=(mazestack *)malloc(sizeof(mazestack)); //開辟坐標空間
if(!p)
return NULL; //開辟失敗，返回空值
p->next=NULL;
return p; //返回棧頂指針
}
2） 壓棧操作
mazestack * push(mazestack * p,int i,int j,int k) //p為棧頂指針
i , j為坐標參數，k為通路下一步方向代碼
{
mazestack * p1;
p1=(mazestack *)malloc(sizeof(mazestack)); //開辟坐標空間
if(!p1)
return NULL;
p1->a=i;
p1->b=j;
p1->dir=k; //將參數導入坐標空間
p1->next=p; //將新開辟空間壓入棧
p=p1; //移動棧頂指針到新棧頂
return p; //返回棧頂指針
}
3） 彈棧操作
mazestack * pop(mazestack *p, int *i,int *j,int *k) // p為棧頂指針，i，j為坐標參數，k為通路下一步方向代碼
{
mazestack *p1;
p1=p;
*i=p1->a;
*j=p1->b;
*k=p1->dir; //將空間中坐標和方向代碼導出
p=p->next; //將棧頂指針移動到新棧頂位置
free(p1); //釋放舊棧頂空間
return p;
}
4） 判斷棧空
int empty(mazestack *p) //p為所要判斷的指針
{
if(p->next==NULL){
return 1; //棧空，返回1
}
else return 0; /棧不空，返回0
}
改變路徑前進方向
int nextpos(int *i,int *j,int di) //i，j為迷宮坐標，di為下一步路徑的方向
{
switch(di){
case 1: *i=*i;*j=*j+1;break; //di=1 ，下一步向東
case 2: *i=*i+1;*j=*j;break; //di=2 ，下一步向南
case 3: *i=*i;*j=*j-1;break; //di=3 ， 下一步向西
case 4: *i=*i-1;*j=*j;break; //di=4 ， 下一步向北
}
return 1;
}
求迷宮路徑的演算法
mazestack * maze(int i1,int j1,int i2,int j2) //i1，j1為入口坐標，i2，j2為出口坐標
{
int a[10][10]={ 0,0,0,0,0,0,0,0,0,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0}; //具體迷宮形式
int i=i1,j=j1;
int k;
mazestack * p;
p=creat(); //建立棧
do{
if(a[i][j]==1){ //判斷路徑是否已經經過
a[i][j]=5; //沒有經過，則將該坐標進行標記
p=push(p,i,j,a[i][j]); //將該坐標點壓入棧中
if(i==i2&&j==j2){ //判斷壓入坐標是否為終點
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(a[i][j]>1){
a[i][j]=5;
printf(" %d ",a[i][j]);
}
else printf(" %d ",a[i][j]);
}
printf("\n\n");
} //壓入坐標是終點，將走迷宮圖輸出，其中路徑值為5

return p; //返回棧頂指針
}
nextpos(&i,&j,1); //壓入坐標不是終點，將坐標點向東移動一步
}
else{ //路徑已經經過
if(!empty(p)){
p=pop(p,&i,&j,&k); //退回一步
a[i][j]=k;
while(a[i][j]==4&&!empty(p)) //判斷該坐標周圍是否還有通路
{
a[i][j]=1;
p=pop(p,&i,&j,&k);
a[i][j]=k; //沒有通路，將其坐標置回成沒有經過的路，退回到上一步
}
if(a[i][j]<4){
a[i][j]++;
p=push(p,i,j,a[i][j]);
nextpos(&i,&j,a[i][j]);
} //存在通路，則向下一步方向前進
else if(a[i][j]>4){
a[i][j]=2;
p=push(p,i,j,a[i][j]);
nextpos(&i,&j,a[i][j]);
} //只經過一次的通路，下一步向南走
}
}
}while(!empty(p)) ;
return NULL;
}
主函數演算法
main()
{
int i1,i2,j1,j2;
int m,n,l;
int num=0;
mazestack * ma;
printf("input start point\n");
scanf("%d,%d",&i1,&j1); //輸入起點
printf("input end point\n");
scanf("%d,%d",&i2,&j2); //輸入終點
ma=maze(i1,j1,i2,j2); //求解迷宮
if(ma==NULL){
printf("There is no way");
} //空棧，說明沒有路經
else{
while(!empty(ma)){
ma=pop(ma,&m,&n,&l);
printf("(%d,%d) ",m,n);
num++;
} //輸出路徑結果和步長
printf("the step is %d",num);
}
}

這個應該自己能看懂吧~~根據你自己的需要,改動某些部分即可~~

『叄』 C語言中用棧實現迷宮問題

#include
#define MAXSIZE 100
using namespace std;
struct stack{
int iway;
int jway;
int dire;
};
stack maze[MAXSIZE];
int top;
int map[14][28]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1},
{1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};

void findway(int xS,int yS,int xE,int yE)
{
top=0;
maze[top].iway=xS;
maze[top].jway=yS;
map[xS][yS]=-1;
int i,j,di,find;
while(top>-1)
{
i=maze[top].iway;
j=maze[top].jway;
di=maze[top].dire;
if(i==xE&&j==yE)
{
cout<<"***********************************\n";
cout<<"path"<<":"<<endl;
cout<<"("<<maze[0].iway<<","<<maze[0].jway<<")";
for(int val=1;val<top+1;val++)
{
cout<("<<maze[val].iway<<","<<maze[val].jway<<")";
if((val+1)%5==0)
cout<<endl;
}
cout<<endl;
cout<<"***********************************\n";
return;
}
find=0;
while(find==0&&di<4)
{
di++;
switch(di)
{
case(0):i=maze[top].iway;
j=maze[top].jway+1;
break;
case(1):i=maze[top].iway;
j=maze[top].jway-1;
break;
case(2):i=maze[top].iway+1;
j=maze[top].jway;
break;
case(3):i=maze[top].iway-1;
j=maze[top].jway;
break;
}
if(map[i][j]==0)
{
find=1;
}
}
if(find==1)
{
maze[top].dire=di;
top++;
maze[top].iway=i;
maze[top].jway=j;
maze[top].dire=-1;
map[i][j]=-1;
}
else
{
map[maze[top].iway][maze[top].jway]=0;
top--;
}
}
}
int main()
{
for(int i=0;i<14;i++) //迷宮圖形化輸出
{
for(int j=0;j<28;j++)
{
if(map[i][j]==1)
cout<<"■";
else cout<<"□";
}
cout<<endl;
}
int xStart,yStart,xEnd,yEnd;
cout<<"請輸入迷宮起點坐標，用空格隔開(左上角坐標為(0,0)):";
cin>>xStart>>yStart;
cout<<"請輸入迷宮終點坐標，用空格隔開(右上角坐標為(13,27)):";
cin>>xEnd>>yEnd;
findway(xStart,yStart,xEnd,yEnd);
return 0;
}
滿意請採納！

『肆』 1、 迷宮尋路（遞歸程序設計和棧的應用） 【問題描述】 將一隻老鼠從一個矩形無頂大盒子（

這里有篇博文基於棧和隊列的迷宮問題求解基於棧和隊列提供迷宮問題的解決方案，也屬有提供源碼下載~也可以在這個網站上面搜索看看，剛才還搜到很多課設和畢設，都有源碼和文檔，一個干貨滿滿的博客，有用的話記得採納哦^_^

『伍』 迷宮問題（棧實現）

問題補充：這個迷宮是八個方向走的，不只是上下左右四個方向。而且迷宮數據肯定沒問題。 #include

『陸』 C++課程設計：迷宮問題演示程序

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define M 15
#define N 15
int z=0;
struct Point
{
int m_1;
int n_1;
Point_cout();
Point_cout1();
};
Point::Point_cout()
{
return(m_1);
}
Point::Point_cout1()
{
return(n_1);
}
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
}; struct Element
{
int x,y; //x行,y列
int d; //d下一步的方向
}; typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/ int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
} int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
} int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
} int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[2][4][2],int z,int &a,int &b)
{
int m=a;
int n=b;
int i,j,d;
int a_1,b_1;
Element elem;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
if(z<2)
{
for(int w_1=0;w_1<9;w_1++)
for(int w_2=0;w_2<8;w_2++)
if(maze[w_1][w_2]==2)
maze[w_1][w_2]=0;
maze[start.x][start.y]=2;
//入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
Push(S1,elem); //開始為-1
//cout<<elem.x<<" "<<elem.y<<" "<<elem.d<<" "; while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
//cout<<elem.x<<elem.y<<elem.d;
i=elem.x;
j=elem.y;
d=elem.d+1;while(d<4) //試探東南西北各個方向
{
a_1=i+diradd[z][d][0];
b_1=j+diradd[z][d][1];
if(a_1==end.x && b_1==end.y && maze[a_1][b_1]==0) //如果到了出口
{
cout<<"可以到達出口的路徑有："<<endl;
//maze[a][b]=2
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a_1;
elem.y=b_1;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
//cout<<"\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)";
cout<<endl;
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,elem);
//cout<<"("<<e.x<<","<<e.y<<","<<e.d<<")"<<"-->";
Push(S2,elem);
}
while(S2)
{
Pop(S2,elem);
printf("-->(%d,%d,%d)",elem.x,elem.y,elem.d);
}
cout<<endl;
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
++z;
MazePath(start,end,maze,diradd,z,a,b);
}
if(maze[a_1][b_1]==0) //找到可以前進的非出口的點
{
maze[a_1][b_1]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a_1; //下一點轉化為當前點
j=b_1;
d=-1;
}
d++;
}
}
//cout<<"("<<elem.x<<","<<elem.y<<","<<elem.d<<")"<<"-->"<<"||";
}
//cout<<"沒有找到可以走出此迷宮的路徑\n";
}
/*************建立迷宮*******************/
int initmaze(int maze[M][N],int &a,int &b)
{
int i,j;
int m,n; //迷宮行,列
cout<<"請輸入迷宮的行數 m=";
cin>>m;
cout<<"請輸入迷宮的列數 n=";
cin>>n;
a=m;
b=n;
cout<<"請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆:";
cout<<endl;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>maze[i][j];
cout<<"你建立的迷宮為:";
cout<<endl;
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=8;
maze[i][n+1]=8;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=8;
maze[m+1][j]=8;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
return 0;
} void main()
{
int a=0;
int b=0;
int sto[M][N]; struct mark start,end; //start,end入口和出口的坐標
int add[2][4][2]={{{0,1},{1,0},{0,-1},{-1,0}},{{1,0},{0,1},{0,-1},{-1,0}}};//行增量和列增量 方向依次為東西南北
cout<<"注:上面的式子一維為2，根據東西南北，共有16種排列，因數量太多，故省略只寫順序依次為東南西北和南東西北";
cout<<endl;
initmaze(sto,a,b);//建立迷宮
cout<<"輸入入口的橫坐標,縱坐標";
cin>>start.x>>start.y;
cout<<"輸入出口的橫坐標,縱坐標";
cin>>end.x>>end.y;
MazePath(start,end,sto,add,z,a,b); //find path
//system("PAUSE");
}
// 下面是以9行8列的輸入（你可以復制，黏貼就ok 了）0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1

『柒』 迷宮問題的課程設計報告

http://download.csdn.net/source/298953
這里有下載呼呼
還有個要交錢的也給你吧
http://cn.happycampus.com/docs/983345939101@hc04/56958/

『捌』 數據結構課程設計的迷宮問題~~~~急！！！

看下我的程序,,要不是你要的.

#include <iostream>
#include <iomanip>
using namespace std;
#define M 20
#define N 20
struct move{int dx,dy;};
move mazemove[8];
char ma[M][N];
int False=0;

void maze()
{int i,j,num;
for(i=1;i<M-1;i++)
{for(j=1;j<N-1;j++)
{num=(800*(i+j)+1500)%327;
if((num<156)&&(i!=M||j!=N))
ma[i][j]='1';
else
ma[i][j]='0';
}
}
ma[1][1]='0';
ma[M-2][N-2]='0';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
cout<<setw(3)<<ma[i][j];
cout<<endl;
}
}

void inimove()
{mazemove[0].dx=0;mazemove[0].dy=1;
mazemove[1].dx=1;mazemove[1].dy=1;
mazemove[2].dx=1;mazemove[2].dy=0;
mazemove[3].dx=1;mazemove[3].dy=-1;
mazemove[4].dx=0;mazemove[4].dy=-1;
mazemove[5].dx=-1;mazemove[5].dy=-1;
mazemove[6].dx=-1;mazemove[6].dy=0;
mazemove[7].dx=-1;mazemove[7].dy=1;
}

void outpath()
{int i,j,x,y,k;
i=1;j=1;k=0;
while((i!=(M-2))||(j!=(N-2)))
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='0'){k=0;break;}
}
if(k!=8)
{if(ma[i][j]=='8')ma[i][j]='2';
if(ma[i][j]=='0')ma[i][j]='>';
i=x;j=y;
}
else
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='8')break;
}
ma[i][j]='2';
i=x;j=y;
}
if((i==1)&&(j==1))
{False=0;
break;
}
else False=1;
}

}

int main()
{int i,j;
maze();
inimove();
outpath();
cout<<endl;
if(False==0)
cout<<"無法走出該迷宮!"<<endl;
else
{cout<<"走出迷宮的路徑(用『>』符號表示)為:"<<endl;
ma[M-2][N-2]='>';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
{ {if(ma[i][j]=='2')ma[i][j]='>';
if(ma[i][j]=='0')ma[i][j]=' ';
if(ma[i][j]=='1')ma[i][j]='*';
}
cout<<setw(3)<<ma[i][j];
}
cout<<endl;
}
}
return 0;
}

『玖』 迷宮問題（棧的應用）

太難了......

『拾』 請幫我做一道數據結構程序題，題目為用棧解決迷宮問題

註：下面分別是三個文件：棧的定義與聲明（頭文件）、棧的實現、迷宮問題。

/* 順序棧表示：類型和界面函數聲明 */

enum { MAXNUM = 20 /* 棧中最大元素個數，應根據需要定義 */
};

typedef int DataType; /* 棧中元素類型，應根據需要定義 */

struct SeqStack { /* 順序棧類型定義 */
int t; /* 棧頂位置指示 */
DataType s[MAXNUM];
};

typedef struct SeqStack SeqSack, *PSeqStack; /* 順序棧類型和指針類型 */

/*創建一個空棧;為棧結構申請空間，並將棧頂變數賦值為-1*/
PSeqStack createEmptyStack_seq( void );

/*判斷pastack所指的棧是否為空棧，當pastack所指的棧為空棧時，則返回1，否則返回0*/
int isEmptyStack_seq( PSeqStack pastack );

/* 在棧中壓入一元素x */
void push_seq( PSeqStack pastack, DataType x );

/* 刪除棧頂元素 */
void pop_seq( PSeqStack pastack );

/* 當pastack所指的棧不為空棧時，求棧頂元素的值 */
DataType top_seq( PSeqStack pastack );

/* 順序棧表示：函數定義 */

#include <stdio.h>
#include <stdlib.h>

#include "sstack.h"

/*創建一個空棧;為棧結構申請空間，並將棧頂變數賦值為-1*/
PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
printf("Out of space!! \n");
else
pastack->t = -1;
return pastack;
}

/*判斷pastack所指的棧是否為空棧，當pastack所指的棧為空棧時，則返回1，否則返回0*/
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}

/* 在棧中壓入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Stack Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}

/* 刪除棧頂元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}

/* 當pastack所指的棧不為空棧時，求棧頂元素的值 */
DataType top_seq( PSeqStack pastack ) {
return pastack->s[pastack->t];
}

/* 迷宮問題的非遞歸演算法(棧實現)*/

#define MAXNUM 100/* 棧中最大元素個數 */
#define N 11 /*地圖的第一維長度*/
#include <stdio.h>
#include <stdlib.h>

typedef struct {
int x;/* 行下標 */
int y;/* 列下標 */
int d;/* 運動方向 */
} DataType;

struct SeqStack { /* 順序棧類型定義 */
int t; /* 指示棧頂位置 */
DataType s[MAXNUM];
};

typedef struct SeqStack *PSeqStack; /* 順序棧類型的指針類型 */
PSeqStack pastack; /* pastack是指向順序棧的一個指針變數 */

PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space!! \n");
else
pastack->t = -1;
return pastack;
}

int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}

/* 在棧中壓入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}

/* 刪除棧頂元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}

/* 當pastack所指的棧不為空棧時，求棧頂元素的值 */
DataType top_seq( PSeqStack pastack ) {
return (pastack->s[pastack->t]);
}

void pushtostack(PSeqStack st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}

void printpath(PSeqStack st) {
DataType element;
printf("The revers path is:\n"); /* 列印路徑上的每一點 */
while(!isEmptyStack_seq(st)) {
element = top_seq(st);
pop_seq(st);
printf("the node is: %d %d \n", element.x, element.y);
}
}

/* 迷宮maze[M][N]中求從入口maze[x1][y1]到出口maze[x2][y2]的一條路徑 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2) {
int i, j, k, g, h;
PSeqStack st;
DataType element;
st = createEmptyStack_seq( );
maze[x1][y1] = 2; /* 從入口開始進入,作標記 */
pushtostack(st, x1, y1, -1); /* 入口點進棧 */

while ( !isEmptyStack_seq(st)) { /* 走不通時,一步步回退 */
element = top_seq(st);
pop_seq(st);
i = element.x; j = element.y;
for (k = element.d + 1; k <= 3; k++) { /* 依次試探每個方向 */
g = i + direction[k][0];h = j + direction[k][1];
if (g == x2 && h == y2 && maze[g][h] == 0) { /* 走到出口點 */
printpath(st); /* 列印路徑 */
return;
}
if (maze[g][h] == 0) { /* 走到沒走過的點 */
maze[g][h] = 2; /* 作標記 */
pushtostack(st, i, j, k); /* 進棧 */
i = g; j = h; k = -1; /* 下一點轉換成當前點 */
}
}
}
printf("The path has not been found.\n");/* 棧退完未找到路徑 */
}

int main(){
int direction[][2]={0,1,1,0,0,-1,-1,0};
int maze[][N] = {
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1
};
mazePath(maze,direction,1,1,6,9);
getchar();
return 0;
}