题目描述

25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：
和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。

注释很详尽

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int N = 5;
// 方向数组，用于表示上下左右四个方向
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

// 检查坐标 (x, y) 是否在 5x5 的网格内
bool inGrid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 改变一盏灯及其相邻灯的状态
void flip(vector<vector<int>>& lights, int x, int y) {
    lights[x][y] ^= 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (inGrid(nx, ny)) {
            lights[nx][ny] ^= 1;
        }
    }
}

// 检查是否所有灯都亮着
bool allLit(const vector<vector<int>>& lights) {///！！！！
    for (const auto& row : lights) {
        for (int light : row) {
            if (light == 0) {
                return false;
            }
        }
    }
    return true;
}

// 计算使所有灯变亮的最少步数
int minSteps(vector<vector<int>> lights) {
    int ans = INT_MAX;
    // 枚举第一行的所有可能操作状态，2^5 = 32 种
    for (int state = 0; state < (1 << N); state++) {
        vector<vector<int>> curLights = lights;
        int steps = 0;
        // 根据第一行的操作状态改变灯的状态
        for (int j = 0; j < N; j++) {
            if (state >> j & 1) {
                flip(curLights, 0, j);
                steps++;
            }//将第一行全部置0
        }
        // 从第二行开始，根据上一行的灯状态确定当前行的操作
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (curLights[i - 1][j] == 0) {
                    flip(curLights, i, j);
                    steps++;
                }
            }
        }
        // 检查最后一行的灯是否都亮着
        if (allLit(curLights)) {
            ans = min(ans, steps);
        }
    }
    return ans <= 6 ? ans : -1;
}

int main() {
    int n;
    cin >> n;
    for (int k = 0; k < n; k++) {
        vector<vector<int>> lights(N, vector<int>(N));//！！！
        for (int i = 0; i < N; i++) {
            string line;
            cin >> line;
            for (int j = 0; j < N; j++) {
                lights[i][j] = line[j] - '0';
            }
        }
        cout << minSteps(lights) << endl;
        if (k < n - 1) {
            cin.ignore(); // 消耗掉每组数据间的空行
        }
    }
    return 0;
}