费解的开关

你玩过“拉灯”游戏吗？

$25$ 盏灯排成一个 $5×5$ 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 $1$ 表示一盏开着的灯，用数字 $0$ 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 $6$ 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 $n$，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，则输出 $−1$。

数据范围

$0<n≤500$

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

解析

① 读完，对于一个开关，只有开或关两种状态可选，而且我们要的是最少的操作数，那么就说明 一个开关不会按第二下，因为按第二下就是撤销上一次的操作 那不如上一次就不按。

② 在操作确定的情况下，任意两个开关的按下顺序是可以互换的，证明：将所有的开关上标上该开关被影响的次数，我们发现无论开关的顺序如何 开关上的影响次数都是一样的。

③ 一个开关的状态改变会影响周围四个开关的状态，简化问题，如果开关只会影响上下的状态（左右的话将图横过来即同理），那么当前第 $k$ 排的最优解就是将第 $k-1$ 排的未打开的开关打开，因为第 $k + 1$ 排的开关会由 $k$ 排、$k +1$ 排、$k + 2$ 排所影响，而 $k-1$ 排此时却只能由 $k$ 排来影响自身的状态，同理，增加一个左右并不会改变这个决策的正确性，且这样做只会有唯一确定的操作（多种按法请看 ②）

但同样产生一个问题，起始排的状态应该如何确定？因为我们的决策是从第二排开始确定，而第一排的状态却无法确定，也许第一排的某一个或几个位置的状态改变会导致结果变得更优。观察数据，一排只有五个数，那就直接用 二进制枚举，$2^5$ 种情况全部枚举即可。

代码

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>

const int N = 505;
std::string c[N][6];
int a[N][6][6], m[N][6][6];
int n;

void effect(int n1, int x, int y) {
	if(m[n1][x][y] == 1) m[n1][x][y] = 0;
	else m[n1][x][y] = 1;  
	if(m[n1][x + 1][y] == 1) m[n1][x + 1][y] = 0;
	else m[n1][x + 1][y] = 1;
	if(m[n1][x - 1][y] == 1) m[n1][x - 1][y] = 0;
	else m[n1][x - 1][y] = 1;
	if(m[n1][x][y + 1] == 1) m[n1][x][y + 1] = 0;
	else m[n1][x][y + 1] = 1;
    if(m[n1][x][y - 1] == 1) m[n1][x][y - 1] = 0;
	else m[n1][x][y - 1] = 1;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 5; j++) {
			std::cin >> c[i][j];	
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 5; j++) {
			for (int k = 0; k < 5; k++) {
				a[i][j][k + 1] = c[i][j][k] - 48;	
				m[i][j][k + 1] = c[i][j][k] - 48;	
			}
		}
	}
	
	int tot = 0;
	for (int k = 1; k <= n; k++) {
		int ans = 0x3f;
		for (int f = 0; f < 1 << 5; f++) {
			tot = 0;
			for (int j = 0; j < 5; j++) {
				if(f >> j & 1) {
					tot++;
					effect(k, 1, j + 1);
				}
			}
			
			for (int i = 2; i <= 5; i++) {
				for (int j = 1; j <= 5; j++) {
					if(m[k][i - 1][j] == 0) {
						tot++;
						effect(k, i, j);
					}
				}
			}
			
			for (int i = 1; i <= 5; i++) {
				if(m[k][5][i] == 0) tot = 0x3f;
			}
			
			for (int i = 1; i <= 5; i++) {
				for (int j = 1; j <= 5; j++) {
					m[k][i][j] = a[k][i][j];
				}
			}
			
			ans = std::min(ans, tot);
		}
	
		if(ans > 6) puts("-1");
		else printf("%d\n", ans);
	} return 0;
}