首页 > 代码库 > uva 11195 Another queen (用状态压缩解决N后问题)

uva 11195 Another queen (用状态压缩解决N后问题)

2024-07-11 21:57:52   222人阅读

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2136


Problem A

Another n-Queen Problem

I guess the n-queen problem is known by every person who has studied backtracking. In this problem you should count the number of placement ofn queens on an n*n board so that no two queens attack each other. To make the problem a little bit harder (easier?), there are some bad squares where queens cannot be placed. Please keep in mind that bad squares cannot be used to block queens‘ attack.

Even if two solutions become the same after some rotations and reflections, they are regarded as different. So there are exactly 92 solutions to the traditional 8-queen problem.

Input

The input consists of at most 10 test cases. Each case contains one integers n (3 < n < 15) in the first line. The following n lines represent the board, where empty squares are represented by dots ‘.‘, bad squares are represented by asterisks ‘*‘. The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the number of solutions.

Sample Input

8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
0

Output for the Sample Input

Case 1: 92
Case 2: 1
Rujia Liu‘s Present 1: A Tiny Contest of Brute Force


n后问题的加强版，采用普通的回朔会超时，所以用状态压缩和位运算加以优化。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX=20;
int str[MAX];//原串
int n,msk;
char s[MAX];//原串
int dfs(int dep,int dow,int lefd,int rigd){//dow，lefd，rigd表示上一层所能攻击到的区域
    if(dep>=n) return 1;
    int cur=~( str[dep] | dow | lefd | rigd );//反转得到1表示这一层，可以放的地方，0表示这一层不可以放的地方。
    int p=cur&(-cur)&msk;//搞到最后一个非0位
    int ret=0;
    while(p){
        ret+=dfs(dep+1,dow|p,(lefd|p)<<1,(rigd|p)>>1);
        cur^=p;//那位置0
        p=cur&(-cur)&msk;
    }
    return ret;
}
int main(){
    int cas=0;
    while(scanf("%d",&n),n){
        msk=(1<<n)-1;
        for(int i=0;i<n;i++){
            scanf("%s",s);
            str[i]=0;
            for(int j=0;s[j];j++){
                if(s[j]=='*'){
                    str[i]|=(1<<j);//把不能访问的区域标志成1
                }
            }
        }
        printf("Case %d: %d\n",++cas,dfs(0,0,0,0));
    }
    return 0;
}





联系
我们