2676303_ac_203ms_172k.cc

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

#include <stdio.h>

int m, n, mark, min;
int map[16][16];
int ans[16][16];
int tmp[16][16];
int res[16][16];

int solve()
{
	int i, j, tot;

	for(i = 0; i < m; i++)
		for(j = 0; j < n; j++)
			tmp[i][j] = map[i][j];
	for(i = 0; i < n; i++)
	{
		if(ans[0][i])
		{
			tmp[0][i] = !tmp[0][i];
			if(i)
				tmp[0][i-1] = !tmp[0][i-1];
			if(i<n-1)
				tmp[0][i+1] = !tmp[0][i+1];
			if(m>1)
				tmp[1][i] = !tmp[1][i];
		}
	}
	for(i = 1; i < m; i++)
		for(j = 0; j < n; j++)
			ans[i][j] = 0;
	for(i = 1; i  < m; i++)
	{
		for(j = 0; j < n; j++)
			if(tmp[i-1][j])
			{
				ans[i][j] = 1;
				tmp[i][j] = !tmp[i][j];
				tmp[i-1][j] = 0;
				if(j)
					tmp[i][j-1] = !tmp[i][j-1];
				if(j<n-1)
					tmp[i][j+1] = !tmp[i][j+1];
				if(i<m-1)
					tmp[i+1][j] = !tmp[i+1][j];
			}
	}
	for(i = 0; i < n; i++)
		if(tmp[m-1][i])
			return 0;
	tot = 0;
	for(i = 0; i < m; i++)
		for(j = 0; j < n; j++)
			tot += ans[i][j];
	return tot;
}

void enum_ans(int j)
{
	int i, t;

	if(j==n)
	{
		if((t=solve())&&t<min)
		{
			min = t;
			for(i = 0; i < m; i++)
			{
				for(j = 0; j < n; j++)
					res[i][j] = ans[i][j];
			}
			mark = 1;
			return ;
		}
		return ;
	}
	for(i = 0; i < 2; i++)
	{
		ans[0][j] = i;
		enum_ans(j+1);
	}
}

int main()
{
	int i, j, t;
	int flag;
	char ch;

	scanf("%d",&t);
	getchar();
	while(t--)
	{
		scanf("%d",&m);
		getchar();
		n = m;
		flag = 1;
		mark = 0;min = 100000;
		for(i = 0; i < m; i++)
		{
			for(j = 0; j < n; j++)
			{
				scanf("%c",&ch),map[i][j] = (ch=='y'?0:1);
				if(map[i][j]==1)
					flag = 0;
			}
			getchar();
		}
		if(flag)
		{
			printf("0\n");
			continue;
		}
		enum_ans(0);
		if(!mark)
			printf("inf\n");
		else
			printf("%d\n",min);
	}
	return 0;
}