题目描述
5*5的方格中每个格子填1或0,1代表灯亮,0代表灯灭,每次操作一个点,相应的本身,上下左右的点的状态也跟着变。
问题:使所有灯都亮,最少需要几次操作?
样例
输入样例
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例
3
2
-1
算法1
(暴力枚举) $O(n^2)$
暴力枚举第一行的所有情况,一共32种。
首先分析题目可以得到:
1.每个点最多按一次,因为按多次没有意义,按两次相当于没按。
2.顺序可以任意。
所以我们的做法是枚举第一行的所有操作,这里用0,1表示, 1表示按了一次, 0代表没按,转换成10进制就是:0 ~ 31。
所以在每一种操作的开始先把1的turn一下。
之后就是看前四行,每次看一行,如果灯是灭的(0),把它相对应的下面那个点turn一下,
因为想让这个灯亮,有五种操作的方法上下左右和自己,上左右和自己都不能操作了,显然只能操作下面这个点了。
同理如果这个点是亮着的,则它下面的那个点就不能按!
最后判断最后一行是否是全部亮着的,如果全亮,则代表一种方案,(所作的操作只能保证前四行都是亮着的),
每次比较这32种操作步骤的最小值,如果大于6步就等于-1,不大于输出即可!
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};
void turn(int x, int y)
{
for(int i = 0; i < 5; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
g[a][b] ^= 1;
}
}
int main()
{
int t;
cin >> t;
while(t --)
{
for(int i = 0; i < 5; i ++) cin >> g[i];
int res = 100;
for(int i = 0; i < 32; i ++)
{
memcpy(backup, g, sizeof g);
int step = 0;
for(int j = 0; j < 5; j ++)
if(i >> j & 1) {step ++; turn(0,j);}
for(int i = 0; i < 4; i ++)
for(int j = 0; j < 5; j ++)
if(g[i][j] == '0')
{
step ++;
turn(i + 1, j);
}
bool is_dark = false;
for(int i = 0; i < 5; i ++)
if(g[4][i] == '0')
{
is_dark = true;
break;
}
if(is_dark == false) res = min(res, step);
memcpy(g, backup, sizeof backup);
}
if(res > 6) cout << -1 << endl;
else cout << res << endl;
}
return 0;
}