【题解】还是全排列

【题解】还是全排列

小鱼干 110 2022-11-01

还是全排列

题目背景

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

题目描述

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

输入格式

一行,一个整数n。

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

输出格式

一个整数,表示方案总数

样例 #1

样例输入 #1

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

样例输出 #1

24

样例 #2

样例输入 #2

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

样例输出 #2

5

提示

1n111\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;
}

image-20221101164446762

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

由于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;
}