费解的开关
模拟一下开关的过程:
直接对第一行进行开关灯即可,那么第一行开关等的方案有多少个呢?
可以第一个想到的是5
次,但实际上是25次,因为没有规定说只能开关一次吧。
那么如何获得这32种方案呢?
可以通过二进制来获得,我们知道0~31
刚好是32个数字,而对应的二进制序列也是从00000~11111
,这不就是一种排列吗?
00000
00001
00010
00010
00011
00100
00101
00110
00111
.
.
.
.
.
11111
其中1表示需要开关灯。
#include<iostream>
#include<cstring>
#include<limits.h>
#include<algorithm>
using namespace std;
const int N = 6;
int n;
char g[N][N], backup[N][N];
int dx[N] = { -1, 0, 1, 0, 0 }, dy[N] = { 0, 1, 0, -1, 0 };
//上、右、下、左、自己
//修改上下左右的灯的情况
void turn(int x, int y)
{
for (int i = 0; i < 5; i++)
{
int ax = x + dx[i], ay = y + dy[i];
if (ax < 0 || ax >= 5 || ay < 0 || ay >= 5) continue;
if (g[ax][ay] == '0')g[ax][ay] = '1';
else g[ax][ay] = '0';
}
}
int dfs(char g[6][6])
{
int step = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 5; j++)
{
if (g[i][j] == '0')
{
turn(i + 1, j);
step++;
}
}
}
return step;
}
bool check()
{
for (int j = 0; j < 5; j++)
{
if (g[4][j] == '0')return false;
}
return true;
}
int main(void)
{
cin >> n;
while (n--)
{
int res = INT_MAX;
bool ch = false;
for (int i = 0; i < 5; i++) cin >> g[i];
//枚举第一行的情况
for (int op = 0; op < 32; op++)
{
memcpy(backup, g, sizeof(backup));//备份一下一开始的地图
int start = 0;
for (int i = 0; i < 5; i++)
{
if (op >> i & 1)
{
start++;
turn(0, i);
}
}
int ans = dfs(g)+start;
if (check()&&res > ans)
{
res = ans;
}
memcpy(g, backup, sizeof(backup));
}
if (res <=6&&res!=-1)
{
printf("%d\n", res);
}
else
{
printf("-1\n");
}
}
return 0;
}