题目链接：http://poj.org/problem?id=1321
题意：中文题目，就不多说了。。。。。。
思路：
解题方法挺多，刚开始想的是先从N行中选择出来含有“#”的K行，再在这K行中放置K个棋子，就好了。时间复杂度为O( C(n, k) * k! ),真实写的时候其实用了2 * k!,勉强也过了。后面又想到可以先从第一个出现的“#”开始搜，搜完之后直接跳到下一行继续,就不用第一次做那么麻烦了。
代码：
（1）
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string> typedef long long LL;
using namespace std;
const int MAXN = ;
int map[MAXN + ][MAXN + ];
int row[MAXN + ];
int chose[MAXN + ];
int n, k;
int ans; void chessDFS(int t) {
if(t > k) {
++ans;
}
else {
int cnt = ;
for(int i = ; i <= n; i++) {//从1 ～ n 行找到放置第t个棋子所在的行。
if(chose[i]) ++cnt;
if(cnt == t && chose[i]) {
for(int j = ; j <= n; j++) {//在该行寻找“#”
if(map[i][j] == '#' && row[j] == ) {
chose[i] = j; // 第t个棋子放在第 i行的第j个位置
row[j] = ;
chessDFS(t + );
row[j] = ;
}
}
}
}
}
} int check(int k) {
for(int i = ; i <= n; i++) {
if(map[k][i] == '#' && chose[k]) return ;
}
return ;
} void LineDFS(int t){
if(t > n){
int cnt = ;
for(int i = ; i <= n; i++) {
if(check(i)) cnt++;//判断chose数组中 1 的个数， 同时判断被选中行是否含有“#”，同时满足才算正真的选中
}
if(cnt == k) {//说明有K行被选中，且符合条件
memset(row, , sizeof(row));
chessDFS();//在这已经被选中的K行中放置K个棋子
}
}
else {
for(int i = ; i < ; i++) {//每行有两种状态，选和不选
chose[t] = i; //chose[t] = 1代表第t行被选则
LineDFS(t + );
}
}
} int main() {
while(scanf("%d%d", &n, &k) == && (n != - && k != -)) {
memset(map, '!', sizeof(map));
memset(row, , sizeof(row));
for(int i = ; i <= n; i++) {
getchar();
for(int j = ; j <= n; j++) {
map[i][j] = getchar();
}
}
ans = ;
LineDFS();//从N行中选择出来K行
printf("%d\n", ans);
}
return ;
}
(2)
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string> typedef long long LL;
using namespace std;
const int MAXN = ;
int map[MAXN + ][MAXN + ];
int row[MAXN + ];
int chose[MAXN + ];
int n, k;
int ans; void DFS(int t, int line) {
for(int i = ; i <= n; i++) {
if(map[line][i] == '#' && !row[i]) {
row[i] = ;
if(t == k) ++ans;
else {
for(int j = line + ; j <= n - (k - t) + ; j++) {//第t+1个点从line+1行开始放
DFS(t + , j);
}
}
row[i] = ;
}
}
} int main() {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
while(scanf("%d%d", &n, &k) == && (n != - && k != -)) {
memset(map, '!', sizeof(map));
memset(row, , sizeof(row));
for(int i = ; i <= n; i++) {
getchar();
for(int j = ; j <= n; j++) {
map[i][j] = getchar();
}
}
ans = ;
for(int i = ; i <= n - k + ; i++) DFS(, i);//第一个点从第一行开始放
printf("%d\n", ans);
}
return ;
}