POJ 1312棋盘问题

问题

题目链接

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C

input

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）

Sample Input

2 1#..#4 4...#..#..#..#...-1 -1

Sample Output

21

问题分析

分析链接

AC代码

#include <iostream>#include <cstring>using namespace std;int n,k;int sum;int count; int T[8];char s[10][10];void dfs(int x,int n,int k){if(count == k){sum = sum + 1;return ;}if(x >= n) {return ;} for(int i = 0; i < n; i++){if(!T[i] && s[x][i] == "#"){T[i] = 1;count++;dfs(x+1,n,k);T[i] = 0;count--;}}dfs(x+1,n,k);}int main(){while(1){cin>>n>>k;if(n == -1 && k == -1){break;}sum = count = 0;for(int i = 0; i < n; i++){cin>>s[i];}memset(T, 0 , sizeof(T));dfs(0,n,k);cout<<sum<<endl;}}