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

#define N 4

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

bool isFinish();

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

void roll(int i){
	int column,row,pianyi_x,pianyi_y;
    column = i % N;
	row = i / N;
//	system("pause");
//	printf("(%d,%d)\n",row, column);
//	cout<<"("<<i<<")"<<endl;
	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];
	}
		
//	output();
}
	
int changeOne(int start,int cnt){
	int i,column,row,pianyi_x,pianyi_y;
	for(i=start; i< N*N; i++){
		roll(i);
		cnt++;
		if(isFinish()==true){
			if(minCount>cnt) minCount = cnt;
		}
		else{
			cnt = changeOne(i+1,cnt);
		}
		roll(i);
		cnt--;
 	}
	return cnt;
}
	
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;
}

int main()
{
	int i,j;
	char aChar;
	for(i = 0;i < N ; i++ ){
		
		for(j = 0 ; j < N ; j++){
            cin>>aChar;
			if( aChar=='b'){
				map[i][j] = -1;
			}
			else {
				map[i][j] = 0;
			}
		}
	}//input over
//	output();
	if( isFinish()== true)
	    printf("0\n");
	else{
//		cout<<changeOne(0,0)<<endl;
		changeOne(0,0);
		if(minCount!=100000) printf("%d",minCount);
		else printf("Impossible");
	}
	system("pause");
	return 0;
}

• Re:搜索也没过，哪位有数据吗 (2416) tedious 2008-09-05 10:57:00
• 直接枚举就可以了吧。。。。 (0) whitesea 2008-09-05 11:34:04