还是全排列

题目背景

本题为全排列的“升级版”

题目描述

给定 $n \times n$ 的棋盘，“*”表示可放，“.”表示不可放，每行放一个棋子，要求不能有两个及以上的棋子出现在同一列上（即每一列只能放一个），请问有多少种放置的方法？

输入格式

一行，一个整数n。

接下来n行，每行n个字符，表示棋盘。

输出格式

一个整数，表示方案总数

样例 #1

样例输入 #1

4
****
****
****
****

样例输出 #1

样例 #2

样例输入 #2

4
**.*
*.*.
**..
****

样例输出 #2

提示

$1\leqslant n \leqslant 11$

题目分析

题目要求的是在行、列不重复的前提下，有多少种放置的方法。
初始思路：定义col[] 数组用于标记某列上是否存在重复元素。第一行，挑选某列放置棋子，放完再在下一行寻找位置放置棋子，若某一行无法放置，则退回上一行，重新放置棋子，重复该步骤，直至所有棋子放完n行为止。

可以采用递归结合标记数组进行实现。

#include <iostream>
#include <cstdio>
using namespace std;
bool col[15];//col[d] 
bool vis[15][15];
int n,cnt;
char c;

void dfs(int d){//放置第d行的棋子
	if(d==n+1){//已放完n行的棋子
		cnt++;//统计方案数
		return ;
	}
	
	for(int j=1;j<=n;j++){//遍历第d行，每一列的位置
		if(vis[d][j] || col[j]) continue;//不能放置的地方跳过
		col[j]=1;//回溯，探寻下一行的放置位置
		dfs(d+1);
		col[j]=0;
	}
	
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c;
			vis[i][j]=(c=='*'?0:1);//能放的地方标记0，不能的标记1
		}
	}
	dfs(1);
	cout<<cnt;
	return 0;
}

会存在超时的点，此时可以尝试进行优化。可发现在搜索过程中越往下层，可供选择的列实际上是越少的，因为每一列最多只能有一个，按之前的搜索方式，依旧会去探索其它的早已放置过棋子的列上，此时若能直接跳过这些不能放的列，直接在可以放置棋子的列中进行搜索，必然速度能快上很多。

由于n的范围很小，我们可以尝试利用二进制的方式描述每一行上棋子的放置情况，且稍作转换将二进制中的1描述未可放置的地方，0描述未不能放置的地方，那么利用lowbit操作，迅速定位到能够放置棋子的列上，从而进行加速。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
int n,cnt=0;
char c;
int vis[15];//每一行的状态 1-能选 0-不能选
int lowBit(int x){
	return x&(-x);
}
void dfs(int d,int state){//d-放第几行 state-列的可用状态
	if(d==n){
		cnt++;
		return ;
	}
	//尝试 d行每个可能的位置
	//合并d行 和 其他行
	int u=vis[d]&state;
	while(u){//只盯着能放的地方去
		int x=lowBit(u);
		u-=x;
		dfs(d+1,state-x);
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>c;
			if(c=='*'){//(i,j) 能放
				vis[i]|=(1<<j);//标记状态
			}
		}
	}
	
	int u=(1<<n)-1;
	dfs(0,u);
	cout<<cnt;
	return 0;
}

【题解】还是全排列