惯例的搜寻是很容易想到的，不再详述。
如果你浏览过 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);}以上。