黑白棋题解_小l和小m在下棋。这张棋盘是n×m的。每一个格子要么是黑色的,要么是白色的。两个

棋盘由 n×m 个方格组成，每个方格上放置一枚棋子，每一枚棋子一面为黑，一面为白。若翻转某枚棋子，它的颜色就会由黑变白，或者由白变黑。一开始，棋子可能是黑色的，也可能是白色的。如果把所有的格子都翻成白色，游戏就结束了。

小爱可以按照任意顺序翻转任意数量的棋子，但游戏规则规定，选择翻动某一枚棋子时，与这个棋子的方格共享边界的其它棋子也必须被同时被翻转。小爱可能在一个步骤中，同时翻转五个棋子（棋子在中间）、四个棋子（棋子在边界上）或三个棋子（当棋子在角上）。

请帮助小爱计算一下，她最少需要多少步骤才能把所有棋子都翻成白色？如果给定的初始局面是不可能结束游戏的，输出 Impossible。

数据：

还可以，明显是的复杂度

Solution 失败：

因为不可能一个棋子上翻两次，所以可以用dfs，但是时间是,明显超时

AC Solution:

那20的数据，贪心不可能，dp不好转移，那什么办呢？

注意：要利用好这个20

那我们用遍历好第一排

那就必须用O(1)的时间确定我们翻不翻

我们用a[][]来记录原来的情况

再用b[i][j]记录(i,j)是否翻

举个栗子，a[][]数组如下，b[][]第一行枚举的

确定b[2][1]:

        我们看(1,1)因为翻过一次，变成0，那么b[2][1]=0，不然(1,1)就变为1了

确定b[2][2]:

        (1,2)翻了一次（b[1][1]=1），变为1，所以b[2][2]=1，不然(1,2)就为1了

......

完工了怎么判断是否对呢？

 因为都是“被迫选择的”，都会被“挽救”，只有(n,j)没有被“挽救”，所以只看(n,j)是否结果=0就行

复杂度：

解释一下：：枚举第一行

                   nm：确定b[][]

算了一下：4亿，用一个O2优化就AC了！

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool a[21][21], b[21][21];
signed main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) cin >> a[i][j];
	for (int i = 0; i < pow(2, m); ++i) {
		memset(b, 0, sizeof b);
		for (int j = 1; j <= m; ++j)
			b[1][j] = (i >> (j - 1)) & 1;
		for (int j = 2; j <= n; ++j)
			for (int k = 1; k <= m; ++k)
				if (a[j - 1][k]^b[j - 2][k]^b[j - 1][k - 1]^b[j - 1][k + 1]^b[j - 1][k]) b[j][k] = 1;
 
		bool f = 1;
		for (int j = 1; j <= m; ++j)
			if (a[n][j]^b[n][j - 1]^b[n][j + 1]^b[n - 1][j]^b[n][j]) {
				f = 0;
				break;
			}
		if (!f) continue;
		int sum = 0;
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= m; ++k) sum += b[j][k];
		cout << sum;
		return 0;
	}
	cout << "Impossible";
	return 0;
}