数据结构迷宫源程序

﹏ヽ暗。殇╰゛Y 2022-08-02 10:48 155阅读 0赞

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<malloc.h>  
\#define M 100  
\#define TRUE 1  
\#define FALSE 0  
\#define OVERFLOW 0  
\#define OK 1  
\#define ERROR 0  
int a\[10\]\[10\] = \{ \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\},  
                 \{1, 0, 0, 1, 0, 0, 0, 1, 0, 1\},  
                 \{1, 0, 0, 1, 0, 0, 0, 1, 0, 1\},  
                 \{1, 0, 0, 0, 0, 1, 1, 0, 0, 1\},            
                 \{1, 0, 1, 1, 1, 0, 0, 0, 0, 1\},  
                 \{1, 0, 0, 0, 1, 0, 0, 0, 0, 1\},  
                 \{1, 0, 1, 0, 0, 0, 1, 0, 0, 1\},  
                 \{1, 0, 1, 1, 1, 0, 1, 1, 0, 1\},  
                 \{1, 1, 1, 0, 0, 1, 0, 0, 0, 1\},  
                 \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\},\};  
typedef struct  
\{  
int r;  
int c;  
\}postype;  
typedef struct  
\{  
int ord;//通道口在路径上的序号  
postype seat;//通道口在迷宫中的位置  
int di;//从通道口走向下一通道口的方向  
\}selmtype;  
typedef struct  
\{  
   selmtype \*base;  
   selmtype \*top;  
   int stacksize;  
\}sqstack;  
  
  
int initstack(sqstack &s);  
int push(sqstack &s,selmtype &e);  
int pop(sqstack &s,selmtype &e);  
int stackempty(sqstack s);  
selmtype gettop(sqstack s);  
int pass(postype curpos);  
void footprint(postype curpos);  
postype nextpos(postype curpos,int i);  
void markprint(postype m);  
  
  
int main()  
\{  
  
  
    int i, j;  
int curstep=1,b=0;  
        postype start=\{1,1\},end=\{8,8\},curpos;  
sqstack s;  
selmtype e;  
initstack(s);  
curpos=start;  
    printf("还没有走的迷宫\\n");  
    for(i=0;i<10;i++)  
\{  
       for(j=0;j<10;j++)  
       printf("%d\\t", a\[i\]\[j\]);  
       printf("\\n\\n");  
\}  
      
   
   do\{  
     if(b=pass(curpos))  
    \{  
       footprint(curpos);  
       e.ord=curstep;  
       e.seat=curpos;  
       e.di=1;   
       push(s,e);  
       if(curpos.r==end.r && curpos.c==end.c)  
       \{  
          printf("迷宫成功走完了！！！");  
          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("\\n已经走完的迷宫\\n");  
  for(i = 0; i < 10; i++)  
  \{      
     for(j = 0; j < 10; j++)           
     printf("%d\\t",a\[i\]\[j\]);          
     printf("\\n\\n");    
  \}  
  return 0;  
\}  
int initstack(sqstack &s)  
\{  
s.base=(selmtype\*)malloc(M\*sizeof(selmtype));  
if(!s.base) return ERROR;  
s.top=s.base;  
s.stacksize=M;  
return OK;  
\}  
  
  
  
  
int push(sqstack &s,selmtype &e)  
\{  
  
\*s.top++=e;  
return OK;  
\}  
  
  
int pop(sqstack &s,selmtype &e)  
\{  
if(s.top==s.base) return ERROR;  
e=\*--s.top;  
return OK;  
\}  
  
  
  
  
int stackempty(sqstack s)  
\{  
if(s.top==s.base) return TRUE;  
else return FALSE;  
\}  
  
  
  
  
selmtype gettop(sqstack s)  
\{  
    selmtype e;  
    if(s.top != s.base)  
    e = \*(s.top - 1);  
    return e;  
\}  
  
  
  
  
  
  
  
  
int pass(postype curpos)  
\{  
int i=curpos.r;  
int j=curpos.c;  
if(a\[i\]\[j\]==0) return 1;  
else return 0;  
\}  
  
  
  
  
void footprint(postype curpos)  
\{  
int i=curpos.r;  
int j=curpos.c;  
a\[i\]\[j\]='9';  
\}  
  
  
  
  
postype nextpos(postype curpos,int i)  
\{  
  
switch(i)  
\{  
case 1:curpos.c+=1;break;  
case 2:curpos.r+=1;break;  
case 3:curpos.c-=1;break;  
case 4:curpos.r-=1;break;  
default:exit(ERROR);  
\}  
return curpos;  
\}  
  
  
  
  
void markprint(postype m)  
\{  
int i,j;  
i=m.r;  
j=m.c;  
a\[i\]\[j\]='4';  
\}