puzzle（1312）黑白迭代、黑白无双_黑白迭代第四关

目录

一，黑白迭代

精选关卡

二，异形黑白迭代

1，本身+八邻居

2，本身+对角四邻居

三，黑白无双

四，六边形黑白迭代

1，对称局面

2*3*3模式

3*3*3模式

4*4*4模式

2，非对称局面

2*2*2模式

2*3*3模式

五，异形六边形黑白迭代

2*2*2模式

2*3*3模式

六，勤快的小蜜蜂

七，三角形黑白迭代

---

一，黑白迭代

黑白迭代是最强大脑同款项目，和点亮所有的灯规则一样。

精选关卡

（1）

  

二，异形黑白迭代

黑白迭代是改变5个格子，即本身加上下左右四邻居。

下面的例子来自苹果APP“翻转-统一颜色”，规则是全部同色即可，和限定一个颜色规则差不多，不展开讨论了。

1，本身+八邻居

3阶

4阶

2，本身+对角四邻居

这个就比较简单，因为按照奇偶性可以分开计算，而且分开后的网络稀疏，所以简单。

3阶

4阶

三，黑白无双

3D版黑白迭代，最强大脑同款项目。

把点亮所有的灯拓展到3维，思路是一样的，就是计算量变大了。

思路的核心是flushOpt：对于任意局面，不操作第0行，操作第1到y-1行，使得上面y-1行全部复原。

代码：

 
int x = 7, y = 7, z = 3;//x列y行z层
bool inBoard(int xi, int yi, int zi)
{
	if (xi < 0 || xi >= x)return false;
	if (yi < 0 || yi >= y)return false;
	if (zi < 0 || zi >= z)return false;
	return true;
}
void pointOpt(vector<vector<vector<int>>>& v, int xi, int yi, int zi)
{
	if (inBoard(xi, yi, zi))v[zi][yi][xi] ^= 1;
	if (inBoard(xi + 1, yi, zi))v[zi][yi][xi + 1] ^= 1;
	if (inBoard(xi - 1, yi, zi))v[zi][yi][xi - 1] ^= 1;
	if (inBoard(xi, yi + 1, zi))v[zi][yi + 1][xi] ^= 1;
	if (inBoard(xi, yi - 1, zi))v[zi][yi - 1][xi] ^= 1;
	if (inBoard(xi, yi, zi + 1))v[zi + 1][yi][xi] ^= 1;
	if (inBoard(xi, yi, zi - 1))v[zi - 1][yi][xi] ^= 1;
}
void lineOpt(vector<vector<vector<int>>>& v, int yi)//0<yi<y,点击第yi行使得上一行复原
{
	for (int zi = 0; zi < z; zi++) {
		for (int xi = 0; xi < x; xi++) {
			if (v[zi][yi - 1][xi])pointOpt(v, xi, yi, zi);
		}
	}
}
void flushOpt(vector<vector<vector<int>>>& v)//对于任意局面，不操作第0行，操作第1到y-1行，使得上面y-1行全部复原
{
	for (int yi = 1; yi < y; yi++)lineOpt(v, yi);
}
 
vector<vector<int>> facs()//得到边长为x*z的正方形0-1系数矩阵
{
	vector<vector<vector<int>>>v(x);
	for (auto& vz : v) {
		vz.resize(y);
		for (auto& vy : vz) {
			vy.resize(x);
			for (int xi = 0; xi < x; xi++)vy[xi] = 0;
		}
	}
	vector<vector<int>>ans(x*z);
	for (int zi = 0; zi < z; zi++) {
		for (int xi = 0; xi < x; xi++) {
			pointOpt(v, xi, 0, zi);
			flushOpt(v);
			for (int zi = 0; zi < z; zi++) {
				for (int xi = 0; xi < x; xi++)ans[zi * x + xi].push_back(v[zi][y - 1][xi]);
			}
			pointOpt(v, xi, 0, zi);
		}
	}
	return ans;
}
 
 
int main()
{
	vector<vector<int>>v = facs();
	int a;
	for (int zi = 0; zi < z; zi++) {
		for (int xi = 0; xi < x; xi++)cin >> a, v[zi * x + xi].push_back(a);
	}
	auto ans = GaussEliminationXor().getAns(v);
	for (auto x : ans)cout << x << " ";
	return 0;
}

其中解方程的函数来自高斯消元法

应用方法：

首先手动执行flushOpt，变成：

即0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1

运行程序，输入这些数字，输出：0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0

按照1的位置点击对应的格子：

再手动执行flushOpt即可复原。 

四，六边形黑白迭代

1，对称局面

最强大脑同款项目

按照其中的推论，其实只要找出任意一个对称解即可。

六边形黑白迭代相对于矩形来说，邻居更多，因此无法采用分层的模式进行确定性的递推分析。但是对于对称解，只需要先确定对称轴上的操作，再确定两边的对称操作即可。而对称轴上的操作，可以进行递推分析。

对称解法中，只有对称轴上的操作会改变对称轴上的格子状态，而这些格子之间的关系就和矩形中的一列的关系一样。所以其实最多就2种情况，即第一个格子要么点要么不点，其他的格子都可以依次推出来。

更具体的结论就是：

设n是对称轴上格子数量，即所有格子编号为1到n，

如果n%3=0或1，则有唯一解，第一个格子的点击数是$(S+C_{n-2}+C_{n-5}+...)%2$，其中C是对应格子的状态（1是需要改变0是不需要），S是所有格子状态和。

如果n%3=2，则有2种情况，都可以完成对称轴的复原。至于2种情况是不是都有最终解法，就不得而知了。

2*3*3模式

对于2*3*3模式，任意对称局面一定有对称解。

完成对称轴之后，只需要计算左边5个格子的点击次数。

假设5个格子需要改状态数分别是c1 c2 c3 c4 c5（取值0，1）

则1和2号格子需要的点击数分别是(c3+c4)%2、(c4+c5)%2，另外3个不需要记忆，只需要从上往下递推即可。

目标局面：

第一个格子的点击数是$(S+C_{n-2}+C_{n-5}+...)%2$ =（3+1）%2=0

于是往下递推完成对称轴：

左边的5个格子，3 4 5号需要的改变状态数分别是1 1 1，所以1 2号格子点击数分别是0 0

而3 4 5号格子的点击数也可以往下递推出来，是0 0 1

所以只把第5号格子点一下，右边对称一下，就变成了目标局面。 

3*3*3模式

完成对称轴有2种方式：

而这2个又都有对称解。 

4*4*4模式

2，非对称局面

如果开局不是对称局面，一般也很容易化成对称局面。

2*2*2模式

2*3*3模式

五，异形六边形黑白迭代

六边形黑白迭代的影响格子是本身+六邻居，异形是本身+三邻居。

这个玩法和黑白迭代大家族的绝大部分玩法有个关键的区别，绝大部分玩法是无向图，而这个玩法是有向图。比如上下2个格子AB，A在B的辐射范围，B不在A的辐射范围。

2*2*2模式

只需要一步就可以变成对称局面：

然后再寻找对称解就很简单。

2*3*3模式

 

六，勤快的小蜜蜂

在线play

规则：移动小蜜蜂，使得所有格子变成黄色。

其实相当于就是六边形黑白迭代的规则之上加了一条，初始局面需要的最小点击次数是已知的。

所以实际上这是简化的问题。

以第（4）关为例

这就相当于是：

把红圈里面的黑白迭代问题，以最少8次点击完成。

先把小区域完成，对于大区域，从外往里收缩就行。

七，三角形黑白迭代

三角形的比六边形的简单很多。