学步园

本题就是枚举所有情况，然后一个个深搜，符合条件就跳出。。

但要有剪枝，不然会超时。

#include<stdio.h>
#include<string.h>
int s[4][4];
int m[4][4],flag,step;

int qq()
{
	int i,j;
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			if(m[i][j]!=m[0][0])
				return 0;
		}
	}
	return 1;
}

void yy(int r,int t)
{
	m[r][t]=!m[r][t];
	if(r<3)
		m[r+1][t]=!m[r+1][t];
	if(r>0)
		m[r-1][t]=!m[r-1][t];
	if(t>0)
		m[r][t-1]=!m[r][t-1];
	if(t<3)
		m[r][t+1]=!m[r][t+1];
}

//void show(int u,int g,int h)
{
	int i,j,d;
	if(u==step)
	{
		d=qq();
		if(d)
			flag=1;
		return ;
	}
	if(flag||g==4)
		return ;
	for(i=g;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			if(s[i][j]==0)
			{
			yy(i,j);
			s[i][j]=1;
			show(u+1,i,j);
			if(flag)
				return ;
			s[i][j]=0;
			yy(i,j);
			}
		}
	}

}（这是超时的搜索。）
void show(int u,int g,int h)
{
	int i,j,d;
	if(u==step)
	{
		d=qq();
		if(d)
			flag=1;
		return ;
	}
	if(flag||g==4)
		return ;
	yy(g,h);
	if(h<3)
		show(u+1,g,h+1);
	else
		show(u+1,g+1,0);
	yy(g,h);
	if(h<3)
		show(u,g,h+1);
	else
		show(u,g+1,0);
}

int main()
{

	int i,j;
	char a;
	memset(s,0,sizeof(s));
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			scanf("%c",&a);
			if(a=='b')
			{
				m[i][j]=0;
			}
			else
				m[i][j]=1;
		}
		getchar();
	}
	for(step=0;step<=16;step++)
	{
		flag=0;
		show(0,0,0);
		if(flag)
			break;
	}
	if(flag)
	   printf("%d\n",step);
	else
		printf("Impossible\n");
	return 0;
}