📄 horse.cpp
字号:
#include <iostream.h>
const N=8; //定义棋盘大小
const MaxSize=N+2*2; //表示棋盘的二维数组的维数
//数组比实际棋盘多顶边、底边各二行，左边、右边各两列
class Position //表示棋盘上一格的位置
{
public:
int x,y;
Position(int x=1,int y=1)
{
this->x=x;
this->y=y;
}
};
class Horse
{
private:
int mat[MaxSize][MaxSize]; //表示棋盘的二维数组
bool show; //是否显示中间结果
int get(Position p); //获得p格的值
void set(Position p,int i); //设置p格的值为i
bool isValid(Position p); //判断p是否在棋盘内且未被占领过
Position goaStep(Position p,int k); //返回p位置按k方向的下一位置
int select(Position p); //选择p位置到达下一位置next1应走的方向k
void output(); //输出棋盘上所有格的元素
public:
Horse(bool show=false);
~Horse(){}
void play(int x,int y); //从(x,y)格开始游历
};
Horse::Horse(bool show)
{ //数组比实际棋盘多顶边、底边各二行，左边、右边各两列
this->show=show;
for(int i=0;i<MaxSize;i++) //棋盘初始化
for(int j=0;j<MaxSize;j++)
if(i>1 && i<MaxSize-2 && j>1 && j<MaxSize-2)
mat[i][j]=0; //棋盘单元格初值
else
mat[i][j]=-1; //棋盘边界
}
int Horse::get(Position p) //获得p格的值
{
return mat[p.x+1][p.y+1];
}
void Horse::set(Position p,int i) //设置p格的值为i
{
mat[p.x+1][p.y+1]=i;
}
void Horse::play(int x,int y) //从(x,y)格开始游历
{
Position current(x,y); //当前位置
int count=1; //统计第几步,count记录走过的格数
int k=1;
while(count<=N*N && k!=0)
{
set(current,count);
if(show)
cout<<"第"<<count<<"步 ";
k=select(current); //试探，选择一个方向
if(k==0 && count<N*N)
cout<<"第"<<count<<"步无路可通!";
else
{
count++; //步数加1
current=goaStep(current,k); //向前走一步
}
}
if(!show)
output();
}
bool Horse::isValid(Position p) //判断p是否在棋盘内且未被占领过
{
return (p.x>=1 && p.x<=N && p.y>=1 && p.y<=N && get(p)==0);
}
Position Horse::goaStep(Position p,int k)
{ //返回p位置按k方向的下一位置
int x=p.x;
int y=p.y;
switch(k)
{
case 1: x-=2; y++; break;
case 2: x--; y+=2; break;
case 3: x++; y+=2; break;
case 4: x+=2; y++; break;
case 5: x+=2; y--; break;
case 6: x++; y-=2; break;
case 7: x--; y-=2; break;
case 8: x-=2; y--; break;
}
Position q(x,y);
return q;
}
int Horse::select(Position p) //选择p位置到达下一位置next1应走的方向k
//试探next1的8个方向位置next2的可通路数road,road的最小值为minroad
{
int i=0,j=0,k=0,road=0,minroad=8;
Position next1,next2;
if(show)
{
cout<<"当前位置: ("<<p.x<<","<<p.y<<")"<<endl;
output();
cout<<"方向 下一位置 可通方向 可通路数"<<endl;
}
for(i=1;i<=8;i++) //试探位置p(x,y)的8个方向的位置next1
{
road=0;
next1=goaStep(p,i); //next1是p按i方向的下一位置
if(isValid(next1)) //next1在棋盘内且未被占领过
{
if(show)
cout<<" "<<i<<"\t("<<next1.x<<","<<next1.y<<")\t";
for(j=1;j<=8;j++) //统计next1(x,y)的可通路数road
{
next2=goaStep(next1,j); //next2是next1按j方向的下一位置
if(isValid(next2)) //next2在棋盘内且未被占领过
{
road++;
if(show)
cout<<j<<",";
}
}
if(road<minroad)
{
minroad=road; //minroad记载road的最小值
k=i; //k记载road最小值的方向
}
if(show)
cout<<"\t"<<road<<endl;
}
}
if(show)
cout<<"选定下一步方向 k="<<k<<"\r\n\n";
return k;
}
void Horse::output() //输出棋盘上所有格的元素
{
for(int i=0;i<MaxSize;i++)
{
for(int j=0;j<MaxSize;j++)
cout<<" "<<mat[i][j];
cout<<endl;
}
cout<<endl;
}
void main()
{
Horse h1(true);
h1.play(1,1); //从(x,y)格开始游历
}
/*
程序运行结果如下：
第1步 当前位置: (1,1)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
3 (2,3) 2,3,4,5,6, 5
4 (3,2) 1,2,3,4,5, 5
选定下一步方向 k=3
第2步 当前位置: (2,3)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 2 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
2 (1,5) 3,4,5, 3
3 (3,5) 1,2,3,4,5,6,8, 7
4 (4,4) 1,2,3,4,5,6,7, 7
5 (4,2) 2,3,4,5,8, 5
6 (3,1) 1,3,4, 3
选定下一步方向 k=2
第3步 当前位置: (1,5)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 3 0 0 0 -1 -1
-1 -1 0 0 2 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
3 (2,7) 4,5,6, 3
4 (3,6) 1,2,3,4,5,6,7, 7
5 (3,4) 2,3,4,5,6,7,8, 7
选定下一步方向 k=3
第4步 当前位置: (2,7)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 3 0 0 0 -1 -1
-1 -1 0 0 2 0 0 0 4 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
4 (4,8) 5,6,7, 3
5 (4,6) 2,3,4,5,6,7,8, 7
6 (3,5) 1,3,4,5,6,8, 6
选定下一步方向 k=4
第5步 当前位置: (4,8)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 3 0 0 0 -1 -1
-1 -1 0 0 2 0 0 0 4 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 5 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
5 (6,7) 4,5,6,7,8, 5
6 (5,6) 1,3,4,5,6,7,8, 7
7 (3,6) 1,2,4,5,6,7, 6
选定下一步方向 k=5
第6步 当前位置: (6,7)
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 1 0 0 0 3 0 0 0 -1 -1
-1 -1 0 0 2 0 0 0 4 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 5 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 6 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
方向 下一位置 可通方向 可通路数
4 (8,8) 7, 1
5 (8,6) 2,7,8, 3
6 (7,5) 1,3,6,7,8, 5
7 (5,5) 1,2,4,5,6,7,8, 7
8 (4,6) 2,3,5,6,7,8, 6
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -