题目链接：https://vjudge.net/problem/POJ-1321
题意：给一张棋盘，‘#’表示可以下棋的地方，‘.’表示不能下棋的地方。
棋盘是n*n的，要求能放下k个棋子，要求k个棋子在不同行不同列
思路：dfs，首先遍历地图找到第一个可以下棋的地方，然后从下一行开始继续dfs，如果已下棋子数等于要求棋子数，答案++
1 #include <iostream>
2 #include <string.h>
3 #include <algorithm>
4 using namespace std; 5
6 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
7 #define per(i,j,k) for(int i = (j); i >= (k); i--)
8
9 const int N = 15; 10 char mp[N][N]; 11 bool vis[N];//记录列是否下的情况，可以看看紫书上八皇后的讲解
12 int ans; 13 int n,k; 14
15 void input(){ 16
17 rep(i, 1, n){ 18 rep(j, 1, n) cin >> mp[i][j]; 19 } 20 } 21
22 void init(){ 23 memset(vis, 0, sizeof(vis)); 24 ans = 0; 25 } 26
27 void dfs(int cur,int chess){ 28
29 rep(i, cur, n){ 30 if (!(n - i >= k - chess)) continue;//如果剩余行数小于了剩余还要下的棋子数，说明 31 //棋子无法完全下完直接忽略
32
33 rep(j, 1, n){ 34
35 if (vis[j] || mp[i][j] == '.') continue;//在这个dfs分支中j列已经有棋子 36 //或者该空间无法下棋子
37
38 if (chess == k) { ans++; continue; } //棋子数满足了，ans++
39
40 vis[j] = true;//标记该dfs分支j列有棋子
41 dfs(i + 1,chess + 1); 42 vis[j] = false;//回溯
43 } 44 } 45 } 46
47
48 int main(){ 49
50 ios::sync_with_stdio(false); 51 cin.tie(0); 52
53 while (cin >> n >> k){ 54 if (n == -1 && k == -1) break; 55
56 init(); 57 input(); 58 dfs(1,1); 59
60 cout << ans << endl; 61 } 62
63
64 return 0; 65 }