迷宫 maze

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 
 4 #define stackinitsize 50
 5 #define stackincrement 8
 6 
 7 typedef struct {
 8     int x,y;
 9 }posttype;
10 
11 typedef struct {
12     int ord;
13     posttype seat;
14     int di;
15 }elemtype;
16 
17 typedef struct{
18   elemtype *base;
19   elemtype *top;
20   int stacksize;
21 }sqstack;
22 
23 
24 int  initstack(sqstack &s)
25   {s.base=(elemtype * ) malloc(stackinitsize*sizeof(elemtype));
26    s.top=s.base;
27    s.stacksize=stackinitsize;
28    return 1;
29    }
30 
31 int push(sqstack &s,elemtype e)
32  {
33    (*(s.top)).ord=e.ord;
34    (*(s.top)).seat.x=e.seat.x;
35    (*(s.top)).seat.y=e.seat.y;
36    (*(s.top)).di=e.di;
37    s.top++;
38    return 1;
39  }
40 
41 //elemtype gettop(sqstack s)
42 //{
43 //  return *(s.top-1);
44 // }
45 
46 int emptystack(sqstack s)
47   {if (s.top==s.base)  return 1;
48    else return 0;
49    }
50 
51 int pop(sqstack &s,elemtype &e)
52    { if (emptystack(s)) return 0;
53      --s.top;
54    e.ord=(*(s.top)).ord;
55    e.seat.x=(*(s.top)).seat.x;
56    e.seat.y=(*(s.top)).seat.y;
57    e.di=(*(s.top)).di;
58     return 1;
59      }



#include <stdio.h>
# include "d:mazemystack.h"

#define TRUE 1
#define FALSE 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,0,0,0,0,0,0,0,1,
	       1,1,1,1,1,1,1,1,1,1};



             			  
typedef int Status;

Status pass(posttype curpos)
{
	if (a[curpos.x][curpos.y]==0)
		return 1;
	else 
		return 0;
}


Status mazepath(int maze[10][10],posttype start,posttype end,sqstack &s)
{
	int curstep;
	posttype curpos;
	elemtype e;
	initstack(s);
	curpos.x=start.x;curpos.y=start.y;
	curstep=1;
	do{
		if(pass(curpos))
		{
	//		footprint(curpos);//stroe foot
	
			e.ord=curstep;
			e.seat.x=curpos.x;
			e.seat.y=curpos.y;
			e.di=1;
			push(s,e);
			if(curpos.x==end.x && curpos.y==end.y) return(TRUE);
			curpos.y=curpos.y+1;//east near
			curstep++;
		}
		else
		{
			if(!emptystack(s))
			{
				pop(s,e);
				while(e.di==4 && !emptystack(s))
				{
//					 markprint(s.seat);//outprint reverse
					 pop(s,e);
				}//end while
				if(e.di<4)
				{
					e.di++;push(s,e);
					switch(e.di)
					{
						case 1:curpos.y=curpos.y+1;break;
						case 2:curpos.x=curpos.x+1;break;
						case 3:curpos.y=curpos.y-1;break;
						case 4:curpos.x=curpos.x-1;break;
					}
				}//if(di<4)
			}//if(!emptystack(s))
		}//else
	}while(!emptystack(s));
	return FALSE;
}

void outputstak(sqstack s)
{
   elemtype e;
	while(!emptystack(s))
   {
	   pop(s,e);
	   printf("%d (%d,%d) %d
",e.ord,e.seat.x,e.seat.y,e.di);
	   }
}


main()
{
	posttype start,end;
    start.x=1;start.y=1;
	end.x=8;end.y=8;
    sqstack s1;
    if(mazepath(a,start,end,s1)==TRUE)
	   outputstak(s1);	
     else
	   printf("
no path....");
}