Question

数据结构C语言版的迷宫问题如何解决？

Answer 1

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define M 10
#define N 10
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=4; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("0=东 1=南 2=西 3=北 4为则走出迷宫\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);
}
printf("成功 !\n");
return;
}
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("请输入迷宫的各行各列:(用空格隔开,0代表路,1代表墙)\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为\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); //寻找路径
}

Answer 2

//迷宫实现 。。。

#include<iostream>
using namespace std;
class Stack
{
public:
void clear();
bool push(const int item);
bool pop(int & item);
bool Top(int & item);
bool isEmpty();
bool isFull();
};

class arrStack: public Stack
{
private:
int mSize;
int top;
int *st;
public:
arrStack(int size)
{
mSize=size;
top=-1;
st=new int[mSize];

}
arrStack()
{
top=-1;
}

~arrStack()
{
delete []st;
}

void clear()
{
top=-1;
}

bool isEmpty()
{
if(top==-1)
return true;
else
return false;
}

bool push(const int item)
{
if(top==mSize-1)
{
cout<<"栈满溢出。。。"<<endl;
return false;

}
else
{
st[++top]=item;
return true;
}
}

bool pop(int &item)
{
if(top==-1)
{
cout<<"栈空。。。"<<endl;
return false;
}

else
{
item=st[top--];
return true;
}

}

bool Top(int &item)
{
if(top==-1)
{
cout<<"栈空，不能读取栈顶元素。。。"<<endl;
return false;
}
else
{
item=st[top];
return true;
}
}
};

void main()
{

arrStack ly(100);
int i=1,j=1,cur,m,n;
int a[9][9];
while(i==0||j==0)
{
a[i][j]=0; // =0为墙
}
a[1][3]=a[1][7]=a[2][3]=a[2][7]=a[3][4]=a[3][5]=a[3][6]=a[4][2]=a[4][3]=a[4][4]=a[5][4]=0;
a[6][2]=a[6][6]=a[7][2]=a[7][3]=a[7][4]=a[7][6]=a[7][7]=a[8][1]=0;

a[1][1]=1;
do
{
if(a[i][j]!=0&&a[i][j]!=2&&a[i][j]!=3)
{
ly.push(i);
ly.push(j);
a[i][j]=3; //走过为3

if(i==8&&j==8)
{
cout<<"成功。。。"<<endl;
break;
}
else
{
i=i;
j++;
}
}
else
{
if(!ly.isEmpty()&&(a[i+1][j-1]!=0)&&(a[i+1][j-1]!=2))
{
i++;
j--;
}
else
{
i=i;
j--;
a[i][j+1]=2;
}

if(((!ly.isEmpty()&&(a[i+1][j]!=0)&&(a[i+1][j]!=2)&&(a[i+1][j]!=3))||(!ly.isEmpty()&&(a[i][j+1]!=0)&&(a[i][j+1]!=2)&&a[i][j+1]!=2)||((!ly.isEmpty()&&a[i-1][j]!=0)&&(a[i-1][j])!=2&&(a[i-1][j])!=3))||((!ly.isEmpty()&&a[i][j-1]!=0)&&(a[i][j-1]!=2)&&(a[i][j-1])!=3))
{}
//if(!ly.isEmpty()&&(((a[i+1][j]==0)||(a[i+1][j]==2)||(a[i+1][j]==3))&&((a[i][j+1]==0)||(a[i][j+1]==2)||(a[i][j+1]==3))&&((a[i-1][j]==0)||(a[i-1][j])==2)||(a[i-1][j]==3)))
else
{
ly.pop(m);
ly.pop(n);
i=m;
j=n;
a[i][j]=2; //已走不通为2

ly.Top(m);
ly.Top(n);
i=n;
j=m;
}

}

}while(1);

cout<<"输出迷宫路线。。。:"<<endl;
do
{
ly.pop(m);
ly.pop(n);
cout<<"("<<n<<","<<m<<")"<<" ";
}while(!ly.isEmpty());
cout<<endl;

}
整不好你跟我都一个学校。。。

Answer 3

具体想问什么