数据结构——迷宫求解

朱雀 2022-08-03 00:25 187阅读 0赞

效果如下：

![Image 1][]

源代码如下：  
\#include<stdio.h>  
\#include<string.h>  
\#include<stdlib.h>  
\#define M 100  
\#define ERROR 0  
\#define OK 1  
char a\[10\]\[10\]=\{ \{'\*','\*','\*','\*','\*','\*','\*','\*','\*','\*'\},  
\{'\*','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','\*','0','0','0','0','\*'\},  
\{'\*','0','\*','0','0','0','\*','0','0','\*'\},  
\{'\*','0','\*','\*','\*','0','\*','\*','0','\*'\},  
\{'\*','\*','0','0','0','0','0','0','0','\*'\},  
\{'\*','\*','\*','\*','\*','\*','\*','\*','\*','\*'\},\};  
typedef struct  
\{  
int row;  
int col;  
\}postype;  
typedef struct  
\{  
int ord;  
postype seat;  
int di;  
\}Chartype;  
typedef struct  
\{  
Chartype \*base;  
Chartype \*top;  
int stacksize;  
\}sqstack;  
int Initstack(sqstack &s)  
\{  
s.base = (Chartype\*)malloc(M \* sizeof(Chartype));  
if(!s.base)return ERROR;  
s.top = s.base;  
s.stacksize = M;  
return OK;  
\}  
int Pass(postype curpos)  
\{  
if(a\[curpos.row\]\[curpos.col\]=='0')  
return 1;  
 else  
return 0;  
\}  
void Footprint(postype curpos)  
\{  
  
  
a\[curpos.row\]\[curpos.col\]='->';  
\}  
int push(sqstack &s, Chartype &e)  
\{  
\*s.top++ = e;  
return OK;  
\}  
int pop(sqstack &s, Chartype &e)  
\{  
if(s.top == s.base)  
return ERROR;  
e = \* --s.top;  
return OK;  
\}  
postype nextpos(postype curpos,int x)  
\{  
if(x==1)  
curpos.col=curpos.col+1;  
else if(x==2)  
curpos.row= curpos.row+1;  
else if(x==3)  
curpos.col= curpos.col-1;  
else  
curpos.row= curpos.row-1;  
return curpos;  
\}  
void markprint(postype e)  
\{  
a\[e.row\]\[e.col\]='&';  
\}  
int stackempty(sqstack s)  
\{  
if(s.base == s.top)  
return 1;  
else  
return 0;  
\}  
int main()  
\{  
int i, j, curstep = 1,x=0;  
postype start = \{1,1\}, end = \{8, 8\}, curpos;  
sqstack s;  
Chartype e;  
Initstack(s);  
curpos=start;  
printf("...........迷宫求解..............\\n");  
printf("还没有走的迷宫\\n");  
 for(i = 0; i < 10; i++)  
\{  
for(j = 0; j < 10; j++)  
\{  
printf("%c ", a\[i\]\[j\]);  
\}printf("\\n");  
\}  
 do  
 \{  
 if(x=Pass(curpos))  
 \{  
 Footprint(curpos);  
 e.ord=curstep;  
 e.seat=curpos;  
 e.di=1;  
 push(s,e);  
 if(curpos.row==end.row&&curpos.col==end.col)  
 \{  
 printf("迷宫已经走完了！\\n");  
 break;  
 \}  
curpos=nextpos(curpos,1);  
 curstep++;  
 \}  
 else  
 \{  
 if(!stackempty(s))  
 \{  
 pop(s,e);  
 while(e.di == 4 && !stackempty(s))  
 \{  
 markprint(e.seat);  
 pop(s,e);  
 \}  
 if(e.di<4)  
 \{  
 e.di++;  
 push(s,e);  
 curpos=nextpos(e.seat,e.di);  
 \}  
 \}  
 \}  
 \}while(!stackempty(s));  
 printf("一共走了%d步\\n",curstep);  
 printf("已经走完的迷宫：\\n");  
 for(i=0;i<10;i++)  
 \{  
 for(j=0;j<10;j++)  
 \{  
 printf("%c ",a\[i\]\[j\]);  
 \}  
 printf("\\n");  
 \}  
 return 0;  
\}

[Image 1]: