|
#include<iostream.h>
#include<stdlib.h>
/*class pose
{
public:
int x;
int y;
int h;
pose(int x,int y,int z)
{
this->x=x;
this->y=y;
this->h=h;
}
};
class type
{
public:
int ord;
pose seat;
int di;
type(int ord,pose curpos,int di)
{
this->ord=ord;
seat=curpos;
this->di=di;
}
};*/
typedef struct
{
int x;
int y;
int h;
}pose;
typedef struct
{ int ord;
pose seat;
int di;
}type;
class sqstack
{
public:
type *base;
type *top;
int stacksize;
};
int curstep;
class stack:public sqstack,public type
{
private:
type e;
public:
void initstack(sqstack &s,int n)
{
s.base=new type[n];
if(!s.base)
{
cout<<"overflow!";exit(2);
}
s.top=s.base;
s.stacksize=n;
}
void push(sqstack &s,type e)
{
if(s.top-s.base>=s.stacksize){cout<<"it is full!";exit(1);}
*s.top=e;
s.top++;
}
type pop(sqstack &s)
{
if(s.top == s.base)cout<<"it is empty!";
s.top--;
e=*s.top;
return e;
}
bool test(pose curpos[],int curstep)
{
if(curstep==1)return false;
else
{
for(int i=curstep-1;i>0;i--)
{
if((curpos[i].x==curpos[curstep].x)&&(curpos[i].y==curpos[curstep].y))
{
return true;break;
}
}
if(i==0)return false;
}
}
bool pass(pose curpos[],int n[][10],int curstep)// pose &curpos,
{
if (curpos[curstep].h==1||n[curpos[curstep].y][curpos[curstep].x]==-2)return false;
else if(test(curpos,curstep))
return false;
//(curpos[7].x==curpos[curstep].x)&&(curpos[7].y==curpos[curstep].y)(curpos[7].x==curpos[curstep].x)&&(curpos[7].y==curpos[curstep].y)
else return true;
}
void footprint(pose &curpos)
{
curpos.h=1;
}
void marksprint(pose &curpos)
{
curpos.h=1;
}
void nextpos(pose &curpos1,pose &curpos2,int di)
{
switch (di)
{
case 1:
curpos2.x=curpos1.x+1;curpos2.y=curpos1.y;
break;
case 2:
curpos2.y=curpos1.y+1;curpos2.x=curpos1.x;
break;
case 3:
curpos2.x=curpos1.x-1;curpos2.y=curpos1.y;
break;
case 4:
curpos2.y=curpos1.y-1;curpos2.x=curpos1.x;
break;
default:
cout<<"there is some error!"<<endl;
break;
}
}
bool mazepath(int n[10][10],stack m1,sqstack s)//stack m1,
{
// pose curpos;//end;start,
// pose start={1,1,1};pose end(8,8,1);//结构变量的赋值！！！！
pose start={1,1,0};pose end={8,8,1};//结构变量的赋值！！！！
pose *curpos=new pose[100];
for(int i=1;i<100;i++)
{
curpos[i].x=0;
curpos[i].y=0;
curpos[i].h=0;//={0,0,0};
}
curstep=1;
curpos[curstep]=start;
do{
if(m1.pass(curpos,n,curstep))//curpos[curstep],
{
footprint(curpos[curstep]);
type e;
e.di=1;
e.seat=curpos[curstep];
e.ord=curstep;//={curstep,curpos,1};
m1.push(s,e);
if((curpos[curstep].x==end.x)&&(curpos[curstep].y==end.y)) return(true);
curstep++;
m1.nextpos(curpos[curstep-1],curpos[curstep],1);
}
else{
if(!(s.base==s.top))
{
e=pop(s);
while(e.di==4&&!(s.base==s.top))
{
m1.marksprint(e.seat);
e=pop(s);
}
if(e.di<4)
{
e.di++;
m1.push(s,e);
curstep++;
// curpos[curstep].h=1;
m1.nextpos(e.seat,curpos[curstep],e.di);
}
}
}
}while(!(s.base==s.top));
return(false);
};
};
void main()
{
int h;//type n;
sqstack s;
stack m;
cin>>h;
m.initstack(s,h);
// m.initstack(s,h);
cout<<"begin!"<<endl;
/* for(int i=1;i<=10;i++)
{
cin>>h;
m.push(s,h);
} */
int n[10][10]=
{{-2,-2,-2,-2,-2,-2,-2,-2,-2,-2},
{-2,0,0,-2,0,0,0,-2,0,-2},
{-2,0,0,-2,0,0,0,-2,0,-2},
{-2,0,0,0,0,-2,-2,0,0,-2},
{-2,0,-2,-2,-2,0,0,0,0,-2},
{-2,0,0,0,-2,0,0,0,0,-2},
{-2,0,-2,0,0,0,-2,0,0,-2},
{-2,0,-2,-2,-2,0,-2,-2,0,-2},
{-2,-2,0,0,0,0,0,0,0,-2},
{-2,-2,-2,-2,-2,-2,-2,-2,-2,-2}};
if(m.mazepath(n,m,s))cout<<"i find the pass"<<endl;
else cout<<"there is no pass available"<<endl;
}
|
