棋盘极小满覆盖

棋盘最小满覆盖问题 在8×8的国际象棋棋盘上，如果在某些位置放置若干个马之后，使整个棋盘中任意空位置上所放置的棋子均能被这些马吃掉，则把这组放置的棋子称为一个满覆盖。若去掉满覆盖中的任意一个棋子都破环了满覆盖，则称这一覆盖为最小满覆盖。 算法思路： 设计棋盘每个位置的数据结构如下 typedef struct{ int count; //攻击次数 int horse; //是否放有马 int count2; //该位置可影响的马被攻击次数总和 }boardpoint; //棋盘元素 其中，count为每个位置被攻击次数（即周围存在的马的个数），count2为周围八个位置（如果不越界）count之和。 算法思路为：既然拿取到不能拿取是一个满覆盖，那不妨先在棋盘上放满棋子，不断进行拿取操作直到不能再拿取。 问题的关键就在于确定一个拿取顺序。我这里现依据count对棋盘元素有小到大排序，在count相同的情况下，再依据count2由小到大进行排序。这样就得到一个拿取顺序。在每一次拿取之后更新棋盘，重新排序，进行下一次拿取。当所有棋子都不能被拿取时，输出这个满覆盖。 在10*10棋盘上，本算法得到一个22个棋子的满覆盖。修改排序条件应该还可以进一步优化这个结果。

/*************************************************************
棋盘最小满覆盖问题
在8×8的国际象棋棋盘上，如果在某些位置放置若干个马之后，使整个棋盘中任意空位置上所放置的棋子均能被这些马吃掉，则把这组放置的棋子称为一个满覆盖。若去掉满覆盖中的任意一个棋子都破环了满覆盖，则称这一覆盖为最小满覆盖。
思路：不妨先在棋盘上放满棋子，递归进行拿去操作，一直到无法拿取时，当前棋盘即为一个最小满覆盖。 
问题要点：1.在棋盘上放满棋子后，记录每个棋子被攻击的次数
		  2.拿取操作，对攻击次数数组有小到大进行排序，然后顺次判断是否能进行拿取，拿取之后更新攻击次数数组，进行下一次拿取。
		  3.当不能进行拿取时打印当前棋盘，即为一个满覆盖。 
**************************************************************/
#include 
#include 
#include 

#define M 10
#define N 10

//顺时针处理棋子 
int fx[8]={1221-1-2-2-1};      
int fy[8]={21-1-2-2-112};

typedef struct{
	int count;                       //攻击次数
	int horse;                       //是否放有马 
	int count2;                      //该位置可影响的马被攻击次数总和 
}boardpoint;                         //棋盘元素

typedef struct{
	int xy;                         //棋盘位置
	int count;                       //攻击次数 
	int count2;					     //该位置可影响的马被攻击次数总和 
}attackpoint;                        //攻击次数数组元素

boardpoint cb[M][N];                 //棋盘 
attackpoint attack[M*N];             //攻击次数数组

//判断是否越界
bool over（int xint y）; 

//初始化棋盘 
void initial（）;

//交换
void Swap（attackpoint *pattackpoint *q）; 

//快速排序（对count的值进行排序）
void QuickSort（int lowint high）;

//快速排序（对count2的值进行排序）
void QuickSort2（int lowint high）;

//对attack数组中值重复的部分进行排序 
void Sort（）;

//封装函数
void manfugai（）; 

//放置棋子后更新attack数组 
void update（）;

//打印棋盘
void display（）;

int main（）
{
	manfugai（）;
	return 0;
}

bool over（int xint y）
{
	return（x<0 || x>=M || y<0 || y>=N）;
}

void initial（）
{
	int count2;
	int t;
	int ij;
	for（i=0;i	    for（j=0;j	    {
	    	cb[i][j].horse=1;
	    	for（t=0;t<8;t++）
	            if（!over（i+fx[t]j+fy[t]））
	                cb[i+fx[t]][j+fy[t]].count++;
		}
		
	for（i=0;i	    for（j=0;j	    {
	    	count2=0;
	    	for（t=0;t<8;t++）
	    	    if（!over（i+fx[t]j+fy[t]））
	    			count2+=cb[i+fx[t]][j+fy[t]].count;
	    	cb[i][j].count2=count2;
		} 
	    
	update（）;
}

void Swap（attackpoint *pattackpoint *q）
{
	int xycountcount2;
	x=p->x;y=p->y;count=p->count;count2=p->count2;
	p->x=q->x;p->y=q->y;p->count=q->count;p->count2=q->count2;
	q->count=count;q->x=x;q->y=y;q->count2=count2;
}

void QuickSort（int lowint high）
{
	int i=low;int j=high;
	int key=attack[low].count;
	
	if（low>=high）
	    return;
	
    while（low    {
    	while（low    	    --high;
    	if（key > attack[high].count）
    	{
    		Swap（&attack[low]&attack[high]）;
    		++low;
		}
		while（low= attack[low].count）
		    ++low;
		if（key < attack[low].count）
		{
			Swap（&attack[low]&attack[high]）;
			--high;
		}
	}
	QuickSort（ilow-1）;
	QuickSort（low+1j）;
} 

void QuickSort2（int lowint high）
{
	int i=low;int j=high;
	int key=attack[low].count2;
	
	if（low>=high）