2013腾讯马拉松初赛 ACM 郑厂长系列故事——N骑士问题

[c]代码库

/*

2013腾讯马拉松初赛第5场

1005 郑厂长系列故事——N骑士问题 

Time Limit: 3.0 Seconds   Memory Limit: 65536K
 

郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
还是那个腾讯公司的码农
一个业余时间喜欢下棋的码农

最近，郑厂长对八皇后问题很感兴趣，拿着国际象棋研究了好几天，终于研究透了。兴奋之余，坐在棋盘前的他又开始无聊了。无意间，他看见眼前的棋盘上只摆了八个皇后，感觉空荡荡的，恰好又发现身边还有几个骑士，于是，他想把这些骑士也摆到棋盘上去，当然棋盘上的一个位置只能放一个棋子。因为受八皇后问题的影响，他希望自己把这些骑士摆上去之后，也要满足每2个骑士之间不能相互攻击。
现在郑厂长想知道共有多少种摆法，你能帮助他吗？

骑士的下法：
每步棋先横走或直走一格，然后再往外斜走一格；或者先斜走一格，最后再往外横走或竖走一格（即走“日”字）。可以越子，没有"中国象棋"的"蹩马腿"限制。

Input

输入第一行为一个整数T(1<=T<=8)，表示有T组测试数据；
每组数据首先是一个整数N(1<=n<=10)，表示要摆N个骑士上去；
接下来是一个8*8的矩阵来描述一个棋盘，’.’表示这个位置是空的，’*’表示这个位置上已经放了皇后了；
数据中的初始棋盘保证是一个合法的八皇后摆法。

Output

对每组数据，请在一行内输出一个整数，表示合法的方案数。

Sample Input

2
1
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....
2
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....


Sample Output

56
1409




*/

/*
解题报告：

一看这数据范围就想到了状态压缩DP，由于马的攻击范围最多是上下2行。
所以我们只要管好前面两行的就行了，
dp[i][j][p][q]
表示第i行放马的状态是q,第i-1行的状态是p,前i行放马的个数是j个的种数。

推i+1行的时候枚举第i+1行放马的状态，进行转移。

总的复杂度无法估计，理论上是(1<<8)*(1<<8)*(1<<8)*n*8
这里需要一些剪枝，不然是通不过的。加了很多的非法判断。
*/


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<list>
using namespace std;
typedef __int64 lld;
const int MAX = 10;
const int INF = 1000000000;
const double EPS = 1.0e-8;
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
int dblcmp(double x) {
    if(fabs(x) < EPS)return 0;
    return x < 0 ? -1 : 1;
}
int a[MAX];
lld dp[2][11][1 << 8][1 << 8];
char s[MAX];
bool ok1[1 << 8][1 << 8];
bool ok2[1 << 8][1 << 8];
bool judge(int a, int b, int d) {
    int i;
    int x, y;
    for(i = 0; i + d - 1 < 8; i++) {
        x = 1 << i;
        y = 1 << i << d;
        if((x & a) && (y & b))return false;
        if((x & b) && (y & a))return false;
    }
    return true;
}
int cnt[1 << 8];
int count(int n) {
    int ret = 0;
    while(n) {
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}
int main() {

    int n = 6;
    int i, j;
    int k;
    int T;
    int CS = 1;
    for(i = 0; i < (1 << 8); i++) {
        for(j = 0; j < (1 << 8); j++) {
            ok1[i][j] = judge(i, j, 1);
            ok2[i][j] = judge(i, j, 2);
        }
    }
    for(i = 0; i < (1 << 8); i++) {
        cnt[i] = count(i);
        //    printf("cnt[%d]=%d\n",i,cnt[i]);
    }
    //printf("%d\n",1<<8);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(i = 0; i < 8; i++) {
            scanf("%s", s);
            a[i] = 0;
            for(j = 0; j < 8; j++) {
                a[i] *= 2;
                if(s[j] == '*')a[i]++;
            }
            //    printf("a[%d]=%d\n",i,a[i]);
        }

        memset(dp, 0, sizeof(dp));
        int xx = 0;
        for(i = 0; i < (1 << 8); i++) {
            if(i & a[0])continue;
            if(cnt[i] > n)continue;
            dp[0][cnt[i]][0][i]++;
            xx++;
            //printf("i=%d\n",i);
        }
        //    printf("xx=%d\n",xx);
        int tag = 0;
        for(i = 1; i < 8; i++) {
            tag = i & 1;
            for(xx = 0; xx <= n; xx++) {
                for(j = 0; j < (1 << 8); j++) {
                    for(k = 0; k < (1 << 8); k++) {
                        dp[tag][xx][j][k] = 0;
                    }
                }
            }
            for(j = 0; j < (1 << 8); j++) {
                if(i - 2 >= 0 && (j & a[i - 2]))continue;

                for(k = 0; k < (1 << 8); k++) {
                    if(k & a[i - 1])continue;

                    if(cnt[j] + cnt[k] > n)continue;
                    if(!ok2[j][k])continue;
                    int tt;

                    for(tt = cnt[j] + cnt[k]; tt <= n; tt++) {
                        if(dp[1 - tag][tt][j][k] == 0)continue;

                        for(int z = 0; z < (1 << 8); z++) {
                            if(cnt[z] + tt > n)continue;
                            if(z & a[i])continue;
                            if(!ok2[z][k] || !ok1[z][j])continue;
                            dp[tag][tt + cnt[z]][k][z] += dp[1 - tag][tt][j][k];
                        }
                    }
                }
            }

        }

        lld ans = 0;
        for(i = 0; i < (1 << 8); i++) {
            for(j = 0; j < (1 << 8); j++) {
                //if(dp[tag][n][i][j]>0)printf("%d %d\n",i,j);
                ans += dp[tag][n][i][j];
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}
/*
2
1
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....


2
1
........
........
........
........
........
........
........
........

2
1
*******.
********
********
********
********
********
********
********
*/