费解的开关
25盏灯排成一个 5×5的方形。
每一个灯都有一个开关,游戏者可以改变它的状态。
每一步,游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1表示一盏开着的灯,用数字 0 表示关着的灯。
输入格式
第一行输入正整数 n,代表数据中共有 n个待解决的游戏初始状态。
以下若干行数据分为 n组,每组数据有 5 行,每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n行数据,每行有一个小于等于 6的整数,它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态,若 6步以内无法使所有灯变亮,则输出 −1。
数据范围
0<n≤500
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdlib.h>
const int N = 6;//每个字符串后面还有个\0
char g[N][N], backup[N][N];
void turn(int x, int y) {
int dx[5] = {-1,1,0,0,0};
int dy[5] = {0,0,-1,+1,0};
for (int i = 0; i < 5; i++) {
int a = x + dx[i];
int b = y + dy[i];
if(a<0||a>=5||b<0||b>=5) continue; // 在边界外,直接忽略即可
backup[a][b] ^= 1;
}
return;
}
int main() {
int n;
scanf("%d", &n);//几组
int step=0;//记录步数
while (n--) {
for (int i = 0; i < 5; i++) {//输入每组
scanf("%d", &g[i]);
}
for (int i = 0; i < 32; i++) {//第一行全排列有32种,每一种有5位
memcpy(backup, g, sizeof g);//对g进行备份
for (int j = 0; j < 5; j++) {//按第一行
if ((i >> j & 1)==0) {//i >> j & 1 每一种全排列的第j位//0灭1开
step++;
turn(0, j);
}
}
for (int p = 0; p < 4; p++) {//前4行
for (int q = 0; q < 5; q++) {
if (backup[p][q] =='0' ) {
step++;
turn(p+1, q);
}
}
}
for (int i = 0; i < 5; i++) {
if (backup[4][i] == '0') { step = -1; break; }
}
}
if (step >= 6) step = -1;
printf("%d", step);
}
return 0;
}
正确答案
3
2
-1