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;
}

如有不当之处欢迎指出！

巴特西

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

最新文章

热门文章