asd.cpp

骑士巡游问题

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <ios.h>
//----------------其它----------------------
struct Point
{
 int x_pos;
 int y_pos;
};
Point operator+(const Point &lp,const Point &rp)
{
 Point rtnPoint;
 rtnPoint.x_pos = lp.x_pos + rp.x_pos;
 rtnPoint.y_pos = lp.y_pos + rp.y_pos;
 return rtnPoint;
}
Point operator-(const Point &lp,const Point &rp)
{
 Point rtnPoint;
 rtnPoint.x_pos = lp.x_pos - rp.x_pos;
 rtnPoint.y_pos = lp.y_pos - rp.y_pos;
 return rtnPoint;
}
Point operator+=(Point &lp,const Point &rp)
{
 lp=lp+rp;
 return lp;
}
ostream &operator<<(ostream &output, const Point &lp )
{
 output << '(' << lp.x_pos << ',' << lp.y_pos << ')';
 return output;
}
bool operator==(const Point &lp, const Point &rp)
{
 if((lp.x_pos==rp.x_pos)&&(lp.y_pos==rp.y_pos))
  return true;
 return false;
}
bool operator!=(const Point &lp, const Point &rp)
{
 return !(lp==rp);
}
//............
struct trajPoint
{
 Point Location;
 int _movedDirec[8];
};
ostream &operator<<(ostream &output, const trajPoint &lp )
{
 output << '(' << lp.Location.x_pos << ',' << lp.Location.y_pos << setw(3) << setiosflags(ios::left) << ')';
 for (int i=0; i<8; i++)
  output << '[' << lp._movedDirec[i] << ']';
 return output;
}
//--------------变量定义--------------------
Point curLocation={0,0};//当前坐标
int curPointSub=-1;//当前坐标下标
bool debugTar=false;
//----------------数组----------------------
const Point moveDirec[8]={{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1}};//方向
trajPoint moveTraj[64]={{{-1,-1},{0}}};//轨迹
int moveValue[8][8]=
{
 2,3,4,4,4,4,3,2,
 3,4,6,6,6,6,4,3,
 4,6,8,8,8,8,6,4,
 4,6,8,8,8,8,6,4,
 4,6,8,8,8,8,6,4,
 4,6,8,8,8,8,6,4,
 3,4,6,6,6,6,4,3,
 2,3,4,4,4,4,3,2
};//优先表
//--------------函数原型--------------------
bool canMove(int);
//bool canMoveEx(int,Point);
bool Move();
int GetOptimumDirec();
//int GetOptimumDirecEx();
void initializeFirst();
void init_moveDirec(int []);
void init_movePoint(Point&);
void progress(int);
void retropulsion();
//------------------------------------------
int main()
{
 while(!Move())
 {
  //cout << "Progress:" << setw(3) << setiosflags(ios::right) << curPointSub << endl;
//	cout << setw(3) << setiosflags(ios::right) << curPointSub;
 }
 cout << "\n==========Move trajectory==========\n" <<endl;
 for(int e=0; e<=curPointSub; e++)
 {
  //cout << setw(2) << setiosflags(ios::left) << e << ": " << moveTraj[e] <<endl;
	 cout<<e << ": " << moveTraj[e] <<endl;
 }
 cout << "\nSuccess! Press any key to exit...";
 cin.get();cin.get();
}


bool canMove(int direcSub)//判断是否可以移动
{
 if(moveTraj[curPointSub]._movedDirec[direcSub]!=0)//在当前轨迹的移动方向历史中如果指定方向为失败方向
  return false;//返回false，结束
 Point tmp=curLocation;//初始化tmp点 记录当前坐标
 tmp += moveDirec[direcSub];//tmp尝试移动至某一方向
 if(tmp.x_pos<0 || tmp.y_pos<0 || tmp.x_pos>7 || tmp.y_pos>7)//发生溢出？
  return false;//返回false，结束
  
 else//没有溢出
  for (int i=0; i<curPointSub; i++)//在移动轨迹中寻找是否已经留下脚印
  {
   if(moveTraj[i].Location==tmp)//如果找到
    return false;//返回false，结束
  }
 return true;//上述false条件未达成，则返回true;
}


