鸿 网 互 联 www.68idc.cn

小游戏 Lights Out (关灯) 的求解 —— 异或方程组

来源:互联网 作者:佚名 时间:2015-10-15 14:50
Author : Evensgn Blog Link :http://www.cnblogs.com/JoeFan/ Article Link :http://www.cnblogs.com/JoeFan/p/4338003.html 游戏介绍 Lights Out (关灯)是一款据说在20世纪90年代就已经被设计出的小游戏,游戏的玩法十分简单。 首先,给定一个 n 行 m 列
Author : Evensgn Blog Link : http://www.cnblogs.com/JoeFan/Article Link : http://www.cnblogs.com/JoeFan/p/4338003.html 

游戏介绍

Lights Out (关灯)是一款据说在20世纪90年代就已经被设计出的小游戏,游戏的玩法十分简单。

首先,给定一个 n 行 m 列的矩形方格阵,每个格子上都有一盏灯。

初始时,有些灯是开着的,有些灯是关着的。

玩家每次进行一次操作,选中一盏灯,点击一下它,就会将它和与它相邻的灯的状态改变,即开着的灯变为关闭,关着的灯变为开启。

最后的目的是关闭所有的灯。

 

这里给出一个网页版的链接:关灯。

还有博客园一位博友DIY的一个类似的游戏,蓝色拼图。这个蓝色拼图与 Lights Out 实质上相同,只是初始状态固定了是所有的灯都是开启的。

 

Lights Out 的游戏规则就是这样简单,然而到了后面的几关,方格增多,情况复杂,人工找出解法对于我来说是十分困难的。

因此,我们考虑用程序求解这个游戏。

 

求解方法

首先我们要将这个游戏的过程转化为数学模型。

显然地,对于一个方格,会影响到它的方格只有它本身和与它相邻的 4 个方格(对于边界的方格来说,相邻的方格不足 4 个)。

并且很容易发现,每一个方格我们要么不点击,要么点击 1 次,因为点击一个方格两次及以上是没有任何意义的。每点击两次就相当于没有点击。

对于方格 i ,我们用 0 表示不点击它,用 1 表示点击它,记作 Si 。

每盏灯的状态只有开或者关,我们用 0 和 1 表示方格 i 状态,方格 i 的初始状态记为 Mi 。 

可以看出,每盏灯 i 的最终状态只与 Mi + Si + Sk1 + Sk2 + .... + Skp  (k1 ... kp 是枚举与 i 相邻的所有方格)的奇偶性有关。

既然只与奇偶性有关,我们就可以用异或运算来表示它。

也就是说,对于每盏灯 i ,我们都可以得到一个方程       Mi xor Si xor Sk1 xor Sk2 xor ... xor Skp = 0 。

等式右边的 0 表示最后每盏灯的状态都是关闭的。

这个方程其实也就等价于        Si xor Sk1 xor Sk2 xor ... xor Skp = Mi 。

我们得到了 Tot 个这样的方程(Tot 是灯的数量,即 Tot = n * m),共有 Tot 个未知数(即 Tot 个 Si),就是一个异或方程组。

由于游戏给定的初始状态一定有解,所以我们是一定可以求出这个异或方程组的一组解的。

 

那么下面的问题就是:怎样求解异或方程组?

显然,我们要使用高斯消元来求异或方程组的解。

这个过程与使用高斯消元求解普通的线性方程组相似(如果不了解高斯消元可以看一下Wikipedia-高斯消去法),只是每次在一个方程中消去一个未知数的时候,不是将这个方程乘上一个系数后与另一个方程相减,而是将这个方程的系数与另一个方程的系数进行异或运算,两个方程右边的数也要一起进行异或。

 

这样就可以求出 Lights Out 的解了。

 

代码如下,因为代码非常简单所以没有添加注释:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MaxL = 10 + 5, MaxN = 100 + 5;
const int Dx[5] = {0, 0, 1, -1}, Dy[5] = {1, -1, 0, 0};

int n, m, Tot;
int A[MaxN][MaxN], Map[MaxL][MaxL], Ans[MaxL][MaxL];

inline bool Inside(int x, int y) 
{
	if (x < 0 || x >= n) return false;
	if (y < 0 || y >= m) return false;
	return true;
}

inline int Get_Index(int x, int y)
{
	return x * m + y + 1;
}

struct Pos
{
	int x, y;
};

inline Pos Get_Pos(int Num) 
{
	Pos ret;
	ret.x = (Num - 1) / m;
	ret.y = ((Num % m - 1) + m) % m;
	return ret;
}

void Get_Equation(int x, int y) 
{
	int Id, Id2, xx, yy;
	Id = Get_Index(x, y);
	for (int i = 1; i <= Tot; ++i) A[Id][i] = 0;
	A[Id][Tot + 1] = Map[x][y];
	A[Id][Id] = 1;
	for (int k = 0; k < 4; ++k)
	{
		xx = x + Dx[k]; yy = y + Dy[k];
		if (!Inside(xx, yy)) continue;
		Id2 = Get_Index(xx, yy);
		A[Id][Id2] = 1;
	}
}

inline void Swap(int p, int q) 
{
	int Temp;
	for (int i = 1; i <= Tot + 1; ++i)
	{
		Temp = A[p][i];
		A[p][i] = A[q][i];
		A[q][i] = Temp;
	}
}

void Gauss() 
{
	int Tj;
	for (int i = 1; i <= Tot; ++i)
	{
		Tj = i;
		for (int j = i + 1; j <= Tot; ++j)
		{
			if (A[Tj][i] == 0 && A[j][i] == 1) 
			{
				Tj = j;
				break;
			}
		}
		if (A[Tj][i] == 0) continue;
		if (Tj != i) Swap(Tj, i);
		for (int j = i + 1; j <= Tot; ++j)
		{
			if (A[j][i] == 0) continue;
			for (int k = i; k <= Tot + 1; ++k)
				A[j][k] ^= A[i][k];
		}
	} 
	
	Pos Pi;
	for (int i = Tot; i >= 1; --i)
	{
		Pi = Get_Pos(i);
		Ans[Pi.x][Pi.y] = A[i][Tot + 1];
		for (int j = i - 1; j >= 1; --j)
			if (A[j][i]) A[j][Tot + 1] ^= A[i][Tot + 1];
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	Tot = n * m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%1d", &Map[i][j]);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			Get_Equation(i, j);
	Gauss();
	
	printf("Solution:\n");
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			printf("%d", Ans[i][j]);
		printf("\n");
	}
	return 0;
}

  

 

网友评论
<