11214 – Guarding the Chessboard（暴力搜索）
分类：
IDA*算法， 从小到大枚举深度上限，不过该题是有深度上限的，题目中的第一个样例表明：最多需要5个皇后就可以覆盖整个棋盘 。
利用紫书上的技巧，我们可以快速的判断任意两个棋子是不是在同一行、同一列、同一对角线 （详情见紫书P193那两个图）。
这样之后暴力搜索就可以了 。 每一层需要O（nm）的复杂度，但是实际上并不需要那么大的复杂度 。和八皇后问题类似 ，， 当前行之前的行已经放置了皇后，所以不必在管，每次从下一行开始放置就好 。
细节见代码：#include<bits/stdc++.h>using namespace std;int n,m,maxd,kase = 0,vis[10][30];char s[15][15];bool dfs(int cur,int r) {if(cur == maxd) {for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++)if(s[i][j] == 'X' && !vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+11]) return false;}return true;}for(int i=r;i<=n;i++) {for(int j=1;j<=m;j++) {if(!vis[0][i] || !vis[1][j] ||!vis[2][i+j] ||!vis[3][i-j+11]) {int v1 = vis[0][i], v2 = vis[1][j], v3 = vis[2][i+j], v4 = vis[3][i-j+11];//注意，一定要恢复“原样”vis[0][i] = vis[1][j] = vis[2][i+j] = vis[3][i-j+11] = 1;if(dfs(cur+1,i+1)) return true;vis[0][i] = v1; vis[1][j] = v2; vis[2][i+j] = v3; vis[3][i-j+11] = v4;}}}return false;}int main() {while(~scanf("%d",&n)&&n) {scanf("%d",&m);for(int i=1;i<=n;i++) scanf("%s",s[i]+1);for(maxd = 1; maxd < 5 ; ++maxd) {memset(vis,0,sizeof(vis));if(dfs(0,0)) break;}printf("Case %d: %d\n",++kase,maxd);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇12558 – Egyptian Fractions (HARD version)（IDA*算法）
顶1踩0
终究还是会从指缝中一滴一滴流淌干净。