bool Move()//行动
{
 int targetSuccessSub=-1;//符合条件的方向下标(0-7)
 if(curPointSub==-1)//如果当前下标变量为-1
 {
  //printTraj();
  initializeFirst();//先初始化
 }
 else if(curPointSub<63 && curPointSub>-1)//如果当前下标变量小于63且大于-1
 {
  targetSuccessSub = GetOptimumDirec();
  //targetSuccessSub = GetOptimumDirecEx();//找到后，修改targetSuccessSub值为可行的方向下标值
  if(targetSuccessSub!=-1)//判断targetSuccessSub的值,如果有可行方向下标
  {
   progress(targetSuccessSub);
  }
  else//如果没有合适的方向，那么回退一步尝试(小心curPointSub的值)
  {
   retropulsion();
  }
 }
 else if(curPointSub==63)
  return true;
 return false;
}


int GetOptimumDirec()
{
 Point tmp;
 int tmpDirecTotal[8]={0};
 int tmpMoveValue=2;
 bool loopTar=true;
 for(int direcSub=0; direcSub<8; direcSub++)//找出可行点
 {
  if(canMove(direcSub))
   tmpDirecTotal[direcSub]=1;
 }
 while(loopTar)
 {
  for(int i=0; i<8; i++)//在可行点中找出最优点
  {
   tmp=curLocation;
   if(tmpDirecTotal[i]!=0)
   {
    tmp+=moveDirec[i];
    if(moveValue[tmp.x_pos][tmp.y_pos]==tmpMoveValue)
     return i;
   }
  }
  switch(tmpMoveValue)
  {
   case 2:
   case 3:
    tmpMoveValue+=1;
    break;
   case 4:
   case 6:
    tmpMoveValue+=2;
    break;
   case 8:
    return -1;
  }
 }
 return -1;
}


void progress(int directSub)//加入轨迹
{
 curLocation+=moveDirec[directSub];//当前坐标向可行方向下标迈出
 moveTraj[++curPointSub].Location=curLocation;//记录轨迹并修改当前点下标
 init_moveDirec(moveTraj[curPointSub]._movedDirec);//清空方向标记
 moveTraj[curPointSub]._movedDirec[directSub]=2;//把迈出的方向标记为入口方向
}


void retropulsion()//回退轨迹
{
 int directSub=-1;//记录入口
 for(int i=0;i<8;i++)
  if(moveTraj[curPointSub]._movedDirec[i]==2)//找到入口就记录下来，跳出
  {
   directSub=i;
   break; 
  }
 if(directSub==-1)
 {
  cout << "Start with location:" << curLocation << "solution set is invalid" << endl;
  initializeFirst();
 }
  
 init_movePoint(moveTraj[curPointSub].Location);
 curLocation=moveTraj[--curPointSub].Location;//当前点下标自减，按轨迹回退一格并赋给当前点坐标
 moveTraj[curPointSub]._movedDirec[directSub]=1;//把退格后的轨迹方向标记修改为"由directSub指定下标的方向为失败方向"
}


void initializeFirst()
{
 curPointSub=0;//当前下标置0
 int a=-1,b=-1;
 while(a>7 || a<0 || b>7 || a<0)
 {
  cout << "Input start point X-Position and Y-Position( 0-7 ):" << endl;
  cin >> a >> b;
 }
 Point tmp={a,b};
 cout << "Search solution use the start point:" << tmp << "..." << endl;
 //Point tmp={rand()%8,rand()%8};//初始化一个随机点
 curLocation=tmp;//放到当前点中
 moveTraj[0].Location=tmp;//放在移步记录里
}


void init_moveDirec(int direc[])
{
 for(int i=0; i<8; i++)
  direc[i]=0;
}


void init_movePoint(Point &locat)
{
 locat.x_pos=0;
 locat.y_pos=0;
}