题目描述

补充一个暴力递归的版本，TLE在500的测试用例 间接说明地推的优势

样例

#include <iostream>
#include <cstring>
using namespace std;

const int N = 6;
char g[N][N], backup[N][N];
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};
int min_steps;

//按下灯的操作 不变
void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) {
            continue;
        }
        g[nx][ny] ^= 1;
    }
}

//用于判断最后一行的情况
bool all_lit() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (g[i][j] == '0') {
                return false;
            }
        }
    }
    return true;
}

void dfs(int x, int y, int steps) {
    if (steps >= min_steps) {
        return;
    }

    if (x == 5) {  // 查看最后一行的情况
        if (all_lit()) {
            min_steps = steps;
        }
        return;
    }

    //相当于对灯一个一个去递归 顺序为从左到右 从上到下
    if (y == 5) {
        dfs(x + 1, 0, steps);
        return;
    }

    //子问题：对于当前的灯递归到下一个灯两个状态，当前灯如果不操作 递归下一个 当前灯操作 递归下一个

    //不操作(x,y)
    dfs(x, y + 1, steps);

    //操作(x,y)
    turn(x, y);
    dfs(x, y + 1, steps + 1);
    turn(x, y);  //这一步相当于备份数组 每次恢复成没有考虑过当前灯的状态 以免污染后面的数据
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        for (int i = 0; i < 5; i++) {
            cin >> g[i];
        }

        min_steps =7;
        memcpy(backup, g, sizeof g);

        dfs(0, 0, 0);

        if (min_steps > 6) {
            min_steps = -1;
        }

        cout << min_steps << endl;
    }
    return 0;
}