AcWing 95. 费解的开关

原题链接
你玩过“拉灯”游戏吗？

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

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

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

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

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

下面这种状态

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

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

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

输入格式

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

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

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

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

输出格式

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

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

数据范围

0<n≤500

输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1
题解

枚举每个方形的第一行的所有可能, 这里用二进制表示, 当前位上是 1 表示改变当前位置和周围的灯
每种可能第一行确定之后, 后面的 n - 1 行的都有确定的情况, 最后判断最后一行是否都为 1, 都为 1 并且改变的 次数 小于等于 6 的话满足条件

下图模拟的是样例输入的第一个方阵

• 当 op 等于 16 的时候是该题的解, (16)2 = 10000, 表示改变第一行的第一个灯
• [2,5]行的操作要根据它上一行灯的状态, 当 (i - 1, j) 的灯是灭的, 就改变(i, j)位置的灯和它(上下左右的灯)
• 图中圈红的 (3,3)位置上面的(2,3)灯是灭的, 所有改变(3,3)的灯和它上下左右的灯, 另一个圈红的同上~~
  

#include <bits/stdc++.h>
using namespace std;
const int N = 10, n = 5;
char g[N][N], back[N][N];
int go[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void change(int x, int y)
{
    g[x][y] = (g[x][y] == '0' ? '1' : '0');
    for (int i = 0; i < 4; i ++)
    {
        int a = x + go[i][0], b = y + go[i][1];
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        g[a][b] = (g[a][b] == '0' ? '1' : '0');
    }
}

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        for (int i = 0; i < n; i ++)
            cin >> g[i];
        
        vector<int> res;  // 存答案
        memcpy(back, g, sizeof g);  // 我们枚举的时候会改变 g 的状态, back留作备份
        for (int op = 0; op < 32; op ++)  // [0,31] 的二进制刚好枚举完第一行的所有可能 (从二进制 [00000,11111])
        {  
            int step = 0;     // 记录每种枚举的操作步数
            memcpy(g, back, sizeof back);  // 初始化 g 的状态为 原状态
            for (int j = 0; j < n; j ++)
                if (op >> j & 1)
                {
                    step ++;
                    change(0, n - j - 1);
                }

            for (int i = 1; i < n; i ++)
                for (int j = 0; j < n; j ++)
                    if (g[i - 1][j] == '0')
                    {
                        change(i, j);
                        step ++;
                    }

            bool f = true;
            for (int i = 0; i < n; i ++)
                if (g[n - 1][i] == '0')
                {
                    f = false;  // 最后一行还有灭的灯的话, 不满足条件
                    break;
                }
            
            if (f && step <= 6) res.push_back(step);
        }
        if (res.size() == 0) cout << -1 << endl;
        else
        {
            sort(res.begin(), res.end());  // 步数最少, 取最小值
            cout << res[0] << endl;
        }
    }
    return 0;
}