[数据结构与算法]费解的开关-递推

费解的开关-递推

费解的开关
看了几个回答，感觉写的不太清晰，这里记录一下我的理解
这道题最重要的就是要得出，最后是否能全部点亮，与点亮的先后次序无关。意思就是说，只要确定了点哪些盏灯，那么无论哪个先，都会得到相同的答案。
那么递推体现在哪个地方呢？
我们只要确定了第一行的操作方式，哪些动，哪些不去动它，结果也会随之被确定下来。往后的每一行，我们只需要根据前一行对应位置的亮灭情况，来决定是否操作。
以这样的方式，最终能否被全部点亮，都会在最后一行体现出来。只需要判断最后一行是否全亮就可以得到答案
这道题有状态压缩DP那意思，进一步强化了位运算。
难点在于这个递推比较难被发现出来

#include <iostream>
#include <cstring>
#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 i = 0; i < (1 << 5); i++) { // 枚举第一行所有可能的操作方法
            memcpy(backup, g, sizeof g); // 保存最初始的状态
            int step = 0; // 记录操作次数
            for (int j = 0; j < 5; j++) {
                if (i >> j & 1) {
                    turn(0, j);
                    step++;
                }
            }
            for (int i = 0; i < 4; i++) //后面的每一行中的每一格是否操作，取决于它的上一格
                for (int j = 0; j < 5; j++) {
                    if (g[i][j] == '0') {
                        turn(i+1, j);
                        step++;
                    }
                }
            
            bool isdark = false; // 遍历最后一行是否全亮即可得到答案
            for (int i = 0; i < 5; i++)
                if (g[4][i] == '0') isdark = true;
            
            if (!isdark) res = min(res, step);
            memcpy(g, backup, sizeof backup); // 还原成最初始的状态
        }
        if (res > 6) res = -1;
        cout << res << endl;
    }
    
    return 0;
}