- 论坛徽章:
- 0
|
自己解决了
#include<iostream>
using namespace std;
const int maxSize = 64;
struct Pos{ //位置
int x , y ;
};
struct Horse{
int ord;
Pos seat;
int di;
};
int Bord[8][8]; //棋盘 0为未走过 1为走过
int movex[8]={-2,-1,1,2,2,1,-1,-2}; //x轴的移动数组
int movey[8]={1,2,2,1,-1,-2,-2,-1}; //y轴的移动数组
class Stack
{
public:
Stack();
~Stack(){delete[]elements;}
void Push(const Horse &x);//入栈
bool Pop( Horse & x);//退栈
bool getTop(Horse & x);//取栈顶元素，不删除
bool IsEmpty()const{return(top==-1)?true:false;}
bool IsFull()const{return(top==maxSize-1)?true:false;}
private:
Horse *elements; //存放栈中元素的栈数组
int top; //栈顶指针
int maxSize; //栈最大可容纳元素个数
};
Stack::Stack(){
top=-1;
maxSize=64;
elements = new Horse[maxSize];
};
void Stack::Push(const Horse & x){
if(IsFull()!=true)
elements[++top] = x;
else
cout<<"栈已满"<<endl;
};
bool Stack::Pop( Horse &x){
if(IsEmpty()==true) return false;
x = elements[top--];
return true;
};
bool Stack::getTop(Horse &x){
if(IsEmpty()==true) return false;
x=elements[top];
return true;
};
void FootPrint(Pos curpos) //走过的标记
{
Bord[curpos.x][curpos.y]=1;
}
bool Pass(Pos curpos) //判断改位置是否以走过
{
if((Bord[curpos.x][curpos.y]==0)
&(curpos.x>=0)&(curpos.y>=0)
&(curpos.x<=7)&(curpos.y<=7))
return true ;
else return false ;
}
int ways_out(int x, int y) //计算改点的出口
{
int i , count = 0 , tx ,ty ;
if(x<0||y<0||x>=8||y>=8||Bord[x][y]>0)
return -1; //-1表示该节点非法或是已经走过
for(i=0;i<8;++i)
{
tx = x + movex;
ty = y + movey;
if(tx<0||ty<0||tx>=8||ty>=8) //该节点非法或是已经走过
continue ; //直接进入下个循环
if(Bord[tx][ty]==0)
++count;
}
return count;
}
void ways_out_sort(int x ,int y) //按孙节点从少到多排序
{
int temp ;
int i , j ;
for(i=0;i<8;++i)
{
for(j=i;j<8;++j)
if(ways_out(x + movex,y + movey)>ways_out(x + movex[j],y + movey[j]))
{
temp = movex;
movex = movex[j];
movex[j] = temp ;
temp = movey;
movey = movey[j];
movey[j] = temp;
}
}
}
Pos NextPos(Pos now , int c) //当前位置的下个出口是ways_out最少的那个
{
Pos next ;
ways_out_sort(now.x,now.y);
next.x = now.x + movex[c-1];
next.y = now.y + movey[c-1];
return next;
}
bool Horse_Move(Pos star , Stack & s) //马遍历棋盘的函数
{
Horse a_horse ; Pos curpos ; int curstep ;
curpos = star ;
curstep = 1 ;
do{
if(Pass(curpos)){ //当前位置可以通过
FootPrint(curpos); //已走标志
a_horse.ord = curstep ;
a_horse.seat = curpos ;
a_horse.di = 1;
s.Push(a_horse);
if(s.IsFull()) return true ;
curpos = NextPos(curpos , 1);
curstep++ ;
}
else {
if(s.IsEmpty()==false){
s.Pop(a_horse);
while((a_horse.di==8 )&( s.IsEmpty()==false)){
Bord[a_horse.seat.x][a_horse.seat.y]=0;
s.Pop(a_horse); //留下不能通过的标记 ，退回一步
}
if(a_horse.di<8){
a_horse.di++ ;s.Push(a_horse);
curpos = NextPos(a_horse.seat,a_horse.di);
}
}
}
}
while(s.IsEmpty()==false);
return false ;
}
void Print(Stack &s) //输出函数
{
int i ,j ;int a[8][8]={0};
int m = 0 ;
Horse a_horse;
do{
s.Pop(a_horse);
a[a_horse.seat.x][a_horse.seat.y]=64-m;
++m;
}while(s.IsEmpty()==false);
for(i=0;i<8;++i){
for(j=0;j<8;++j)
cout<<a[j]<<" ";
cout<<endl;
}
}
int main()
{
Stack s ;
int i , j ;
int a , b ;
cout<<"请输入初始位置：\n"<<"(x=0~7,y=0~7)"<<endl;
cout<<"x = ";
cin>>a;
cout<<"y = ";
cin>>b;
Pos start ;
start.x = a ;
start.y = b ;
for(i=0;i<8;++i)
for(j=0;j<8;++j)
Bord[j] = 0;
Horse_Move(start , s );
Print(s);
return 0;
system("pause");
}
[ 本帖最后由 h2ojie 于 2008-7-11 17:01 编辑 ] |
|
免费注册
发表于 2008-07-10 14:06
