/*************************************************************
棋盤最小滿覆蓋問題
在8×8的國際象棋棋盤上，如果在某些位置放置若干個馬之后，使整個棋盤中任意空位置上所放置的棋子均能被這些馬吃掉，則把這組放置的棋子稱為一個滿覆蓋。若去掉滿覆蓋中的任意一個棋子都破環(huán)了滿覆蓋，則稱這一覆蓋為最小滿覆蓋。
思路：不妨先在棋盤上放滿棋子，遞歸進(jìn)行拿去操作，一直到無法拿取時，當(dāng)前棋盤即為一個最小滿覆蓋。?
問題要點(diǎn)：1.在棋盤上放滿棋子后，記錄每個棋子被攻擊的次數(shù)
		??2.拿取操作，對攻擊次數(shù)數(shù)組有小到大進(jìn)行排序，然后順次判斷是否能進(jìn)行拿取，拿取之后更新攻擊次數(shù)數(shù)組，進(jìn)行下一次拿取。
		??3.當(dāng)不能進(jìn)行拿取時打印當(dāng)前棋盤，即為一個滿覆蓋。?
**************************************************************/
#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;???????????????????????//攻擊次數(shù)
	int?horse;???????????????????????//是否放有馬?
	int?count2;??????????????????????//該位置可影響的馬被攻擊次數(shù)總和?
}boardpoint;?????????????????????????//棋盤元素

typedef?struct{
	int?xy;?????????????????????????//棋盤位置
	int?count;???????????????????????//攻擊次數(shù)?
	int?count2;					?????//該位置可影響的馬被攻擊次數(shù)總和?
}attackpoint;????????????????????????//攻擊次數(shù)數(shù)組元素

boardpoint?cb[M][N];?????????????????//棋盤?
attackpoint?attack[M*N];?????????????//攻擊次數(shù)數(shù)組

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

//初始化棋盤?
void?initial（）;

//交換
void?Swap（attackpoint?*pattackpoint?*q）;?

//快速排序（對count的值進(jìn)行排序）
void?QuickSort（int?lowint?high）;

//快速排序（對count2的值進(jìn)行排序）
void?QuickSort2（int?lowint?high）;

//對attack數(shù)組中值重復(fù)的部分進(jìn)行排序?
void?Sort（）;

//封裝函數(shù)
void?manfugai（）;?

//放置棋子后更新attack數(shù)組?
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?		{
			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）