3007351_tle.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 107 行

#include <stdio.h>

int press[17];
int ans = 17;
char str[5][5];

int valid(int x,int y)
{
	if(x < 0 || y < 0 || x > 3 || y > 3)
		return 0;
	return 1;
}

void flip(int num)
{
	int i, j;
	int x, y;
	int w, b;
	char map[4][5];
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0},{0,0}};

	w = b = 0;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			map[i][j] = str[i][j];
		}
		map[i][j] = '\0';
	}
	for(i = 0; i < 16; i++)
	{
		if(!press[i])
		{
			continue;
		}
		x = i/4;
		y = i%4;
		for(j = 0; j < 5; j++)
		{
			if(valid(x+mov[j][0],y+mov[j][1]))
			{
				if(map[x+mov[j][0]][y+mov[j][1]]=='w')
				{
					map[x+mov[j][0]][y+mov[j][1]] = 'b';
				}
				else
				{
					map[x+mov[j][0]][y+mov[j][1]] = 'w';
				}
			}
		}
	}
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			if(map[i][j] == 'w')
			{
				w = 1;
			}
			else
			{
				b = 1;
			}
			if(w&&b)
				return ;
		}
	}
	if(num < ans)
	{
		ans = num;
	}
}

void enumerate(int p,int num)
{
	int i;
	
	if(p == 16)
	{
		flip(num);
		return ;
	}
	for(i = 0; i < 2; i++)
	{
		press[p] = i;
		enumerate(p+1,num+i);
	}
}

int main()
{
	int i;
		
	for(i = 0; i < 4; i++)
	{
		scanf("%s",str[i]);
	}
	enumerate(0,0);
	if(ans!=17)
		printf("%d",ans);
	else
		puts("Impossible");
	return 0;
}