【题解】还是全排列
还是全排列
题目背景
本题为全排列的“升级版”
题目描述
给定n×nn \times nn×n的棋盘，“*”表示可放，“.”表示不可放，每行放一个棋子，要求不能有两个及以上的棋子出现在同一列上（即每一列只能放一个），请问有多少种放置的方法？
输入格式
一行，一个整数n。
接下来n行，每行n个字符，表示棋盘。
输出格式
一个整数，表示方案总数
样例 #1
样例输入 #1
4
****
****
****
****样例输出 #1
24样例 #2
样例输入 #2
4
**.*
*.*.
**..
****样例输出 #2
5提示
1⩽n⩽111\leqslant n \leqslant 111⩽n⩽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;
}Q.E.D.
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
