首页 > 代码库 > poj 1321 棋盘问题 【DFS】

poj 1321 棋盘问题 【DFS】

题意:。。。

策略:深搜.

仔细分析我们发现,我们只需要对列进行标记,对于行我们考虑放棋子还是不放就行了。

代码:

#include<stdio.h>
#include<string.h>
char s[10][10];
int n, m;
int vis[10];
int ans;
void dfs(int cur, int step)
{
	if(step == m){
		ans ++;
		return;
	}
	if(cur > n-1) return ;
	int i, j;
	for(i = cur; i < n; i ++){
		for(j = 0; j < n; j ++){
			if(s[i][j] == '#'&&!vis[j]){
				vis[j] = 1;
				dfs(i+1, step+1);//向下一行放置
				vis[j] = 0;
			}
		}
	}
}
int main()
{
	int i, j;
	while(scanf("%d%d", &n, &m), n!=-1&&m!=-1){
		for(i = 0; i < n; i ++){
			scanf("%s", s[i]);
		}
		memset(vis, 0, sizeof(vis));
		ans = 0;
		dfs(0, 0);
		printf("%d\n", ans);
	}
	return 0;
} 
题目链接:点击打开链接