#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define SIZE 100
#define INCR 20
struct migong{
int flag;
int dir;
};
struct migong a[10][10];
struct sqstack{
int *base;
int *top;
int stacksize;
};
void initstack( sqstack &s){
s.base=(int *)malloc(SIZE*sizeof(int));
if(!s.base){printf("\nshort of \n");exit(0);}
s.top=s.base;
s.stacksize=SIZE;
}
int pop( sqstack &s,int *e){
if(s.top==s.base)return 0;
*e=*(--s.top);
return 1;
}
void push( sqstack &s,int e){
if(s.top-s.base>=s.stacksize){
s.base=(int *)realloc(s.base,
(s.stacksize+INCR)*sizeof(int));
if(!s.base)exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=INCR;
}
*(s.top)=e;
(s.top)++;
}
int gettop(sqstack &s,int *e){
if(s.top==s.base)return 0;
*e= *(s.top-1);
return 1;
}
int masepath(int i,int j,int m,int n,sqstack &s){
if(a[i][j].flag==1){printf("\nentrance is error\n");return 0;}
do {
if (i==m&&j==n){push(s,i);push(s,j);return 1;}
else {
if(a[i][j].dir==1){
if(a[i][j+1].flag==1) a[i][j].dir++;
else {
push(s,i);push(s,j);a[i][j].flag=1;j++;continue;
}
}
if(a[i][j].dir==2){
if(a[i+1][j].flag==1) a[i][j].dir++;
else {
push(s,i);push(s,j);a[i][j].flag=1;i++;continue;
}
}
if(a[i][j].dir==3){
if(a[i][j-1].flag==1) a[i][j].dir++;
else {
push(s,i);push(s,j);a[i][j].flag=1;j--;continue;
}
}
if(a[i][j].dir==4){
if(a[i-1][j].flag==1) a[i][j].dir++;
else {
push(s,i);push(s,j);a[i][j].flag=1;i--;continue;
}
}
else{
a[i][j].flag=1;
pop(s,&j);pop(s,&i);
a[i][j].flag=0;
}
}
}
while(s.top!=s.base);
printf("\n no exit\n");
return 2;
}
void main(){
int m,n,x,y,i,j,r=1;
sqstack s1,s2;
initstack(s2);
initstack(s1);
int b[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,1,1,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},
};
printf("it is:\n");
printf(" 0 1 2 3 4 5 6 7 8 9\n\n");
for(i=0;i<10;i++){
printf(" %d ",i);
for(j=0;j<10;j++){
a[i][j].flag=b[i][j];
printf("%d ",b[i][j]);
a[i][j].dir=1;
}
printf("\n");
}
printf("entrance is:\n");
scanf("%d",&m);
scanf("%d",&n);
masepath(1,1,m,n,s1);
while(s1.top!=s1.base){
pop(s1,&x);
push(s2,x);
}
printf("\nexit is :\n");
while(s2.top!=s2.base){
pop(s2,&x);pop(s2,&y);
printf("< %d,%d> ",x,y);
if(r++%5==0)
printf("\n");
}
}