#include <stdio.h>
#define max_h 9
#define max_s 10
chesschess()//构造函数的实现
{
int attack[max_h][max_s];
for(int i= 0;i<max_s;i++)
{
for(int j=0;j<max_s;j++)
{
cover[i][j]='N';//棋盘初始状态都是没放马
attack[i][j]=0;//受攻击次数都为0
}
}
max_i=0;//受攻击最多的马坐标?0 ?0?
max_j=0;
}
void chess::get_attack(){//受攻击次数数组的实现
for(int i = 0; i < max_h;i++){
for(int j=0;j<max_s;j++){
if(i-1>=0&&j-2>=0){attack[i-1][j-2]++;}//
将当前位置的-1.-2方向的位置被吃次数加1
if(i-1>=0&&j+2<max_s){ attack[i-1][j+2]++;}
//将当前位置的-1.2方向的位置被吃次数加1 ?
if(i-2>=0&&j-1>=0){attack[i-2][j-1]++;}//
将当前位置的-2.-1方向的位置被吃次数加1
if(i-2>=0&&j+1<max_s){attack[i-2][j+1]++;}//
将当前位置的-2.1方向的位置被吃次数加1
if(i+1<max_h&&j-2>=0){attack[i+1][j-2]++;}//
将当前位置的1.-2方向的位置被吃次数加1
if(i+1<max_h&&j+2<max_s){attack[i+1][j+2]++;}//
将当前位置的1.2方向的位置被吃次数加1
if(i+2<max_h&&j-1>=0){attack[i+2][j-1]++;}//将
当前位置的2.-1方向的位置被吃次数加1
if(i+2<max_h&&j+1<max_s ){ attack[i+2][j+1]++;}//将当前
位置的2.1方向的位置被吃次数加1}
}
}
//坐标?a,b?上放马对攻击次数的影响
void chess::to_attack(int a,int b){
if(a-1>=0&&attack[a-1][b]!= 0)//其蹩(a-1,b)
位置上的马吃(a+1,b-1)和(a+1,b+1)上的马
{if(a+1<max_h && b-1 >= 0&&cover[a+1][b-1]=='N')
attack[a+1][b-1]--;
if(a+1<max_h && b+1 <max_s&&cover[a+1][b+1]=='N')
attack[a+1][b+1]--;}
if(a+1 <max_h && attack[a+1][b] != 0){
if(a-1 >= 0 && b-1 >= 0&&cover[a-1][b-1]=='N')
attack[a-1][b-1]--;
if(a-1 >= 0 && b+1 <max_s&&cover[a-1][b+1]=='N')
attack[a-1][b+1]--;}
if(b+1 <max_h &&
attack[a][b+1] != 0){
if(a+1 <max_h&& b-1 >= 0&&cover[a+1][b-1]=='N')
attack[a+1][b-1]--;
if(a-1 >= 0 && b-1>= 0&&cover[a-1][b-1]=='N')
attack[a-1][b-1]--;}
if(b-1>= 0 &&
attack[a][b-1] != 0){
if(a-1 >= 0 && b+1 <max_s&&cover[a-1][b+1]=='N')
attack[a-1][b+1]--;
if(a+1 >= 0 && b+1 <max_s&&cover[a+1][b+1]=='N')
attack[a+1][b+1]--;
}
}
void chess::get_horse(){//得到攻击次数最高的马的函
数实现
max = attack[0][0];//用 Max暂时储存被吃次数最多的
位置上被吃次数?中间变量
for(int i = 0; i < max_s; i++){
for(int j = 0; j < max_s; j++){
if(attack[i][j] > max){
max = attack[i][j];
max_i = i;
max_j = j;
}
}
}
}
void chess::put_horse()//放马的实现
{
if(attack[max_i][max_j] >= 0 )
{ //用数组Attack[Max_i][Max_j]储存被吃几率最大位置
上的被吃次数
cover[max_i][max_j] = '*';//在覆盖数组中标志此位置
为已放马.
attack[max_i][max_j] =0;//不能忘记将该位置也标记已
放马。
if(max_i-1>=0&&max_j-2>=0&&cover[max_i][max_j-1]!='*
'){
cover[max_i-1][max_j-2]='Y';
attack[max_i-1][max_j-2]=0;}
if(max_i-1>=0&&max_j+2<max_s&&cover[max_i][max_j+1]!='*
') {
cover[max_i-1][max_j+2]='Y';
attack[max_i-1][max_j+2] = 0;}
if(max_i-2>=0&&max_j+1<max_s&&cover[max_i-1][max_j]!
='*') {
cover[max_i-2][max_j+1]='Y';
attack[max_i-2][max_j+1] = 0;}
if(max_i-2>=0&&max_j-1>0&&cover[max_i-1][max_j]!='*')
{
cover[max_i-1][max_j+2]='Y';
attack[max_i-1][max_j+2] = 0;}
if(max_i+1<max_h&&max_j-2>0&&cover[max_i][max_j-1]!=
'*') {
cover[max_i+1][max_j-2]='Y';
attack[max_i+1][max_j-2] = 0;
}
if(max_i+1<max_h &&
max_j+2<max_s&&cover[max_i][max_j+1]!='*') {
cover[max_i+1][max_j+2]='Y';
attack[max_i+1][max_j+2] = 0;
}
if(max_i+2<max_h &&
max_j-1>0&&cover[max_i+1][max_j]!='*') {
cover[max_i+2][max_j-1]='Y';
attack[max_i+2][max_j-1] = 0;
}
if(max_i+2<max_h&&max_j+1<max_s&&cover[max_i+1][max_
j]!='*') {
cover[max_i+2][max_j+1]='Y';
attack[max_i+2][max_j+1] = 0;
}
to_attack(max_i,max_j);
}
}
void chess::get_cover()//得到最小覆盖函数的实现
{
while(1){
do{
get_horse();
if(max!=0&&cover[max_i][max_j]!='N')
return;
}while(cover[max_i][max_j]!='N');
put_horse();
}
}
void chess::print_out()//输出棋盘函数的实现
{ for(int i = 0; i < max_s; i++){
for(int j = 0; j < max_s; j++){
cout<<cover[i][j]<<" ";
}
cout<<endl;
}
}
//主函数的实现
Void main??{
Chess c;//定义一个对象
c.get_attack();//生成攻击表格
c.get_cover();//完成极小覆盖的求解
c.print_out();//输出棋盘
}