UVA 11214 Guarding the Chessboard(回溯)-蒲公英云

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;
}