POJ1321 棋盘问题(详解)

 题目

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

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

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

Sample

Inputcopy	Outputcopy
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1

 思路：

 看到这个题我先想到的是n皇后问题，不太记得的同学可以看看这篇文章，他们都是在满足这一行的条件下在继续搜索下一行。但是这个题目有点不同，n皇后问题是n行n个皇后都要占满，而这个题是 难点一：n行只要占满k个就OK了，所以这就是一个难点。那怎么解决的呢？n皇后中是当当前行数大于总的n行时满足条件，那我们这里其实也是类似的，我们这里是需要新建立一个参数m，表示我们已经放置的棋子数，当棋子数等于目标k值时就是一种方案啦。难点二：两个棋子不能放在棋盘中的同一行或者同一列。其实同一行好办，因为我们根本不会重复，因为在当前行有一列满足条件时我们直接搜索下一行了所以不会冲突。同一列怎么办呢？其实也简单，就是我们直接定义一个数组来表示当前列是否被选择过了就行啦，因为同一列嘛，当然是所有行的同一列都是用同一个pos[j]来表示啦。

 代码：

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<string.h>
#include<queue> 
using namespace std;
char c[10][10];
int cnt;//方案数 
int n,k,m;//n为维数，k为目标棋子数，m为当前已经安置的棋子数 
int pos[10];//标记每一列的选取情况，如果被选取了就为1 
int vis[10][10];//标记每一个棋盘位置 

void dfs(int t,int m){ //t为行数 
		if(m>=k){
		cnt++;
		return;
		}
		if(t>n)return;

	for(int i=1;i<=n;i++){//列 ，就是当前为t行，遍历t行下的每一列 
		if(pos[i]||vis[t][i]||c[t][i]!='#')continue;//不满足条件继续 
		pos[i]=1;//这一列被遍历了就为1 
		vis[t][i]=1;	 
		dfs(t+1,m+1);//满足条件搜索下一行 
		pos[i]=0;
		vis[t][i]=0;
	}
	dfs(t+1,m);//如果当前行都不满足条件继续搜索下一行，这是有时候容易忽略的地方 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);//这两行就是使用cin，cout流时清空缓存，读写速度更快 
	while(cin>>n>>k){
		memset(c,0,sizeof(c));
		memset(vis,0,sizeof(vis));//两行都是初始化 
		if(n==-1&&k==-1)break;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>c[i][j];
			}
		}
		cnt=0,m=0;
		dfs(1,0);//第一行开始调用 
		cout<<cnt<<endl;
	}
	return 0;
}