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

以上。

评论

暂无评论