题意：在一个n*n的棋盘上放k个棋子（任意两个棋子不同行不同列）有几种放法。(n <= 8, k <= n)
题目链接：http://poj.org/problem?id=1321
——>>和八皇后问题很像，只是这里不用每行都有，简单回溯。
时间复杂度 O(4^n)
#include <cstdio>
#include <cstring>const int MAXN = 8 + 10;int n;
int k;
int C;
char G[MAXN][MAXN];
bool vis[MAXN];void Dfs(int curRow, int curCnt)
{if (curCnt == k){++C;return;}if (curRow == n) return;for (int i = 0; i < n; ++i){if (G[curRow][i] == '#' && vis[i] == false){vis[i] = true;Dfs(curRow + 1, curCnt + 1);vis[i] = false;}}Dfs(curRow + 1, curCnt);
}void Read()
{for (int i = 0; i < n; ++i){getchar();for (int j = 0; j < n; ++j){G[i][j] = getchar();}}
}void Solve()
{C = 0;memset(vis, 0, sizeof(vis));Dfs(0, 0);
}void Output()
{printf("%d\n", C);
}int main()
{// freopen("poj_1321.in", "r", stdin);while (scanf("%d%d", &n, &k) == 2){if (n == -1 && k == -1) break;Read();Solve();Output();}return 0;
}old code：
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 10;
int cnt, n, k;
char MAP[maxn][maxn];
bool vis[maxn];void dfs(int x, int cur)
{if(cur == k){cnt++;return;}else{for(int i = x; i < n; i++)for(int j = 0; j < n; j++)if(MAP[i][j] == '#' && !vis[j]){vis[j] = 1;dfs(i+1, cur+1);vis[j] = 0;}}
}int main()
{int i, j;while(scanf("%d%d", &n, &k) == 2){if(n == -1 && k == -1) return 0;for(i = 0; i < n; i++){getchar();for(j = 0; j < n; j++)MAP[i][j] = getchar();}cnt = 0;memset(vis, 0, sizeof(vis));dfs(0, 0);printf("%d\n", cnt);}return 0;
}