題意：類似n皇后問題，要求用最少的皇后防守所有的X;

思路：暴力回溯，開始一直按照n皇后的思路來解（即同行同列同對角線不能有多個皇后，但事實證明本題可以，因為是逐行向下搜索，所以同行上沒有多個皇后）

AC代碼如下：

#include<cstdio>#include<cstring>using namespace std;const int maxn=10+2;char g[maxn][maxn];int vis[4][2*maxn];int n,m;bool check(){	for(int i=0;i<n;i++){		for(int j=0;j<m;j++){			if(g[i][j]=='X'){				if(!vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+maxn])				return false ;			}		}	}	return true;}bool dfs(int num,int row,int c){  //num表示皇后的個數(shù)，row表當前行，c表示放置了多少個皇后 	if(c==num){		int flag=check();		if(flag)return true;		else return false;	}	for(int i=row;i<n;i++){		for(int j=0;j<m;j++){			int a1,a2,a3,a4;      //分別保存原來的值 		        a1=vis[0][i] ,a2=vis[1][j] ,a3=vis[2][i+j] ,a4=vis[3][i-j+maxn]	;				vis[0][i]=1;vis[1][j]=1;				vis[2][i+j]=1;vis[3][i-j+maxn]=1;				if(dfs(num,row+1,c+1))return true;				vis[0][i]=a1;vis[1][j]=a2;				vis[2][i+j]=a3;vis[3][i-j+maxn]=a4;		}	}	return false;}int main(){	int count1=0;	while(scanf("%d%d",&n,&m)==2 && n){		for(int i=0;i<n;i++)scanf("%s",g[i]);		memset(vis,0,sizeof(vis));		for(int i=0;i<=n;i++){			if(dfs(i,0,0)){				PRintf("Case %d: %d/n",++count1,i);				break;			}		}	}	return 0;}