poj1321 DFS水
棋盘问题
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 11335 | Accepted: 5563 |
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
Sample Output
2 1
#include<cstdio>
#include<cstring>
int n,k;
int i;
int j;
char board[12][12];
int pos[12];
int cnt;
void DFS(int row,int num)
{
if(num==0)
{
cnt++;
return;
}
if(row>=n) return;
for(int l=0; l<n; l++)
{
if(pos[l]!=1&&board[row][l]=='#')
{
pos[l]=1;
DFS(row+1,num-1);
pos[l]=0;
}
}
DFS(row+1,num);
}
int main()
{
scanf("%d%d",&n,&k);
while(n!=-1&&k!=-1)
{
for(i=0; i<n; i++)
scanf("%s",board[i]);
cnt=0;
memset(pos,0,sizeof(pos));
DFS(0,k);
printf("%d\n",cnt);
scanf("%d%d",&n,&k);
}
return 0;
}
2021年3月02日 20:06
Great articles and great layout. Your blog post deserves all of the positive feedback it's been getting. movies123
2022年9月11日 18:40
General Knowlorge is most important subject to all Class 10 students studying in English Medium, AP 10th Gk Model Paper Telugu Medium & Urdu Medium of the State Board. So every student who is studying in the state Government & Private Schools can download the AP 10th GK Model Paper 2023 Pdf with answer solutions designed and suggested by subject experts. General Knowlorge is most important subject to all Class 10 students studying in English Medium.
2023年11月21日 22:00
出摆放的方
2024年1月19日 15:59
Board Model Papers 2024 Download with Suggestions for 10th Class Textbooks 2024 Pdf Download and SSLC New Syllabus Sample Question Paper 2024 and different types of model papers boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course Languages & Subjects Important Question for the above link.