费解的开关

  • 2019-06-29
  • 130
  • 0

费解的开关

题目描述:

你玩过“拉灯”游戏吗?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

暴力 + 二进制枚举

根据开关的规则,不难发现,对于某一行的灯,如果它是熄灭的,那么,只要按一下它下方的那一盏灯的开关,就可以在后续的过程中保证当前这一行的这一盏灯处于开启状态。

由上述结论得出,对于一盏灯的开关按或者不按,取决于这一盏灯的上方那盏灯是处于熄灭还是明亮状态。

那么,当第一行灯的状态固定时,只需要枚举前四行,就可以得出第 2 到 5 行按开关的次数,再判断第五行的灯是否处于全亮状态来决定是否更新答案。

而对于第一行灯的状态,为了判断所有情况,可以用一个数的二进制位是否为 1 来表示在进入上述枚举之前是否事先改变第一行的某盏灯的状态。

虽然有 500 组数据,但是每组数据只有 5 行 5 列,上述暴力完全可以的一秒内出解。


评论

还没有任何评论,你来说两句吧

浙ICP备19014917号

浙公网安备 33068302000569号