1681.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#define NMAX 21
#define INF 1000000
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int minans;
char f[NMAX][NMAX];
int bit[26];
int sum[NMAX];
int p[NMAX];
int n;
int total;
char check[2000000];
void initbit()
{
	bit[1]=1;
	int i;
	for(i=2;i<=20;i++)
	{
		bit[i]=2*bit[i-1];
	}
}
void input()
{
	int i,j;
	scanf("%d",&n);
	char tmp[NMAX];
	for(i=1;i<=n;i++)
	{
		scanf("%s",tmp);
		f[i][0]='n';
		for(j=1;j<=n;j++)
		{
//			if(tmp[j-1]=='y')
//				sum[i]++;
			f[i][j]=tmp[j-1];
		}
	}

}
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int inv(int t)
{
	int tmp[NMAX],i;
	int ans;
	for(i=n;i>=1;i--)
	{
		tmp[i]=t%2;
		t=t/2;
	}
	ans=0;
	for(i=1;i<=n;i++)
	{
		ans+=tmp[i]*bit[i];
	}
	return ans;
}
void get(int t)
{
	for(int i=n;i>=1;i--)
	{
		p[i]=t%2;
		t=t/2;
	}
}
void init()
{
	int j,k;


	for(j=1;j<=n;j++)
	{
		if(p[j]==1)
		{
			total++;	
			for(k=max(1,j-1);k<=min(n,j+1);k++)
			{
				if(f[1][k]=='w')
					f[1][k]='y';
				else
					f[1][k]='w';
			}
			if(f[2][j]=='w')
				f[2][j]='y';
			else
				f[2][j]='w';
		}
	}
}
void solve()
{
	int i,t,j,k;
	minans=INF;
	int s;
	char tf[NMAX][NMAX];
	memcpy(tf,f,sizeof(f));
	if(n==1)
	{
		if(f[1][1]=='y')
			printf("0\n");
		else
			printf("1\n");
		return ;
	}
	for(t=0;t<bit[n+1];t++)
	{
		total=0;
		
//		if(check[t])
//			continue;
		memcpy(f,tf,sizeof(f));
//		check[t]=1;
//		check[inv(t)]=1;
		get(t);
		init();
		for(i=1;i<n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(total>=minans)
				{
					i=n;
					break;
				}
				if(f[i][j]=='w')
				{
					f[i][j]='y';
					total++;
					for(k=max(1,j-1);k<=min(n,j+1);k++)
					{
						if(f[i+1][k]=='w')
							f[i+1][k]='y';
						else
							f[i+1][k]='w';
					}
					if(f[i+2][j]=='w')
						f[i+2][j]='y';
					else
						f[i+2][j]='w';
				}
			}
		}
		s=0;
		for(j=1;j<=n;j++)
		{
			if(f[n][j]=='y')
				s++;
		}
		if(s<n)
			continue;
		if(total<minans)
			minans=total;
		if(minans==0)
			break;
	}
	if(minans==INF)
		printf("inf\n");
	else
		printf("%d\n",minans);
}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	
	initbit();
	int t;
	scanf("%d",&t);
	while(t--)
	{
	//	minans=INF;
		input();
		solve();
	}
#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}