// 算法思想：①将牌局映射到一维的只函0，1的数组，以便用取非运算模拟翻牌。②翻牌顺序不影响结果，可以每次都是从编号低的格子往编号高的格子翻。例如，当前考虑是否翻第5个格子时，之后就不用考虑前4个格子了。

#include "stdafx.h"
#include "stdio.h"
#define INF 999999999
char a[10][10];
int map[100];
int min_rounds = INF,flag;

int main()
{
	void flip_rounds(int x,int rounds);   //当前格局为a,选中a[i][j],那么实现目标最少需要翻多少轮
	int i, j, k;
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4; j++)
		{
            scanf_s("%c", &a[i][j], 1);
			k = 4 * i + j;  //转换为一维数组，以方便采用深搜和广搜策略处理。相应的一维数据的位置
			if (a[i][j] =='b')   //将b映射为0，w映射为1，以方便通过取非运算进行状态转换
				map[k] = 0;
			else
				map[k] = 1;
		}
	    // getchar();
	}
	flip_rounds(0, 0);
	if (min_rounds == INF)
		printf_s("Impossible\n");
	else
	    printf_s("%d\n", min_rounds);
    return 0;
}

void flip_rounds(int x,int rounds)   //因为翻牌顺序不影响结果，可以每次都是从编号低的格子往编号高的格子翻
{
	int judge();
	void flip(int x);
	flag = judge();
	if (x >= 16)
		return;
	if (flag == 1)
	{
		if (rounds < min_rounds)
		    min_rounds = rounds;
		return;
	}
	else
	{
		flip(x);  //翻转当前牌及其上下左右的牌
		rounds++;
		flip_rounds(x + 1,rounds); 
		flip(x);  //复原
		rounds--; 
        flip_rounds(x+1,rounds);
	}
}

int judge()   //判断是否已全部为黑面朝上，或全部为白面朝上
{
	int i;
	for (i = 1; i < 16; i++)
	{
		if (map[i] != map[0])
			return 0;
	}
	return 1;
}


void flip(int x)  //翻转a[i][j]及其上下左右棋子
{
	map[x] = !map[x];  //翻转[i][j]
	if (x - 4 >= 0)   //翻转上面的[i-1][j]
		map[x - 4] = !map[x - 4];
	if (x + 4 < 16)    //翻转下面的[i+1][j]
		map[x + 4] = !map[x + 4];
	if (x != 0 && x != 4 && x != 8 && x!=12)    //翻转左边的[i][j-1]
		map[x - 1] = !map[x - 1];
	if (x != 3 && x != 7 && x != 11 && x != 15)    //翻转右边的[i][j+1]
		map[x + 1] = !map[x + 1];
	return;
}

• 已经知道原因了，就是在flip_rounds()函数中应该先判断是否已到达目标状态，再判断是否有牌可翻 (0) ghh99best 2018-03-23 14:55:34