1 #include <stdlib.h>
#include <stdio.h> #define stackinitsize 50
#define stackincrement 8 typedef struct {
int x,y;
}posttype; typedef struct {
int ord;
posttype seat;
int di;
}elemtype; typedef struct{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack; int initstack(sqstack &s)
{s.base=(elemtype * ) malloc(stackinitsize*sizeof(elemtype));
s.top=s.base;
s.stacksize=stackinitsize;
return ;
} int push(sqstack &s,elemtype e)
{
(*(s.top)).ord=e.ord;
(*(s.top)).seat.x=e.seat.x;
(*(s.top)).seat.y=e.seat.y;
(*(s.top)).di=e.di;
s.top++;
return ;
} //elemtype gettop(sqstack s)
//{
// return *(s.top-1);
// } int emptystack(sqstack s)
{if (s.top==s.base) return ;
else return ;
} int pop(sqstack &s,elemtype &e)
{ if (emptystack(s)) return ;
--s.top;
e.ord=(*(s.top)).ord;
e.seat.x=(*(s.top)).seat.x;
e.seat.y=(*(s.top)).seat.y;
e.di=(*(s.top)).di;
return ;
}
#include <stdio.h>
# include "d:\maze\mystack.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\n",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("\nno path....");
}