费解的开关

费解的开关

你玩过“拉灯”游戏吗？

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
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111

输出样例：

3
2
-1

解析：

观察这个题目首先可以把他当作一个典型的01图标问题，解决这种问题我们一般使用dfs深度遍历搜索

在这里先使用递归来解题，感兴趣的同学可以把他翻译成遍历。

针对于题目给的数组，先把他化成图，

10111
01101
10111
10000
11011

我们可以试着玩游戏一样把他全点亮，该怎么做呐？

首先在第一行不变的前提下（因为要保护第一行，如果直接动第一行会造成无限的死循环，前后的操作会彼此影响，导致不断重复）

我们操作第二行，点击第二行的第一个

第一行就解脱了，这时我们专注于操作第二行就可以了，同理在保护第二行的前提下，所以我们只能操作第三行。

打开（1，2）这个开关

为了点亮（2，2）所以点击（2，3）

为了点亮（4，2）关闭开关（4，3）

至此前两行操作完成，点击（1，4）

依次点击（2，4），（3，4），（5，4）得到

操作最后一行得到：

很显然这种状态无法完成。

因为我们对下面的每一行的操作有大量的重复工作，比如说在保护第二行的基础上对第三行进行操作，以此类推，我们完全可以把它封装成一个函数来实现。

int check(int cnt)//这里的cnt其实是我们传入的k(已经执行的操作数)
{int sum=cnt;for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)b[i][j]=a[i][j];//复制出一个可操作数组for(int i=1;i<=4;i++)//不对最后一行进行操作，因为最后一行不能在通过保护最后一行来操作下一行来实现了。{for(int j=1;j<=5;j++){if(!b[i][j])//找到熄灭的灯{sum++;b[i][j]=!b[i][j];//把目标开关下面的开关点亮，再把它四周的开关取反b[i+1][j]=!b[i+1][j];b[i+1][j-1]=!b[i+1][j-1];b[i+1][j+1]=!b[i+1][j+1];b[i+2][j]=!b[i+2][j];}}}for(int i=1;i<=5;i++)if(!b[5][i])return Inf;//检测最后一行，如果存在熄灭的灯就说明这次递归失败，无解return sum;//成功则返回操作数
}

在代码写到这里的时候我们发现。我们并没有对第一行进行过任何的操作，很明显这样会漏解。

我们延续这种思路其实在遍历每一种情况的时候无非是选或者不选两种情况。这时我们就得出了状态转移方程

这里的cnt表示列，k表示操作数，当操作数＋1的时候表示打开开关，操作数不变时表示没有操作。cnt＋1表示前进一列

由此我们可以写出一个简单个dfs

int dfs(int cnt,int k)
{if(cnt>5)//到达第5列以后的判断(check)//按下开关时对周围开关的操作dfs(cnt+1,k+1);//按下这个开关//写递归最重要的就是还原案发现场dfs(cnt+1,k);//不按下这个开关
}

在这里我们只对第一行的操作进行了递归，为什么不对每一行都进行递归呐？

因为针对于下面的操作都是寻找未打开的开关有明确的指向性，而对于第一行的操作没有明确的目的，我们只是为了不遗漏答案。

int dfs(int cnt,int k)
{if(cnt>5){ans=min(ans,check(k));//对每一种合法操作进行比较寻找操作数最小的操作数//ans的初值设为IMT_MAX;return 0;}//按下开关时对周围开关的操作a[1][cnt]=!a[1][cnt];a[1][cnt-1]=!a[1][cnt-1];a[1][cnt+1]=!a[1][cnt+1];a[2][cnt]=!a[2][cnt];dfs(cnt+1,k+1);//按下这个开关//写递归最重要的就是还原案发现场a[1][cnt]=!a[1][cnt];a[1][cnt-1]=!a[1][cnt-1];a[1][cnt+1]=!a[1][cnt+1];a[2][cnt]=!a[2][cnt];dfs(cnt+1,k);//不按下这个开关
}

设计主函数

int main()
{scanf("%d",&t);while(t--){for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%1d",&a[i][j]);ans=Inf;dfs(1,0);if(ans<7)printf("%d\n",ans);//操作数是否小于等于6步。else printf("-1\n");}return 0;
}

完整代码:

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define Inf 0x3f3f3f
#define ll long long
using namespace std;
int t;
int ans;
int a[10][10];
int b[10][10];
int check(int cnt)//判断第一行的条件是否成立
{int sum=cnt;for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)b[i][j]=a[i][j];for(int i=1;i<=4;i++){for(int j=1;j<=5;j++){if(!b[i][j]){sum++;b[i][j]=!b[i][j];b[i+1][j]=!b[i+1][j];b[i+1][j-1]=!b[i+1][j-1];b[i+1][j+1]=!b[i+1][j+1];b[i+2][j]=!b[i+2][j];}}}for(int i=1;i<=5;i++)if(!b[5][i])return Inf;return sum;}
int dfs(int cnt,int k)
{if(cnt>5){ans=min(ans,check(k));return 0;}a[1][cnt]=!a[1][cnt];a[1][cnt-1]=!a[1][cnt-1];a[1][cnt+1]=!a[1][cnt+1];a[2][cnt]=!a[2][cnt];dfs(cnt+1,k+1);//按下这个开关a[1][cnt]=!a[1][cnt];a[1][cnt-1]=!a[1][cnt-1];a[1][cnt+1]=!a[1][cnt+1];a[2][cnt]=!a[2][cnt];dfs(cnt+1,k);//不按下这个开关
}
int main()
{scanf("%d",&t);while(t--){for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%1d",&a[i][j]);ans=Inf;dfs(1,0);if(ans<7)printf("%d\n",ans);else printf("-1\n");}return 0;
}