wywwzjj's Blog.

POJ 1321 棋盘问题[DFS]

字数统计: 407阅读时长: 1 min
2018/10/28 Share

原题链接

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

这个题非常经典,深搜的回溯,细细品尝,必有所获。
每次遇到合适的位置,立即钻进去,转而进入下一个深搜,直到棋子完全拜完,此深搜结束,回到上一个深搜状态,再进行恢复现场,恢复完后先到下一列,下一列可行又继续前面的状态,换列不能解决就换行,直到行数跑完,行数跑完则结束当前深搜,继续改变上一个深搜状态。“第一个”深搜以最后一行作为起点,才真正结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
using namespace std;

#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b);++i)

char G[10][10];
bool fg[10] = {0}; // 走过为真
int ans = 0, n, k;

void dfs(int cur, int x) { // cur为已摆的棋子数, x 为行数
if(cur == k) {
ans++;
return;
}
rep(i, x, n)
rep(j, 0, n)
if(G[i][j] == '#' && !fg[j]) {
fg[j] = true;
dfs(cur+1, i+1); // 下一行继续摆下一个棋子
fg[j] = false;
}
}

int main() {
while(sf("%d%d", &n, &k) == 2 && n != -1 && k != -1) {
rep(i,0,n) sf("%s",G[i]);
dfs(0, 0); // 第一行开始摆
pf("%d\n", ans); ans = 0;
}
return 0;
}
CATALOG