解题思路：混乱了几天，觉得是时候从新开始刷专题了。这题与八皇后问题区别就是k < n可以存在。
并不难的回溯题。见代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 10; 6 int vis[maxn], n, k, cnt; 7 char mapp[maxn][maxn]; 8 9 void dfs(int row, int num) 10 { 11 12 if(num == k) //当是k时，表示这种情况是符合条件的。 13 { 14 cnt ++; 15 return ; 16 } 17 if(row > n) return ; //当下一行越界时，直接退出。 18 19 for(int i = 1; i <= n; i++) 20 { 21 if(!vis[i] && mapp[row][i] == '#') 22 { 23 vis[i] = 1; //标记为已走过 24 dfs(row+1, num+1); //棋子数加1，行数到下一行 25 vis[i] = 0; //回溯之后这行再次标记为没走过 26 } 27 } 28 dfs(row+1, num); //这就是这题的最关键所在，表示当前行可以不放棋子，直接跳到下一行。 29 30 return ; 31 } 32 33 int main() 34 { 35 char ch; 36 while(~scanf("%d %d", &n, &k)) 37 { 38 if(n == -1 && k == -1) break; 39 memset(vis, 0, sizeof(vis)); //vis表示对应的列是否标记过，初始化为没走过。 40 for(int i = 1; i <= n; i++) 41 for(int j = 1; j <= n; j++) scanf(" %c", &mapp[i][j]); 42 43 cnt = 0; 44 dfs(1, 0); //第一行开始搜，0表示当前棋子数为0 45 46 printf("%d ", cnt); 47 } 48 return 0; 49 }