#include<iostream>
#include<cmath>
#include<bitset>
using namespace std;

#define N 4

int minCount = 100000;
int map[N][N];
int oldarr[N][N];

bool isFinish();

void output(int mapp[N][N]){
	int i,j;
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			cout<<mapp[i][j];
		}
		cout<<endl;
	}
}

void roll(int i){//i的范围0－15，转化为MAP中的位置
	int column,row,pianyi_x,pianyi_y;
    column = i % N;
	row = i / N;

	pianyi_x = row;
	pianyi_y = column ;
	if(pianyi_x>=0 && pianyi_x<N && pianyi_y>=0 && pianyi_y<N){
		map[pianyi_x][pianyi_y] = ~map[pianyi_x][pianyi_y]; //求反
	}


	pianyi_x = row - 1;
	pianyi_y = column ;
	if(pianyi_x>=0 && pianyi_x<N && pianyi_y>=0 && pianyi_y<N){
		map[pianyi_x][pianyi_y] = ~map[pianyi_x][pianyi_y];
	}

	pianyi_x = row + 1;
	pianyi_y = column;
	if(pianyi_x>=0 && pianyi_x<N && pianyi_y>=0 && pianyi_y<N){
		map[pianyi_x][pianyi_y] = ~map[pianyi_x][pianyi_y];
	}

    pianyi_x = row ;
	pianyi_y = column - 1;
	if(pianyi_x>=0 && pianyi_x<N && pianyi_y>=0 && pianyi_y<N){
		map[pianyi_x][pianyi_y] = ~map[pianyi_x][pianyi_y];
	}

    pianyi_x = row ;
	pianyi_y = column + 1;
	if(pianyi_x>=0 && pianyi_x<N && pianyi_y>=0 && pianyi_y<N){
		map[pianyi_x][pianyi_y] = ~map[pianyi_x][pianyi_y];
	}
}

bool isFinish(){  //判断是否已经成功
	int i,j;
	for(i=0; i<N; ++i){
		for(j=0; j<N; ++j){
			if( map[i][j]==0 ) return false;
		}
	}
	return true;
}




void work(){
	int i,cnt,k,jin;
    bitset<16> bs(0);
	while(bs!=65535){
		if(bs[0]==0) bs[0]=~bs[0];        //BS＝BS+1，穷举1－65535的状态
		else{
			k=0;
			bs[k] = 0;
			jin = 1;
			 while(jin==1){
				if(bs[++k]==1){
					bs[k] = 0;
				}else{
					bs[k] = 1;
					jin = 0;
				}
			}
		}
		memcpy(map,oldarr,16);
 		for(i=0; i<bs.size();i++){
			if(bs[i]==1) roll(i);  //如果这一位是1，就转换
		}
		if(isFinish()==true){
			cnt = (int) bs.count();  //有多少位是1，就转换了多少次
			if(cnt< minCount) minCount = cnt;
		}
	}
}

int main()
{
	int i,j;
	char aChar;
	for(i = 0;i < N ; i++ ){
		for(j = 0 ; j < N ; j++){
            cin>>aChar;
			if( aChar=='b'){
				oldarr[i][j] = -1;
			}
			else {
				oldarr[i][j] = 0;
			}
		}
	}
	memcpy(map,oldarr,16);
	if( isFinish()== true)
	    cout<<0<<endl;
	else{
		work();
		if(minCount!=100000) cout<<minCount<<endl;
		else cout<<"Impossible"<<endl;
	}
	system("pause");
	return 0;
}

• 对每个位置要么变化1次，要么不变。。。。 (0) whitesea 2008-09-05 11:35:35