2551450_ac_593ms_144k.cpp

北大大牛代码 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;

	scanf("%d%d",&m,&n);
	mark = 0;min = 100000;
	for(i = 0; i < m; i++)
	{
		for(j = 0; j < n; j++)
			scanf("%d",&map[i][j]);
	}
	enum_ans(0);
	if(!mark)
		printf("IMPOSSIBLE\n");
	else
	{
		for(i = 0; i < m; i++)
		{
			for(j = 0; j < n; j++)
				printf("%d ",res[i][j]);
			printf("\n");
		}
	}
	return 0;
}