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);
}以上。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论