迷宫问题C语言解法

本是古典何须时尚 2022-08-11 00:40 198阅读 0赞

这是我们数据结构课上布置的作业，自己花了些时间完成的，下面是代码。这是C语言的解法，利用面向过程方法可能比较的复杂。

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<fstream>  
using namespace std;  
ofstream fout("maze.txt");  
  
  
\#define M 5 //行数  
\#define N 6  //列数  
  
  
  
  
typedef struct   
\{  
int x;  
int y;  
  
  
\}item;//定义坐标和方向  
  
  
  
  
typedef struct  
\{  
int x;  
int y;  
int d;  
  
  
\}dataType;//定义顺序栈的类型定义  
  
  
typedef struct  
\{  
dataType data\[100\];//定义栈的容量  
int top;  
\}SeqStack;  
  
  
SeqStack\* InitSeqStack()//初始化空栈  
//返回单元首地址  
\{  
SeqStack \*s;  
s=new SeqStack;//分配栈空间  
s->top=0;//把这个栈变为空栈  
return s;//返回首地址  
\}  
  
  
int Push(SeqStack \*s,dataType x)  
//入栈  
  
  
\{  
if(s->top==100-1)  //这时候栈已经满了  
return 0;  
  
  
else\{  
s->data\[s->top\]=x;  
s->top++;  
return 1;  
\}  
\}  
  
  
int StackEmpty(SeqStack \*s)  //判断栈是否为空,若为空则返回一，否则返回0  
\{  
if(s->top==0)  
return 1;  
else  
return 0;  
  
  
\}  
  
  
  
  
int Pop(SeqStack \*s,dataType \*x)  
         //栈顶元素出栈,如果栈为空那么就会返回0，否则，执行出栈这个操作  
\{  
if(StackEmpty(s))//执行出栈操作，若为空，则结束  
return 0;  
else  
\{  
s->top--;//栈顶元素减一  
\*x=s->data\[s->top\];//将出栈的元素值赋给x  
return 1;  
  
  
\}  
  
  
\}  
  
  
  
  
  
  
void print\_Path(SeqStack \*s)//这个函数用来输出迷宫的路线  
\{  
printf("maze的路径是:\\n");  
fout<<"maze的路径是:\\n";  
for(int i=0;i<s->top;i++)  
\{  
printf("(%d,%d)->",s->data\[i\].x,s->data\[i\].y);  
fout<<"(";  
fout<<s->data\[i\].x;  
fout<<",";  
fout<<s->data\[i\].y;  
fout<<")->";  
  
\}  
  
\}  
  
  
void find\_Path(int maze\[M+2\]\[N+2\],item move\[4\])  
//在迷宫数组中按照方向探测迷宫的路线，如果存在就返回1，否则返回0  
\{  
SeqStack \*s=InitSeqStack();//初始化栈  
dataType temp;  
int x,y,d,i,j;  
  
temp.x=1;  
temp.y=1;  
temp.d=0;  
Push(s,temp);//入栈  
  
  
while(!StackEmpty(s))//当顺序栈S不为空时  
\{  
Pop(s,&temp);//元素出栈  
x=temp.x;  
y=temp.y;  
d=temp.d;  
  
  
while(d<4)  
\{  
i=x+move\[d\].x;  
j=y+move\[d\].y;//这两条语句是上下左右探测的关键，i,j代表探测之后新的位置  
  
  
if(maze\[i\]\[j\]==0)//代表这个方向可以走  
\{  
temp.x=x;  
temp.y=y;  
temp.d=d;  
Push(s,temp);//坐标和方向入栈  
x=i;  
y=j;//这两条语句代表新的位置  
                maze\[x\]\[y\]=-1;//这个位置已经到达  
   if(x==M&&y==N)//已经到达出口  
\{  
temp.x=x;  
temp.y=y;  
Push(s,temp);  
print\_Path(s);//输出路径  
  
  
\}  
else  
d=0;//到了新的位置，重新初始化探测方向  
\}  
else  
d++;//探测下一个方向  
\}  
\}  
  
  
  
  
  
  
\}  
  
  
void main()\{  
  
  
    item move\[4\];//领域试探方向数组  
move\[0\].x=0;move\[0\].y=-1;//上  
    move\[1\].x=0;move\[1\].y=1;//下  
move\[2\].x=-1;move\[2\].y=0;//左  
move\[3\].x=1;move\[3\].y=0;//右  
    int maze\[M+2\]\[N+2\]=\{  
//定义迷宫数组  
\{1,1,1,1,1,1,1,1\},  
\{1,0,0,1,1,1,1,1\},  
\{1,1,0,0,0,1,1,1\},  
\{1,1,1,1,0,0,1,1\},  
\{1,1,1,1,0,0,1,1\},  
\{1,1,1,1,1,0,0,1\},  
\{1,1,1,1,1,1,1,1\}  
  
    \};  
for(int i=0;i<M+2;i++)  
\{  
for(int j=0;j<N+2;j++)  
\{  
printf("%d ",maze\[i\]\[j\]);  
\}  
printf("\\n");  
\}  
fout<<"1,1,1,1,1,1,1,1\\n";  
fout<<"1,0,0,1,1,1,1,1\\n";  
fout<<"1,1,0,0,0,1,1,1\\n";  
fout<<"1,1,1,1,0,0,1,1\\n";  
    fout<<"1,1,1,1,0,0,1,1\\n";  
fout<<"1,1,1,1,1,0,0,1\\n";  
fout<<"1,1,1,1,1,1,1,1\\n";  
  
  
find\_Path(maze,move);  
  
  
  
  
\}