4613100_wa.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
char inp;
bool input[4][4];
bool now[4][4];
//bool sdo[4][4];
int jdo[4][4];
int tmin=100;
int bu=0;
void press(int i,int j)
{
	now[i][j]=!now[i][j];
	if(i>0) now[i-1][j]=!now[i-1][j];
	if(i<3) now[i+1][j]=!now[i+1][j];
	if(j>0) now[i][j-1]=!now[i][j-1];
	if(j<3) now[i][j+1]=!now[i][j+1];
}
void copy()
{
	for(int count=0;count<4;count++)
	{
		for(int count1=0;count1<4;count1++)
		{
			now[count][count1]=input[count][count1];
		}
	}
}
void hang(int row,bool goal)
{
	switch(row)
	{
	case 0:
	{
	for(int count=0;count<=15;count++)
	{
		bu=0;
		copy();
		jdo[row][0]=count/8;if(jdo[row][0]==1) {press(row,0);bu++;}
		jdo[row][1]=count%8/4;if(jdo[row][1]==1) {press(row,1);bu++;}
		jdo[row][2]=count%4/2;if(jdo[row][2]==1) {press(row,2);bu++;}
		jdo[row][3]=count%2;if(jdo[row][3]==1) {press(row,3);bu++;}
		hang(row+1,goal);
	}
	break;
	}
	case 1:
	case 2:
	case 3:
		{
			if(now[row-1][0]!=goal) {jdo[row][0]=1;press(row,0);bu++;}
			else {jdo[row][0]=0;}
			if(now[row-1][1]!=goal) {jdo[row][1]=1;press(row,1);bu++;}
			else {jdo[row][1]=0;}
			if(now[row-1][2]!=goal) {jdo[row][2]=1;press(row,2);bu++;}
			else {jdo[row][2]=0;}
			if(now[row-1][3]!=goal) {jdo[row][3]=1;press(row,3);bu++;}
			else {jdo[row][3]=0;}
			if(row!=3)hang(row+1,goal);
			else
			{
				if(now[3][0]==goal&&
					now[3][1]==goal&&
					now[3][2]==goal&&
					now[3][3]==goal
					)
				{
					tmin=bu<tmin?bu:tmin;
				}
			}
		}
	}
}
void slove(bool goal)
{
	hang(0,goal);
}
int main()
{
	//int first==0;
	do
	{
	//	first++;
	tmin=100;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>inp;
			if(inp=='b') input[i][j]=true;
			else input[i][j]=false;
		}
	}
	slove(true);
	slove(false);
	if(tmin!=100)cout<<tmin<<endl;
	else cout<<"Impossible"<<endl;
	//if(first!=1) cout<<endl;
	}
	while(getchar()!=EOF);
	return 0;
}