$$\color{Purple}{kuangbin题解目录}$$
描述
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。
要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放 $k$ 个棋子的所有可行的摆放方案数目 $C$。
输入格式
输入含有多组测试数据。
每组数据的第一行是两个正整数 $n, k$,用一个空格隔开,表示了将在一个 $n\*n$ 的矩阵内描述棋盘,以及摆放棋子的数目。当为-1 -1
时表示输入结束。
随后的 $n$ 行描述了棋盘的形状:每行有 $n$ 个字符,其中 #
表示棋盘区域, .
表示空白区域(数据保证不出现多余的空白行或者空白列)。
输出格式
对于每一组数据,给出一行输出,输出摆放的方案数目 $C$ (数据保证 $C < 2^{31}$)。
数据范围
$n \\le 8,k \\le n$
输入样例:
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
输出样例:
2
1
思路
经典dfs问题.
方法一: 枚举每一个元素,时间复杂度为$O(2^{n^2})$.
方法二: 枚举每一行(或每一列),时间复杂度为$O(n!)$.
代码
- 方法一 :枚举每一个元素
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 10
using namespace std;
int n,k,res;
char g[MAXN][MAXN];
int row[MAXN],col[MAXN];
void dfs(int x,int y,int cnt)
{
if(y==n+1)
y=1,x++;
if(x==n+1)
{
if(cnt==k)
res++;
return ;
}
if(g[x][y]=='#'&&row[x]==0&&col[y]==0)
{
g[x][y]='.';
row[x]=col[y]=1;
dfs(x,y+1,cnt+1);
g[x][y]='#';//恢复现场
row[x]=col[y]=0;
}
dfs(x,y+1,cnt);//不选(x,y)的元素
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
break;
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
res=0;
//memset(col,0,sizeof(col));
//memset(row,0,sizeof(row));
dfs(1,1,0);
printf("%d\n",res);
}
return 0;
}
- 方法二: 枚举每一行(或每一列).
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 10
using namespace std;
int n,k,res;
char g[MAXN][MAXN];
int col[MAXN];//标记该列是否使用
void dfs(int root,int cnt)
{
if(root==n+1)//所有行都枚举完
{
if(cnt==k)//且使用的次数刚好为k
res++;
return ;
}
for(int i=1;i<=n;i++)
{
if(g[root][i]=='#'&&col[i]==0)
{//该点为棋盘元素,且没被访问过
g[root][i]='.';
col[i]=1;
dfs(root+1,cnt+1);//选当前行,枚举下一行
col[i]=0;//恢复现场
g[root][i]='#';
}
}
dfs(root+1,cnt);//当前行不选
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
break;
res=0;
//memset(col,0,sizeof(col));
//此处col可以不用清0,由于dfs会恢复现场使得col数组最终为0
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
dfs(1,0);
printf("%d\n",res);
}
return 0;
}