题目：
输入一个n*m的棋盘(n,m<10)，某些格子有标记，用最少的皇后守卫（即占据或攻击）所有的标记的格子。输出皇后的个数。
思路：
一开始没有想到用迭代加深搜索，直接dfs结果还没写完就发现这样要枚举的量太大了……于是换用迭代加深搜索。对于每个格子有四个方向可以用i，j，i+j，i+j+maxn（下标要是正的）表示，当cur等于枚举的答案maxd就判断是不是所有的标记都被攻击了。
另外如果这个格子放上了皇后，那该皇后所在行的后边的格子就没必要枚举了，直接跳到下一行的开头就可以了。
将二维数组线性表示的代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int maxn = ;
char mp[maxn][maxn];
int vis[][maxn*];
int n,m,maxd; bool isok(){//判断所有的标记是不是都已经被攻击
for(int i=; i<n; i++){
for(int j=; j<m; j++){
if(mp[i][j]=='X' && !vis[][i] && !vis[][j] && !vis[][i+j] && !vis[][i-j+maxn]){
return false;
}
}
}
return true;
} bool dfs(int now, int cur){
if(cur==maxd){
return isok() ? true : false;
} for(int k=now; k<n*m; k++){
int i = k/n,j = k%m;
vis[][i]++; vis[][j]++; vis[][i+j]++; vis[][i-j+maxn]++;//对四个方向进行标记
if(dfs((i+)*m,cur+)){
return true;
}
vis[][i]--;vis[][j]--;vis[][i+j]--;vis[][i-j+maxn]--;//恢复四个方向dfs之前的状态
}
return false;
} int main(){
//FRE();
int kase = ;
while(scanf("%d",&n) && n){
scanf("%d",&m);
getchar();
for(int i=; i<n; i++){
gets(mp[i]);
}
memset(vis,,sizeof(vis));
for(maxd = ;; maxd++){
if(dfs(,)){
break;
}
}
printf("Case %d: %d\n",++kase,maxd);
}
return ;
}
正常二维数组表示代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int maxn = ;
char mp[maxn][maxn];
int vis[][maxn*];
int n,m,maxd; bool isok(){//判断所有的标记是不是都已经被攻击
for(int i=; i<n; i++){
for(int j=; j<m; j++){
if(mp[i][j]=='X' && !vis[][i] && !vis[][j] && !vis[][i+j] && !vis[][i-j+maxn]){
return false;
}
}
}
return true;
} bool dfs(int x,int y, int cur){
if(cur==maxd){
return isok() ? true : false;
} for(int i=x; i<n; i++){
for(int j=y; j<m; j++){
vis[][i]++; vis[][j]++; vis[][i+j]++; vis[][i-j+maxn]++;//对四个方向进行标记
if(dfs(i+,,cur+)){//这一行后边的都不用遍历了，直接跳到下一行的开头就可以了
return true;
}
vis[][i]--;vis[][j]--;vis[][i+j]--;vis[][i-j+maxn]--;//恢复四个方向dfs之前的状态
}
}
return false;
} int main(){
//FRE();
int kase = ;
while(scanf("%d",&n) && n){
scanf("%d",&m);
getchar();
for(int i=; i<n; i++){
gets(mp[i]);
} for(maxd = ;; maxd++){
memset(vis,,sizeof(vis));
if(dfs(,,)){
break;
}
}
printf("Case %d: %d\n",++kase,maxd);
}
return ;
}