1217：棋盘问题
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kk 个棋子的所有可行的摆放方案 CC 。 【输入】输入含有多组测试数据。 每组数据的第一行是两个正整数n,kn,k ，用一个空格隔开，表示了将在一个n×nn×n 的矩阵内描述棋盘，以及摆放棋子的数目。 (n≤8,k≤n)(n≤8,k≤n) 当为−1−1−1−1 时表示输入结束。 随后的nn 行描述了棋盘的形状：每行有nn 个字符，其中 ## 表示棋盘区域，.. 表示空白区域（数据保证不出现多余的空白行或者空白列）。 【输出】对于每一组数据，给出一行输出，输出摆放的方案数目CC （数据保证C<231C<231 |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 35
int dx[4]= {1,0,-1,0};
int dy[4]= {0,-1,0,1};
char mp[MAXN][MAXN];
int qizi[MAXN][2];
int col[MAXN];
int n,k,cnt;
void dfs(int step)
{
for(int i=qizi[step-1][0]+1; i<=n-k+step; i++)
{
for(int j=1; j<=n; j++)
{
if(mp[i][j]=='#'&&col[j]==0)
{
col[j]=1;
qizi[step][0]=i;
if(step==k)
cnt++;
else
dfs(step+1);
col[j]=0;
qizi[step][0]=0;
}
}
}
return ;
}
int main()
{
int i,j;
cin>>n>>k;
while(n!=-1&&k!=-1)
{
memset(qizi,0,sizeof(qizi));
memset(col,0,sizeof(col));
cnt=0;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
cin>>mp[i][j];
}
}
dfs(1);
cout<<cnt<<endl;
cin>>n>>k;
}
return 0;
}
拜师教育学员文章：作者:1001-高同学，
转载或复制请以 超链接形式 并注明出处 拜师资源博客。
原文地址：《一本通——1217棋盘问题》 发布于2020-02-13
评论 抢沙发