时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3207 通过数: 1502
[题目描述]
在一个给定形状的棋盘 (形状可能是不规则的) 上面摆放棋子, 棋子没有区别. 要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列, 请编程求解对于给定形状和大小的棋盘, 摆放 k 个棋子的所有可行的摆放方案 C.
[输入]
输入含有多组测试数据.
每组数据的第一行是两个正整数 n,k, 用一个空格隔开, 表示了将在一个 n*n 的矩阵内描述棋盘, 以及摆放棋子的数目. (n≤8,k≤n)
当为−1−1 时表示输入结束.
随后的 n 行描述了棋盘的形状: 每行有 n 个字符, 其中 #表示棋盘区域,. 表示空白区域(数据保证不出现多余的空白行或者空白列).
[输出]
对于每一组数据, 给出一行输出, 输出摆放的方案数目 CC(数据保证 C<231C<231).
[输入样例]
- 2 1
- #.
- .#
- 4 4
- ...#
- ..#.
- .#..
- #...
- -1 -1
[输出样例]
2
1
解析:
这是一道八皇后的变式题, 具体来讲就是不默认棋子数, 不默认棋盘大小和形状, 因此我们必须考虑到可放置棋子的数量与行数的关系, 若照搬八皇后的解法, 是无法搜索到整张棋盘的.
故, 将其具体分析, 得知我们需要让每次放置方法的起始行递增, 直到搜索完整张棋盘. 其他还是和八皇后没太大区别.
参考代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<string>
- #include<cstdlib>
- #include<queue>
- #include<vector>
- #define INF 0x3f3f3f3f
- #define PI acos(-1.0)
- #define N 101
- #define MOD 2520
- #define E 1e-12
- using namespace std;
- int l[10],n,k,ans=0,a[10][10];// l 判断列上是否有棋子, a 储存棋盘
- char c;
- void dfs(int x,int step)//x 当前行, step 当前放置棋子数
- {
- if(step==k) ans++;
- else
- for(int i=x;i<n;i++)// 从 x 行开始搜索下面的剩余棋盘, 以得到整张棋盘的解
- for(int j=0;j<n;j++)
- {
- if(l[j]==0&&a[i][j]==1)
- {
- l[j]=1;
- dfs(i+1,step+1);
- l[j]=0;
- }
- }
- }
- int main()
- {
- do
- {
- memset(l,0,sizeof(l));
- memset(a,0,sizeof(a));
- ans=0;
- scanf("%d%d",&n,&k);
- if(n==-1&&k==-1) break;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- cin>>c;
- if(c=='#') a[i][j]=1;
- else a[i][j]=0;
- }
- }
- dfs(0,0);
- printf("%d\n",ans);
- }while(n!=-1&&k!=-1);
- return 0;
- }
- 2019-03-24 00:23:55
来源: http://www.bubuko.com/infodetail-2997825.html