点击打开链接

这道题的大致意思是：

        给你一个4*4的方格，上面只有'b'和'w',他们分别代表棋子的正面和反面。现在你对棋盘的操作有翻转

其中的一个棋子，但是同时会使得这个棋子上边，下边，左边，右边的棋子也会翻转。这个操作可以有多次。

问经过N次操作后棋盘上的棋子全为正面或反面（也就是全为'b'或全为'w'）,并使得N最小。


        分析一下解题思路，首先能想到的是对整个棋盘进行搜索，但是这样在最糟糕的情况下，需要进行4^16

次，很可能会超时。所以我们需要考虑到更优的方法。


        仔细读题就会发现翻转某个个棋子只能改变当前棋子，上下左右的棋子的状态。假设我们需要进行多次操

作使得棋盘全为'b',那么当我们翻转第j行的棋子，必须使的第j-1行的棋子全部变为'b',因为当我们翻转完第j行

的棋子后，就不能使得第j-1行的棋子发生改变(所以此时即使第j-1行的棋子有'w'，也不能让它翻转了)。


        经过以上分析，我们可以知道当第一行的棋子的翻转后，剩下的3行棋子如何翻转就确定，因为你翻转某

行的棋子，必须使得当前行的上一行的棋子达到目标状态。最后我们只需要检查最后一行的的棋子是否符合目

标状态就行了。


        程序的大致步骤就是写一个dfs,来搜索第一行翻转的状态。然后根据第一行的状态来推出最后一行的状态

，判断是否达到目标状态，在这个过程中应该用一个值来记录在这种情况下的翻转次数。并不断更新这个值，

使得这个值最小。

代码如下：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const int error = 999999999;			//用来表示达不到目标状态； 

int flip(int x, int y, int flag);		//flag==1表示在全为'b'的时候翻转，
									//flag==2时，表示在全为'w'时翻转；
									

int judge(int num, int flag);					//flag==1表示在判断棋盘是否全为'b',
									//flag==2表示是否全为'a';
									

int dfs(int index, int sum);		//深搜第一行的所有翻转状态，
								//sum表示第一行翻转的次数。


char data[6][6], data1[6][6], data2[6][6];	//data1表示在全为'b'的棋盘，data1表示在全为'w'的棋盘 

int vis[5] = {0};					//用来在深搜时表示第一行的翻转状态，1代表翻转，0代表不翻转。 

int dir[5][2] = {0,0,-1,0,0,-1,1,0,0,1};	//表示翻转的方向 

int result = error; 

/*
Sample Input

bwwb
bbwb
bwwb
bwww

bbbb
bbbb
bbbb
bbbb

bbbb
bbbb
bbbb
wwww

Sample Output

    4

*/
 
int main()							
{
	for(int i = 1; i <= 4; i++) 
	{
		for(int j =1; j <= 4; j++)
		cin>>data[i][j];
	}
	dfs(0,0);
	
	if(result == error)
	printf("Impossible\n");
	else
	printf("%d\n",result);
	
	
	
	return 0;
}

 int flip(int x, int y, int flag)
{
	if(flag == 1)
	{
		for(int i = 0;i < 5; i++)
		{
			int next_x = x + dir[i][0];
			
			int next_y = y + dir[i][1];
			
			if(data1[next_x][next_y] == 'b')
			data1[next_x][next_y] = 'w';
			else
			data1[next_x][next_y] = 'b';
		} 
	}
	else
	{
		for(int i = 0; i < 5; i++)
		{
			int next_x = x + dir[i][0];
			
			int next_y = y + dir[i][1];
			
			if(data2[next_x][next_y] == 'b')
			data2[next_x][next_y] = 'w';
			else
			data2[next_x][next_y] = 'b';
		} 
	}
	
}


int judge(int num, int flag)
{
	int step = num;
	
	if(flag == 1)
	{
		for(int i = 2; i <= 4; i++)
		{
			for(int j = 1; j <= 4; j++)
			{
				if(data1[i-1][j] != 'b')
				{
					flip(i, j, flag);
					
					step++;
				}
			}
		}
		for(int i = 1; i <= 4; i++)		//根据最后一行状态判断是否达到目标状态 
		if(data1[4][i] != 'b')
		return error;
		
		return step;
	}
	
	else if(flag == 2)
	{
		for(int i = 2; i <= 4; i++)
		{
			for(int j = 1; j <= 4; j++)
			{
				if(data2[i-1][j] != 'w')
				{
					flip(i, j, flag);
					
					step++;
				}
			}
		}
		for(int i = 1; i <= 4; i++)		//根据最后一行状态判断是否达到目标状态 
		if(data2[4][i] != 'w')
		return error;
		
		return step;
	}
	
}

int dfs(int index, int sum)
{
	if(index == 4)
	{
		memcpy(data1, data, sizeof(data1));
		
		for(int i = 1; i <= 4; i++)
		{
			if(vis[i] == 1)
			{
				flip(1,i,1);
			}
		}
		
		memcpy(data2, data1, sizeof(data1));
		
		int b =judge(sum, 1);
		
		int w = judge(sum, 2);
		
		result = min(result , min(b , w));
		
		return 0;
		
	}
	else
	{
		vis[index+1] = 0;
		dfs(index+1, sum);
		
		vis[index+1] = 1;
		dfs(index+1, sum+1);
	}
}