本题题意：
输入一个n*m的棋盘，某些格子有标记，用最少的皇后占据或者攻击所以带标记的格子。皇后的攻击范围为同行同列和同对角线。
可以使用IDA*算法，即从样例可以发现只需要最多5个棋子就可以对棋盘上所有地方进行攻击，因而使用IDA*进行对应的剪枝即可。
#include<cstdio>
#include<cstring>
using namespace std; int n,m,kase=,maxd;
bool vis[][];///表示皇后已经攻击的范围，vis[0][]中存储的是行，vis[1][]中存储的是每列，vis[2][]中存储的是每个副对角线，vis[3][]是每个主对角线
char chess[][]; bool dfs(int pos,int r)
{
if(pos==maxd){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if(chess[i][j]=='X'&&!vis[][i]&&!vis[][j]&&!vis[][i+j]&&!vis[][i-j+n])///如果达到最大深度，但是仍有X点不处于皇后的攻击范围内，则剪枝
return false;
}
return true;
}
for(int i=r;i<=n;i++)///从当前行开始，因为前面的行已经搜索过
for(int j=;j<=m;j++){
if(!vis[][i]||!vis[][j]||!vis[][i+j]||!vis[][i-j+n]){///若存在有未被攻击的地方，则进行放棋
bool v1=vis[][i],v2=vis[][j],v3=vis[][i+j],v4=vis[][i-j+n];
vis[][i]=vis[][j]=vis[][i+j]=vis[][i-j+n]=true;
if(dfs(pos+,r+)) return true;///若要放置棋子数最小，则皇后必定会放于是X的位置
vis[][i]=v1,vis[][j]=v2,vis[][i+j]=v3,vis[][i-j+n]=v4;///还原
}
}
return false;
} int main()
{
while(~scanf("%d%d",&n,&m)&&n)
{
for(int i=;i<=n;i++) scanf("%s",chess[i]+);
for(maxd=;maxd<;maxd++)
{
memset(vis,,sizeof(vis));
if(dfs(,)) break;
}
printf("Case %d: %d\n",++kase,maxd);
}
return ;
}