1 、求解一个极小满覆盖。
2、最好能画出棋盘的图形形式，并在其上动态的演视试探过程。
3、程序能方便移植到其他规格棋盘上。

2个回答

#include
#include
/*get_attact( )
void chess::get_attact() //计算每个位置被马吃掉的次数
{ for(int i=0;i { for(int j=0;j { if(i-1>=0&&j-2>=0) {attact[i-1][j-2]++;}
if(i-1>=0&&j+2 if(i-2>=0&&j-1>=0) {attact[i-2][j-1]++;}
if(i-2>=0&&j+1 if(i+1=0) {attact[i+1][j-2]++;}
if(i+1 if(i+2=0) {attact[i+2][j-1]++;}
if(i+2 } } }
get_horse(chess c)
void chess::get_horse(chess c) // 计算极小满覆盖
{ int max=attact[0][0];
int max_i=0,max_j=0;
for(int i=0;i { for (int j=0;j { if(attact[i][j]>max)
{ max=attact[i][j];
max_i=i;
max_j=j;
} } }
if(attact[max_i][max_j]>=0)
{ cover[max_i][max_j]='*';
attact[max_i][max_j]=-1;
cout< cout if(max_i-1>=0 && max_j-2>=0 )
{ attact[max_i-1][max_j-2] =-1;
int i = max_i-1;
int j = max_j-2;
c.to_attact(i,j);}
if(max_i-2>=0 && max_j-1>=0)
{ attact[max_i-2][max_j-1] =-1;
int i=max_i-2;
int j=max_j-1;
c.to_attact(i,j);}
if(max_i+1= 0)
{ attact[max_i+1][max_j-2] =-1;
int i=max_i+1;
int j=max_j-2;
c.to_attact(i,j);}
if(max_i+2=0)
{ attact[max_i+2][max_j-1] =-1;
int i=max_i+2;
int j=max_j-1;
c.to_attact(i,j);}
if(max_i-1>=0 && max_j+2 { attact[max_i-1][max_j+2] =-1;
int i=max_i-1;
int j=max_j+2;
c.to_attact(i,j);}
if(max_i-2>=0 && max_j+1 { attact[max_i-2][max_j+1]=-1;
int i=max_i-2;
int j=max_j+1;
c.to_attact(i,j);
}
if(max_i+1 { attact[max_i+1][max_j+2] =-1;
int i=max_i+1;
int j=max_j+2;
c.to_attact(i,j);}
if(max_i+2 { attact[max_i+2][max_j+1] =-1;
int i=max_i+2;
int j=max_j+1;
c.to_attact(i,j);}
cout cout for(int i2=0;i2 {for(int j2=0;j2 { cout cout cout cout for(int i3=0;i3 {for(int j3=0;j3 { cout cout }system("pause");}
to_attact(int a,int b)
void chess::to_attact(int a,int b)
{if(a-1>=0&&b-2>=0&&attact[a-1][b-2]!=-1&&attact[a-1][b-2]!=0)
{ attact[a-1][b-2]--;}
if(a-2>=0&&b-1>=0&&attact[a-2][b-1]!=-1 && attact[a-2][b-1]!=0)
{ attact[a-2][b-1]--;}
if(a+1=0 && attact[a+1][b-2]!=-1 && attact[a+1][b-2]!=0)
{ attact[a+1][b-2]--;}
if(a+2=0&&attact[a+2][b-1]!=-1&& attact[a+2][b-1]!=0)
{ attact[a+2][b-1]--;}
if(a-1>=0&&b+2 {attact[a-1][b+2]--;}
if(a-2>=0&&b+1 {attact[a-2][b+1]--;}
if(a+1 { attact[a+1][b+2]--;}
if(a+2 { attact[a+2][b+1]--;} }
1.2.4 get_mincover(chess c)
void chess::get_mincover(chess c)
{ int max_attact = 0;
while(max_attact !=-1)
{ c.get_horse(c); //循环计算最小覆盖；
max_attact =-1.5;//中间变量;判断是否已完成最小覆盖的计算；
for(int i=0;i { for(int j=0;j { if(attact[i][j]>=max_attact)
{

max_attact=attact[i][j];

}

} }
} }
/
void main()
{
int M,N,k=0;
int i,j;
printf("请输入棋盘的行数M,列数N:");
scanf("%d,%d",&M,&N);
printf("棋盘的布局是：\n");
printf("________________________________________\n");
for(i=0;i<M;i++)
{

for(j=0;j<N;j++)
{
printf(" ");
printf("%d",k);
if(k<10)
printf(" ");
printf("|"); // 0
k++;
}
printf("\n");
printf("________________________________________\n");
}
}
/

chess c;
c.get_attact( );
for(int p=0;p<M;p++)
{ for(int q=0;q<N;q++)
{ cout<<attact[p][q]<<" ";}
cout<<endl; }
c.get_mincover(c);
cout<<endl;}
*/

chess c；
c.get_attact();
c.to_attact(i,j);
get_horse(chess c)

get_mincover(chess c)
void chess::get_mincover(chess c)