poj1753：Flip Game

传送门

题目大意

Flip Game是在一个4×4的矩形棋盘上进行的游戏，16个方格中的每一个方格上都放置了有两面的棋子。每块棋子的一面是白色的，另一面是黑色的。每一轮你都要翻转3到5个棋子，从而将其上边的颜色从黑色变为白色，反之亦然。每轮要翻转的棋子按照以下规则选择。
1、在16枚棋子中任选一枚。
2、将所选棋子和所有相邻棋子向左、向右、向上、向下翻转（如果有的话）。
游戏的目标是翻转所有棋子白面朝上或所有棋子黑面朝上。你要写一个程序，寻找实现这个目标所需的最少回合数。

思路

一个棋子有且仅有两个状态，非黑即白。所以，对同一颗棋子而言，翻动偶数次显然是没有意义的，只有奇数次的翻动才会改变棋子状态，所以只用考虑第一次翻面操作。一共十六个格子，最多16步就能全部翻完，所以从0~16枚举每个操作，只要某一次成功了，这次的步数就是最优的。

用dfs来翻，如果到叶子节点还没成功就回溯。需要注意的是回溯需要把之前翻过的所有棋子翻回来。

代码

#include <cstdio>
#include <iostream>

using namespace std;

int ans;
bool flag;
bool mp[5][5] = {0};
//方向数组:
//左、右、下、上、中
const int dx[5] = {-1, 1, 0, 0, 0};
const int dy[5] = {0, 0, -1, 1, 0};

bool isOver() {
	bool flag = mp[1][1];

	for(int i = 1; i < 5; i++)
		for(int j = 1; j < 5; j++)
			if(mp[i][j] != flag) 
				return false;
	
	return true;
}

void flip(int x, int y) {
	for(int i = 0; i < 5; i++) {
		mp[x + dx[i]][y + dy[i]] = !(mp[x + dx[i]][y + dy[i]]);
	}
}

void dfs(int x, int y, int cur, int step) {
	if(cur == step) {
		flag = isOver();
		return;
	}
	if(flag || x == 5) return;

	//翻面
	flip(x, y);
	if(y < 4)
		dfs(x, y + 1, cur + 1, step);
	else
		dfs(x + 1, 1, cur + 1, step);

	//回溯，翻回来
	flip(x, y);
	if(y < 4)
		dfs(x, y + 1, cur, step);
	else
		dfs(x + 1, 1, cur, step);

	return;
}

int main() {
	char tmp;
	for(int i = 1; i < 5; i++) {
		for(int j = 1; j < 5; j++) {
			cin >> tmp;
			if(tmp == 'b')
				mp[i][j] = 1;
		}
	}

	for(int step = 0; step <= 16; step++) {
		dfs(1, 1, 0, step);
		if(flag) {
			ans = step;
			break;
		}
	}

	flag ? cout << ans : cout << "Impossible";
	return 0;
}