問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1321思路:
深度優(yōu)先搜索
有點(diǎn)類似于八皇后問題，不過要注意這里k<=n，也就是說: 某些行是可以不放置棋子的
不過，該題還可以利用位運(yùn)算進(jìn)行優(yōu)化...
代碼:
1 char chessboard[MAX_LEN][MAX_LEN];
2 int record[MAX_LEN];
3 int n, k;
4 int total;
5
6 int
7 is_valid(int i, int depth)
8 {
9 int j;
10 for(j=0; j<depth; j++)
11 if(record[j] == i)
12 return 0;
13 return 1;
14 }
15
16 void
17 dfs(int depth, int cur)
18 {
19 int i, j;
20 if(depth == n) {
21 if(cur == k)
22 ++total;
23 return;
24 }
25 if(cur+(n-depth) < k) /* pruning */
26 return;
27 for(i=0; i<n; i++) {
28 if(chessboard[depth][i]=='#' && is_valid(i, depth)) {
29 record[depth] = i;
30 dfs(depth+1, cur+1);
31 record[depth] = -1;
32 }
33 }
34 dfs(depth+1, cur);
35 }