UVA 11214 Guarding the Chessboard(回溯)

题意：类似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表示皇后的个数，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;}