AcWing 95. 费解的开关
原题链接
中等
作者:
YAX_AC
,
2024-02-05 20:30:07
,
所有人可见
,
阅读 31
// 思路:我们枚举第一行的点击方法,共32种,完成第一行的点击后,固定第一行,
// 从第一行开始递推,若达到第n行不全为0,说明这种点击方式不合法。
// 在所有合法的点击方式中取点击次数最少的就是答案。
// 对第一行的32次枚举涵盖了该问题的整个状态空间,因此该做法是正确的
//
// 时间复杂度:32*20*5*500
// 对第一行操作有32种可能 * 对前四行有20种操作可能 * 每一次操作都要改变5个灯的状态 * 最多读入的时候可能有500次light矩阵
//
// 最关键的两个性质
// 每一个位置最多只会被点击一次
// 如果固定了第一行,那么满足题意的点击方案最多只有一种
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 6;
char g[N][N],backup[N][N];
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};//存一下,上下左右,5个方向的偏移量
// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
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; //异或,不同的时候就变成相反的数,相同变1,不同变0
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
// 按行输入,把每一行当成一个字符串
for(int i = 0;i < 5;i++) cin>>g[i];
int res = 10;//最多需要多少步,超过6步就是无解
//对该行所有灯按不按的所有情况进行枚举
//第一行5个位置共32种按法,都先按一遍
for(int op = 0; op < 32; op++)
{
// 把原始数组备份一下,然后操作g,操作完了还原,然后再操作
memcpy(backup, g,sizeof g);
int step = 0;//记录最小步数
//枚举第一行的操作
for(int i = 0;i < 5;i++)
{
//看二进制第i位是否为1,右移i位余上1,op>>i&1
if(op >> i & 1)//为了找到当前这个op情况下哪些数字是1.是1的话就需要对上下左右,进行操作,是0的话不操作
{
step++;
turn(0,i);//turn(x,y)对数组第一行进行操作,改变了g[0][i]
}
}
// 然后通过对第一行操作完,对234行进行操作
for(int i = 0;i < 4;i++)
{
for(int j = 0;j < 5;j++)
{
if(g[i][j] == '0') //如果前一行 == ‘0’,那么改变下一行
{
step++;
turn(i+1,j); // 如果这个位置是灭的,就下一行对应的位置进行操作
}
}
}
//判断最后一行灯有没有黑(灭)的
bool dark = false;
for(int i = 0;i < 5; i++)
{
//最后一行有黑的
if(g[4][i] == '0')
{
dark = true;
break;
}
}
//最后一行没用黑的
if(!dark) res = min(res,step); //取最小步数
memcpy(g,backup,sizeof g);//原数组从备份里面copy回来
}
if(res > 6) res = -1;//步数大于6
cout<< res <<endl;
}
return 0;
}