POJ – 1321 dfs [kuangbin带你飞]专题一

枚举行和列即可，当前已经放下cnt个棋子，当前已经搜索到第r行，如果 n – r + cnt  < k 直接退出，因为后面无法放下剩下的棋子。

AC代码

#include<cstdio>#include<cstring>const int maxn = 10;char G[maxn][maxn];int vis[maxn], n, k;int ans;void dfs(int x, int cnt){if(cnt == k){ans++;return;}for(int i = x; i < n; ++i){if(n - x + cnt < k) return;for(int j = 0; j < n; ++j){if(vis[j] || G[i][j] == '.') continue;vis[j] = 1;dfs(i + 1, cnt + 1);vis[j] = 0;}}}int main(){while(scanf("%d%d", &n, &k) == 2 ){if(n == -1 && k == -1) break;for(int i = 0; i < n; ++i){scanf("%s", G[i]);}memset(vis, 0, sizeof(vis));ans = 0;dfs(0, 0);printf("%d\n", ans);}return 0;}

如有不当之处欢迎指出！