POJ 1753 Flip Game（枚举+递归）

传送门

思路是别人的，自己理解了半天，真是渣渣。对于自己，路还长，年轻人。

• 对任意一个格子来说，翻动偶数次等于没翻，翻动奇数次等于翻一次，所以只需考虑翻一次的情况。
• 一共16个格子，每个格子只有翻和不翻，所以最多16步，最少0步，题目要求最少的步数，所以0——>16枚举，看哪一步先成功就是最优解。
• 使用dfs，要考虑到树根时如果还没成功，要回溯；回溯时要把棋子再翻回来，再搜。 

#include<iostream>
#include<cstdio>
using namespace std;
bool chess[6][6]={false};
int step;
bool flag;
int r[5]={-1,1,0,0,0};//row up,down,left,right,o
int c[5]={0,0,-1,1,0};//col up,down,left,right,o
bool isOver()
{
	for(int i = 1;i <= 4; i++)
	{
		for(int j = 1;j <= 4;j++)
		{
			if(chess[i][j] != chess[1][1])
			{
				return false;
			}
		}
	}
	return true;
}
void flip(int row,int col)
{
	int i;
	for(i = 0;i < 5;i++)
	{
		chess[row + r[i]][col + c[i]] = !chess[row + r[i]][col + c[i]];
	}
}

void dfs(int row,int col,int deep)
{
	if(deep == step)
	{
		flag = isOver();
		return;
	}
	if(flag || row == 5)
		return;
	flip(row,col);
	if(col < 4)
		dfs(row,col+1,deep+1);
	else
		dfs(row+1,1,deep+1);
	flip(row,col);
	if(col < 4)
		dfs(row,col + 1,deep);
	else
		dfs(row + 1,1,deep);
	return;
}
int main()
{
	char temp;
	for(int i = 1;i <= 4; i++)
	{
		for(int j = 1;j <= 4; j++)
		{
			scanf("%c",&temp);
			if('b' == temp)
			{
				chess[i][j] = true;
			}
		}
		getchar();
	}
	for(step = 0;step <= 16; step++)
	{
		dfs(1,1,0);
		if(flag)
			break;
	}
	if(flag)
        printf("%d\n",step);
	else
		printf("Impossible\n");
	return 0;
}