原题链接
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
这个题非常经典，深搜的回溯，细细品尝，必有所获。
每次遇到合适的位置，立即钻进去，转而进入下一个深搜，直到棋子完全拜完，此深搜结束，回到上一个深搜状态，再进行恢复现场，恢复完后先到下一列，下一列可行又继续前面的状态，换列不能解决就换行，直到行数跑完，行数跑完则结束当前深搜，继续改变上一个深搜状态。“第一个”深搜以最后一行作为起点，才真正结束。
#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) {
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;
}
|
