Question

C++编程题！急求解答！

我们的作业，国际象棋的n*n棋盘
一个马在输入给定的初始位置开始跳，根据国际象棋中的规则跳，试找出方案，使得这个马能跳编所有的棋盘网格。
要求，输入马的初始位置坐标 格式：（行，列）
输出的解的格式，按次序输出每次跳的网格坐标 （行，列）
摆脱大家了，如果觉得贴代码不太方便请发我邮箱：daijin_sjtuer@hotmail.com
谢谢了
如果把每个国际象棋的棋子看做是放在棋盘网格的中心点，连结所有的中心点成为一个新棋盘（类似中国象棋）则马还是像中国象棋一样走日字，而且没有蹩腿

Answer 1

我试试

可以把问题看成无向图的遍历问题，每一个棋盘网格是一个点，马可以跳到的点是相连的点，构造数据结构描述棋盘网格，遍历整个图就可以了，但输出解不一定是最优解
#include <iostream>
using namespace std;

#define C_N 8
typedef struct node
{
int arc[8];
int node_x[8];
int node_y[8];

}gra_node;

typedef struct graph
{
int num;
int join[C_N][C_N];
gra_node cheese[C_N][C_N];
}ch_gra;

ch_gra My_G;
int times=0;

void init()
{
My_G.num=0;
for(int i=0;i<C_N;i++)
for(int j=0;j<C_N;j++)
{
My_G.join[i][j]=0;
for(int k=0;k<8;k++)
My_G.cheese[i][j].arc[k]=0;
}
}

void CreateGraph()
{
for(int i=0;i<C_N;i++)
for(int j=0;j<C_N;j++)
{
int k=0;
if(i+2<C_N)
{
if(j+1<C_N)
{
My_G.cheese[i][j].node_x[k]=i+2;
My_G.cheese[i][j].node_y[k]=j+1;
My_G.cheese[i][j].arc[k++]=1;
}
if(j-1>=0)
{
My_G.cheese[i][j].node_x[k]=i+2;
My_G.cheese[i][j].node_y[k]=j-1;
My_G.cheese[i][j].arc[k++]=1;
}
}
if(i+1<C_N)
{
if(j+2<C_N)
{

My_G.cheese[i][j].node_x[k]=i+1;
My_G.cheese[i][j].node_y[k]=j+2;
My_G.cheese[i][j].arc[k++]=1;
}
if(j-2>=0)
{

My_G.cheese[i][j].node_x[k]=i+1;
My_G.cheese[i][j].node_y[k]=j-2;
My_G.cheese[i][j].arc[k++]=1;
}
}
if(i-1>=0)
{
if(j+2<C_N)
{
My_G.cheese[i][j].node_x[k]=i-1;
My_G.cheese[i][j].node_y[k]=j+2;
My_G.cheese[i][j].arc[k++]=1;
}
if(j-2>=0)
{
My_G.cheese[i][j].node_x[k]=i-1;
My_G.cheese[i][j].node_y[k]=j-2;
My_G.cheese[i][j].arc[k++]=1;
}
}
if(i-2>=0)
{
if(j+1<C_N)
{
My_G.cheese[i][j].node_x[k]=i-2;
My_G.cheese[i][j].node_y[k]=j+1;
My_G.cheese[i][j].arc[k++]=1;
}
if(j-1>=0)
{
My_G.cheese[i][j].node_x[k]=i-2;
My_G.cheese[i][j].node_y[k]=j-1;
My_G.cheese[i][j].arc[k++]=1;
}
}
}
}

void print(int x,int y)
{
cout<<"横:"<<x<<"纵:"<<y<<endl;
}

void travel(int x,int y)
{
int total=C_N*C_N;
My_G.num=1; My_G.join[x][y]=1;
print(x,y);

int node_weight[8],max_weight,max_node;
while(My_G.num<total)
{
for(int i=0;i<8;i++)
{
node_weight[i]=0;
}
int k=0,tem_x,tem_y;
while(My_G.cheese[x][y].arc[k]!=0)//选择策略，下一步走哪一个点
{
tem_x=My_G.cheese[x][y].node_x[k];
tem_y=My_G.cheese[x][y].node_y[k];
if(My_G.join[tem_x][tem_y]==0)
node_weight[k]=100;
else
{
node_weight[k]=100-My_G.cheese[x][y].arc[k];
}
k++;
if(k==8)
break;
}
max_weight=node_weight[0];
max_node=0;
for(i=1;i<8;i++)
{
if(node_weight[i]>=max_weight)
{
max_weight=node_weight[i];
max_node=i;
}
}
////////////////////////////////////////
int temp;
My_G.cheese[x][y].arc[max_node]++;
temp=My_G.cheese[x][y].node_x[max_node];
y=My_G.cheese[x][y].node_y[max_node];
x=temp;
if(My_G.join[x][y]==0)
{
My_G.join[x][y]=1;
My_G.num++;
}
print(x,y);
times++;
}
}
void main()
{
int init_x,init_y;
cout<<"请输入行坐标：";
cin>>init_x;
cout<<"请输入列坐标：";
cin>>init_y;
init();
CreateGraph();
travel(init_x,init_y);
cout<<"总共跳了"<<times<<"步。"<<endl;
}

Answer 2

不会国际象棋。。。。。。。。。。。