学步园

题目大概意思 都是 给出一个n*m的0 1矩阵， 改变其中一个位置为(i,j)的点的状态 则该点 上下左右的状态同时改变；现给出一个矩阵 要你求出到达目标状态的

最小改变次数 或者 输出 需要按下的位置

 

思路：1.某个点被按下两次 则回到初始的状态 也就是每个点 最多只需要按一次 那总共不会超过n*m次；

            2.要使第一行的状态都为1 或0 只要把 第一行需改变的点下方的点按下； 同理 到最后一行，判断最后一行的状态是否都为1或0 ，若是则可以完成；

            第一行 按下的情况  有 2^m种，由上可知   枚举 第一行按下的情况 得到 新的状态 再按2操作，即可完成；

 1222 EXTENDED LIGHTS OUT

CODE：

#include <iostream>
#include <bitset>
using namespace std;
bool map[5][6],t[5][6],sum[5][6];
int r[5]={0,0,0,1,-1};
int c[5]={0,1,-1,0,0};
int Case=0;
void filp(int x, int y)
{
	for(int i=0; i<5; i++)
	{
		int xx = x+r[i];
		int yy = y+c[i];
		if(xx>=0&&xx<=4 && yy>=0&&yy<=5)
		{
			t[xx][yy]^=1;
		}
	}
}
bool cheak()
{
	for(int j=0; j<5; j++)
	for(int k=0; k<6; k++)
		if(t[j][k]) return false;
	return true;
}
void solve()
{
	int i,j,k,ans=20;
	for(i=0; i<64; i++)
	{
		bitset<6>bit(i);
		memset(sum, 0, sizeof(sum));
		memcpy(t,map,sizeof(t));
		for(j=0; j<6; j++)
		{
			if(bit[j]==1)
			{
				filp(0,j);
				sum[0][j]=1;
			}
		}
		for(j=1; j<5; j++)
		for(k=0; k<6; k++)
		if(t[j-1][k])
		{
			filp(j,k);
			sum[j][k]=1;
		}
		if(cheak()) break;
	}
	printf("PUZZLE #%d\n", ++Case);
	for(i=0; i<5; i++,printf("\n"))
	for(j=0; j<6; j++)
		printf("%d ",sum[i][j]);
}
int main()
{
	int i,j,t;
	scanf("%d", &t);
	while(t--)
	{
		for(i=0; i<5; i++)
		for(j=0; j<6; j++)
			scanf("%d", &map[i][j]);
		solve();
	}
	return 0;
}

1753  Flip Game

#include <iostream>
#include <bitset>
using namespace std;
bool map[4][4],t[4][4];
int r[5]={0,0,0,1,-1};
int c[5]={0,1,-1,0,0};
int Case=0;
void filp(int x, int y)
{
	for(int i=0; i<5; i++)
	{
		int xx = x+r[i];
		int yy = y+c[i];
		if(xx>=0&&xx<=3 && yy>=0&&yy<=3)
		{
			t[xx][yy]^=1;
		}
	}
}
bool cheak(bool f)
{
	for(int j=0; j<4; j++)
	for(int k=0; k<4; k++)
		if(t[j][k]!=f) return false;
	return true;
}
void solve()
{
	int i,j,k,ans=20,coun=0,count;
	for(i=0; i<16; i++)
	{
		bitset<4>bit(i);
		memcpy(t,map,sizeof(t));
		coun=0;
		for(j=0; j<4; j++)
		if(bit[j]==1)
		{
			filp(0,j);
			coun++;
		}
		count = coun;
		for(j=1; j<4; j++)
		for(k=0; k<4; k++)
		if(t[j-1][k])
		{
			filp(j,k);
			count++;
		}
		if(cheak(0) && ans>count) ans=count;

		memcpy(t,map,sizeof(t));
		coun=0;
		for(j=0; j<4; j++)
		if(bit[j]==1)
		{
			filp(0,j);
			coun++;
		}
		count = coun;
		for(j=1; j<4; j++)
		for(k=0; k<4; k++)
		if(!t[j-1][k])
		{
			filp(j,k);
			count++;
		}
		if(cheak(1) && ans>count) ans=count;
	}
	if(ans==20) printf("Impossible\n");
	else printf("%d\n",ans);
}
int main()
{
	int i,j;
	char ch;
	for(i=0; i<4; i++)
	{
		for(j=0; j<4; j++)
		{
			scanf("%c", &ch);
			map[i][j]=ch=='w'?1:0;
		}
		getchar();
	}
	solve();
	return 0;
}

两题都是一次AC ，但是调试的时候发现 输出答案错误， 发现 在枚举第一行按下情况、改变状态前 ，没有 将 原矩阵 复制到 临时矩阵里 ORZ。。。