题意：
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1#..#4 4...#..#..#..#...-1 -1
Sample Output
21
思路分析：
DFS方法。
1、从第一个棋子开始放，能放的棋子必须满足条件：在棋盘区域&&这个位置没被放过，按照这个条件把棋子依次放下去，每放一颗棋子记得：
（1）标记这个位置
（2）已放棋子数要加加
2、一旦遇到放不下去的棋子，就回溯到上一个棋子。此时：
（1）撤销上次被标记的位置
（2）已放棋子数要减减
3、判断越界是否可以结束。越界条件：
（1）已放棋子数=要求放的棋子数
（2）棋子数超过了棋盘区域
源代码：
1 #include2 #include 3 #include 4 using namespace std; 5 char chess[12][12]; 6 int vis[12]; 7 int n,k,sum,ans; 8 void dfs(int a) 9 {10 11 if (ans == k) //已放棋子数=给定的棋子数12 {13 sum++;14 return;15 }16 if (a >= n) //棋子数超过棋盘区域17 return;18 19 for (int j = 0; j < n; j++)20 {21 if (chess[a][j] == '#'&&!vis[j])22 {23 vis[j] = 1; //标记位置已被放过24 ans++; //已放棋子数加加25 dfs(a + 1); //放下一个棋子26 vis[j] = 0; //撤销标记，递归失败27 ans--; //已放棋子数减减28 }29 30 }31 dfs(a + 1); //放第二行棋子32 }33 int main()34 {35 while (cin >> n >> k)36 {37 sum = 0; //方案数38 ans = 0; //已放棋子数39 getchar();40 if (n == -1 && k == -1)41 break;42 memset(chess, 0, sizeof(chess));43 memset(vis, 0, sizeof(vis));44 for (int i = 0; i < n; i++)45 {46 for (int j = 0; j < n; j++)47 cin >> chess[i][j];48 getchar();49 }50 dfs(0);51 cout << sum << endl;52 }53 54 return 0;55 56 }
心得：
本题跟八皇后的问题相似，都是DFS，回溯，但是有些细节不一样，比如越界条件。第二次遇到这种题目还是有些恍惚，可能是没有理解透吧。。。。。↖(^ω^)↗加油