2551683_ac_656ms_208k.cc

北大大牛代码 1240道题的原代码 超级权威

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

int m, n;
char map[8][8];
int pos[65][2];
int mark[65];
int no, ans;

int check(int j)
{
	int i;

	for(i = j-1; i >= 0; i--)
	{
		if(mark[i]&&(pos[i][0]==pos[j][0]||pos[i][1]==pos[j][1]))
			return 0;
	}
	return 1;
}

void dfs(int s,int num)
{
	int i;

	if(num==0)
	{
		ans++;
		return ;
	}
	for(i = s; i < no; i++)
	{
		mark[i] = 1;
		if(num==n||check(i))
			dfs(i+1,num-1);
		mark[i] = 0;
	}
}

void solve()
{
	int i, j;

	for(i = 0; i < m; i++)
		scanf("%s",map[i]);
	no = ans = 0;
	memset(mark,0,sizeof(mark));
	for(i = 0; i < m; i++)
		for(j = 0; j < m; j++)
			if(map[i][j]=='#')
			{
				pos[no][0] = i;
				pos[no][1] = j;
				no++;
			}
	if(no<n)
	{
		printf("0\n");
		return ;
	}
	dfs(0,n);
	printf("%d\n",ans);
}

int main()
{
	while(scanf("%d%d",&m,&n)==2&&m!=-1)
		solve();
	return 0;
}