费解的开关解析

2024-02-07 17:40:11

费解的开关
描述:
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

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

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

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

输入格式

第一行有一个正整数n，代表数据*有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。

输出格式
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。

输入样例：

输出样例：

3
2
-1

在这运用的主要运用的方法是位运算
注意的一些点都放在代码里了，有兴趣的同学可以运行一下
这一题主要的思想路线：（希望大家看看）

这一题的总体思路就是枚举第一排由于性质来说其实一个按钮如果按偶数次其实是没有用处的(会复原)，
所以可以推出其实每个按钮就按过一次，通过前一排灯光的状态来决定开关的操作，
通过对第一排的全排会产生一些关闭的开关(还会有连带的关系)，所以在第二排把第一排的关闭按钮下面按一次，
以此类推~~~~~~在第四排对应关闭的下面按依次，
最后特判一次第五排如果都是开着的就成功和之前的步数进行比较，取小的值.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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 = 10;
               for (int op = 0; op < 32; op++)                    //操作数2^5，全排第一行，可以进行2^5不同的操作
               {
                       memcpy(backup, g, sizeof g);
                       int step = 0;
                       for (int i = 0; i < 5; i++)
                              if (op >> i & 1)
                              {
                                      step++;
                                      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 i = 0; i < 5; i++)
                              if (g[4][i] == '0')
                              {
                                      dark = true;
                                      break;
                              }
                       if (!dark) res = min(res, step);            //min方法必须加头文件#include <algorithm>
                       memcpy(g, backup, sizeof g);                //还原继续测试，取到最小的步数
               }
               if (res > 6) res = -1;
               cout << res << endl;
        }
        return 0;
}

在进行第一排的全排时的操作时可以利用数字来表示，
每个按钮可以有按和不按所以就2^5可以用0~31进行位运算来代替实现全排的效果，
还有就是对于开关连带的表示见下图

码农公寓

相关文章