用栈编程迷宫
1. 用栈的方法设计迷宫求解（c语言）。。限时
原来做过，以下为源代码和部分注释，可以运行
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
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[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
2. C++用栈实现迷宫的搜索
java">
packagecom.stack;
importjava.util.Stack;
classStep{
intx,y,d;
publicStep(intx,inty,intd){
this.x=x;//横坐标
this.y=y;//纵坐标
this.d=d;//方向
}
}
publicclassMazeTest{
publicstaticvoidmain(String[]args){
//迷宫定义
int[][]maze={{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,1,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,1,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}};
int[][]move={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
Stack<Step>s=newStack<Step>();
inta=path(maze,move,s);
while(!s.isEmpty()){
Stepstep=s.pop();
System.out.println(step.x+":"+step.y);
}
}
publicstaticintpath(int[][]maze,int[][]move,Stack<Step>s){
Steptemp=newStep(1,1,-1);//起点
s.push(temp);
while(!s.isEmpty()){
//temp=s.pop();这样写是有问题的，不能将出栈的元素作为当前位置，应该将栈顶元素作为当前位置
s.pop();//如果路走不通就出栈
if(!s.isEmpty()){
temp=s.peek();//将栈顶元素设置为当前位置
}
intx=temp.x;
inty=temp.y;
intd=temp.d+1;
while(d<8){
inti=x+move[d][0];
intj=y+move[d][1];
if(maze[i][j]==0){//该点可达
temp=newStep(i,j,d);//到达新点
s.push(temp);
x=i;
y=j;
maze[x][y]=-1;//到达新点，标志已经到达
if(x==6&&y==1){
return1;//到达出口，迷宫有路，返回1
}else{
d=0;//重新初始化方向
}
}else{
d++;//改变方向
}
}
}
return0;
}
}
3. 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;
}
满意请采纳！
4. 数据结构 迷宫问题 用栈解决
核心算法是搜索，这里如果要求用栈实现那就是深度优先搜索。 如果他不指定是用栈， 那么用队列来做就是广度优先搜索。
正常的深度优先搜索是可以用递归来实现的， 即然要求你非递归 你可以用栈来模拟递归的效果，毕竟函数的递归调用本质也是用栈来实现的
5. 请帮我做一道数据结构程序题，题目为用栈解决迷宫问题
注：下面分别是三个文件：栈的定义与声明（头文件）、栈的实现、迷宫问题。
/* 顺序栈表示：类型和界面函数声明 */
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;
}
6. 【迷宫问题】用堆栈解迷宫
#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;
}
你给的那库实在是没什么用的欲望，要最短路径一般用广度搜索，上面的代码应该属于深度搜索
7. c语言用栈解决迷宫问题
明摆着图的深度遍历 用堆栈模拟递归
8. C语言迷宫问题，用栈来做
#include <stdio.h> #include <mem.h> void main() { int a[100][100]; //0:blocked 1:passage 2:finish -1:visited; int b[10000][2]; int m=0,n=0; int sttop=0; int i,j,k,l; memset(a,0,sizeof(a)); printf("Please Input m,n:"); scanf("%d%d",&m,&n); printf("Input the start:"); scanf("%d%d",&i,&j); b[0][0]=i-1; b[0][1]=j-1; printf("Input the Map:\n"); for (i=0;i<m;i++) for (j=0;j<n;j++) { scanf("%d",&a[i][j]); } printf("Input the Finish:"); scanf("%d%d",&i,&j); a[i-1][j-1]=2; i=b[sttop][0];j=b[sttop][1]; a[i][j]=-1; while (sttop!=-1) { if (i>0) { //can up? if (a[i-1][j]==1) { a[--i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i-1][j]==2) { b[++sttop][0]=--i; b[sttop][1]=j; break; } } if (i<m-1) { //can up? if (a[i+1][j]==1) { a[++i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i+1][j]==2) { b[++sttop][0]=++i; b[sttop][1]=j; break; } } if (j>0) { //can left? if (a[i][j-1]==1) { a[i][--j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j-1]==2) { b[++sttop][0]=i; b[sttop][1]=--j; break; } } if (j<m-1) { //can up? if (a[i][j+1]==1) { a[i][++j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j+1]==2) { b[++sttop][0]=i; b[sttop][1]=j++; break; } } sttop--; } if (sttop+1) { for (i=0;i<sttop;i++) printf("(%d,%d)->",b[i][0]+1,b[i][1]+1); printf("(%d,%d)\n",b[i][0]+1,b[i][1]+1); } else printf("Can't Reach The Finish Spot!\n"); return; } 用非嵌套的方法做的栈，起点 终点自己定 输入数据规则如下： 先输入m n（m为行数，n为列数） 再输入起点(最左上角为(1,1)（前者行号，后者列号）则输入"1 1"（不含引号）其他依次类推) 再输入地图(0为被阻挡，1为通路)（起点被默认为通路，无论输入0还是1） 再输入终点（规则和起点一样） 回车后出结果，结果的表达方式以(x,y)->(x,y)->....->(x,y)（坐标任以1，1为左上角） 或者Can't Reach The Finish Spot! 呈现 其他的修改的话可以随便咯（规模m,n<=100，太大栈放不下了）
9. 迷宫问题，用栈，用C语言
这个是我写的一个迷宫最短路径的一个例子：广搜
#include<stdio.h>
#include<queue>
using namespace std;
struct node
{
int x,y;
};
int map[5][5],vis[5][5];
node root[30];
int rn,f;
int dir[4][2]={-1,0,0,1,1,0,0,-1};
void bfs(int i,int j)
{
node cur,next;
queue<node>q;
cur.x=i;
int k;
cur.y=j;
memset(vis,-1,sizeof(vis));
vis[i][j]=0;
q.push(cur);
while(!q.empty())
{
cur=q.front();
q.pop();
for(k=0;k<4;k++)
{
next.x=cur.x+dir[k][0];
next.y=cur.y+dir[k][1];
if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5)
{
if(map[next.x][next.y]==1) continue;
if(vis[next.x][next.y]==-1)
{
vis[next.x][next.y]=vis[cur.x][cur.y]+1;
q.push(next);
}
}
}
}
}
void dfs(int i,int j)
{
root[rn].x=i;
root[rn].y=j;
rn++;
if(i==0&&j==0)
{
f=1;
return;
}
int k,ii,jj;
for(k=0;k<4;k++)
{
ii=i+dir[k][0];
jj=j+dir[k][1];
if(ii>=0&&ii<5&&jj>=0&&jj<5)
{
if(vis[ii][jj]==(vis[i][j]-1))
dfs(ii,jj);
}
if(f)
return;
}
}
int main()
{
int i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&map[i][j]);
bfs(0,0);
rn=0;
f=0;
dfs(4,4);
for(i=rn-1;i>=0;i--)
{
printf("(%d, %d)\n",root[i].x,root[i].y);
}
return 0;
}
10. 栈的运用-迷宫问题
我说一下思路，代码自己实现吧。
你的要求是用栈：
首先得到迷宫的表示（一般是一个二维数组),在起点处，按顺时针方向，即如果东能走，走东（东进栈），如果东不能走，则走南（南进栈）。依此不停地走，如果四个方向都走不了，退栈。...到这里讲的是栈在这个算法中的用处。
至于要栈中要保存的信息：位置，走的方向。
算法中还需要一个数组来保存路径。
讲的很泛,但意思都在，希望你认真理解。