费解的开关 (蓝桥杯倒计时12天）

你玩过“拉灯”游戏吗？

2525 盏灯排成一个 5×55×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 11 表示一盏开着的灯，用数字 00 表示关着的灯。

下面这种状态

在改变了最左上角的灯的状态后将变成：

再改变它正中间的灯后状态将变成：

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 nn，代表数据中共有 nn 个待解决的游戏初始状态。

以下若干行数据分为 nn 组，每组数据有 55 行，每行 55 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 nn 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1−1。

数据范围

输入样例：

输出样例：

3
2
-1

解题思路：

首先，看到这道题，应该就知道需要位运算的思想，当时想了一会，看了一下题解，应该是利用二进制和字符串的思想去解题，

仔细读题，我们会发现按下一个灯泡是会改变他的上下左右的状态的，

此外，如何改变他的状态，可以从左右也可以从上下，但是最优步数，所以应该是按每一个需要改变的灯泡下面位置；

然后，每一行的字符串是可以看成二进制去求解的，所以2^5，一行有32种可能，那么则需要枚举32种可能，分别找到步数，再统计其最优步数，所以我们需要开俩个数组，一个存灯泡状态，一个备份。即可求出所需步数。

#include
#include
#include
#include

using namespace std;
const int N = 6;
int n;
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 > 4 || b < 0 || b > 4) continue;
        g[a][b] ^= 1; //异或运算，不同则同。
    }
}

int main()
{
    cin >> n;
    while(n --)
    {
        for(int i = 0; i < 5; i ++) cin >> g[i];
        
        int res = 7;
        for(int op = 0; op < 32; op ++)//因为一行字符串看成二进制最大是32,所有一行有32种不同；
        {
            memcpy(backup, g, sizeof g);//备份数组，方便每次找出最优步数；
            int step = 0;//记录步数
            //第一行的枚举步数
            for(int i = 0; i < 5; i ++)//一行有五个灯泡，所以需要右移5次，
            {
                if(op >> i & 1)//假设op为2，那么二进制表示为00010，
                {              //那么右移一次，按位与1则为1，也就是说一行需要在第二个位置按一下
                    step ++;   //那么当op = 3, 对应00011， 则第一个和第二个位置需要按一下
                    turn(0, i);
                }
            }
            //第二行到倒数第二行的枚举步数
            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 dark = false;
            for(int j = 0; j < 5; j ++)
               if(g[4][j] == '0')
               {
                   dark = true;
                   break;//根据题意，最后一行如果有黑的，则无解
               }
              
            if(!dark) res = min(res, step); //最后一行全亮，则统计32种情况的最少步数
            memcpy(g, backup, sizeof g);
        }
        if(res > 6) res = -1;
        cout << res << endl;
    }
    return 0;
}

点个赞再走呗！

感谢支持！

费解的开关 (蓝桥杯倒计时12天）

C/C++/C#相关栏目本月热门文章