网址如下：

Guarding the Chessboard - UVA 11214 - Virtual Judge

（第三方网址）

绞尽脑汁优化算法，结果暴力遍历就够了

孩子你无敌了

本质上是IDA

甚至不用剪枝

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>const int maxn = 9;bool G[maxn][maxn];
int vis[4][17];
int n, m;bool succeed(void){for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(G[i][j] && !vis[0][i] && !vis[1][j] && !vis[2][i + j] && !vis[3][i - j + 8])return false;return true;
}
bool dfs(int idx, int d, int maxd){if(succeed()) return true;if(d == maxd) return false;for(int cur = idx; cur < n * m; cur++){int i = cur / m, j = cur % m;vis[0][i]++; vis[1][j]++; vis[2][i + j]++; vis[3][i - j + 8]++;if(dfs(idx + 1, d + 1, maxd)) return true;vis[0][i]--; vis[1][j]--; vis[2][i + j]--; vis[3][i - j + 8]--;}return false;
}int main(void)
{int kase = 0;while(scanf("%d", &n) && n){scanf("%d", &m); getchar();for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)G[i][j] = getchar() == 'X';getchar();}for(int maxd = 1; maxd <= std::min(m, n); maxd++){memset(vis, 0, sizeof(vis));if(dfs(0, 0, maxd)){printf("Case %d: %d\n", ++kase, maxd);break;}}}return 0;
}