学步园

哎哎..对自己还是蛮失望...刚开始看这个题目知道用dfs ....但是就是不知道怎么处理...纠结了好久，最开始用一个for 循环老得不出正确答案...因为这个dfs有事递归调用...都不知道错在哪里....好久之后在看...这里想到了用一个两重循环去判断....第一，我们需要对于棋盘中的每一个位置考虑，第二因为我们要对当前的一个位置考虑在这个位置开始填写第一个....我们是不是能在其他的位置填写处题目要求的个数.....那么就想到在dfs中用到双层for....确实很暴力...菜鸟的我也只能想到这里

注意：这里我们用到对于第一个for每层考虑 第二个for从第一列开始,,,这里我们只要设一个flag[9]一维数组查看每列是否填写过....因为逐行就不用考虑行了....

上马：

#include<stdio.h>
#include<string.h>

int n,k;
int ans;//最后答案
char map[9][9];
bool flag[9];//标记列的访问

void Input()
{
	for(int i=0;i<n;i++)
		scanf("%s",map[i]);
}

void dfs(int cnt,int step)
{
	if(step==k)
	{
           ans++;return;	
	}
	for(int i=cnt;i<n;i++)
		for(int j=0;j<n;j++)
			if(map[i][j]=='#' && !flag[j])
			{
				flag[j]=true;//对于j这列标记...
				map[i][j]='*';
				dfs(i+1,step+1);
				map[i][j]='#';
				flag[j]=false;
			}
}

int main()
{
	while(scanf("%d%d",&n,&k))
	{
		if(n==-1&&k==-1)
			break;
		memset(flag,false,sizeof(flag));
		ans=0;
		Input();
		dfs(0,0);
		printf("%d\n",ans);
	}
	return 0;
}

个人愚昧观点...欢迎指正与讨论