关于算法:POJ-1321-棋盘问题dfs位运算

惯例的搜寻是很容易想到的，不再详述。

如果你浏览过 Matrix67 的博客中八皇后问题对于 位运算的优化，此题也有相似的优化伎俩，而且此题比原题简略得多。

先放代码，上面是剖析。

/*
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <functional>
*/

#include "lab.h"// 预编译头

typedef long long ll;

#define    _fora(i,a,n)    for(ll i=(a);i<=(n);i++)
#define    _forz(i,a,n)    for(ll i=(a);i>=(n);i--)
#define    _forb(i,a)        for(ll i=(a);i>0;i-=i&(-i))

using namespace std;

int n,k;
int nn[10];

int sum(int n) {
    int rst = 0;
    _forb(i,n)
        rst++;
    return rst;
}

int dfs(int tn,int prv,int a) {
    int rst = 0;
    int ans = (~prv) & nn[tn];
    if(tn+a < n)
        rst += dfs(tn+1,prv,a);
    if(a == 1) {rst += sum(ans);
        return rst;
    }
    _forb(i,ans) {rst += dfs(tn+1,prv|(i&(-i)),a-1);
    }
    return rst;
}

int main() {while(scanf("%d %d", &n,&k) != EOF) {if(n+k<0)
            break;
        char ch[10][10];
        nn[n] = (1<<n)-1;
        _fora(ia,0,n-1) {scanf("%s",ch[ia]);
            nn[ia] = 0;
            _fora(ib,0,n-1) {nn[ia] = nn[ia] << 1;
                if(ch[ia][ib] == '#')
                    nn[ia] += 1;
            }
        }
        printf("%d\n", dfs(0,0,k));
    }
    return 0;
}

题解 2020-09-24

请先浏览 Matrix67 的博客，我不感觉我能讲的比他好。

如不理解运算 x&(-x)，请查阅 lowbit 或者树状数组相干信息。

咱们来看怎么把同样的思维套进此题里。因为 n 最大只有 8，int 塞下一整行入不敷出。

main 里先读入，按位初始化到 int nn[10]。如果第 t 行是 ..#.，那么 nn[t] = 0b0010。

要害在搜寻 dfs(tn,prv,a)。其中 tn 为到了第几行，a 为还剩多少棋子，prv 是已搁置的信息，返回值是答案。

int dfs(int tn,int prv,int a);

那么 prv 取反即是以后行不抵触信息，nn[tn] 是以后行棋盘信息，相与失去 ans，即为以后行可搁置信息。

int ans = (~prv) & nn[tn];

如果 tn+a < n，能够思考这一行不放。

if(tn+a < n)
    rst += dfs(tn+1,prv,a);

如果 a = 1，阐明棋子曾经全副搁置，计算 ans 中 1 的个数并返回。

if(a == 1) {rst += sum(ans);
    return rst;
}

外围局部，ans 蕴含了整行的可搁置信息，能够通过 lowbit 取出低位地位。

所以应用宏 _forb 一直循环 i，则 lowbit(i) 是每个可搁置地位，用或运算把此地位退出已搁置信息，递归进入下一行。

_forb(i,ans) {rst += dfs(tn+1,prv|(i&(-i)),a-1);
}

以上。