题目如题

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char g[N][N], t[N][N];
int n;

void turn(int x, int y) {
    int dx[] = { 0, 0, 0, -1, 1 };
    int dy[] = { 0, -1, 1, 0, 0 };
    for(int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a > 4 || b < 0 || b > 4) continue;
        g[a][b] = !(g[a][b] - '0') + '0';
    }
}

// 按行递归，一开始我搞的是个啥嘛。按列递归去了。
int check(int u, int& s) {
    if(u == 4) {
        int claim = 1;
        for(int j = 0; j < 5; j++)
            if(g[u][j] == '0') {
                claim = 0;
                break;
            }
        return claim;
    }

    for(int j = 0; j < 5; j++)
        // 看第u行j列开关的状态，决定第u + 1行j列开关的操作
        if(g[u][j] == '0')  
            s++, turn(u + 1, j);

    check(u + 1, s);
}

int calc() {
    int ans = 1e9;
    // 第0行一共有32种按键方案，所有解的产生都是因为32种方案导致
    for(int i = 0; i < 1 << 5; i++) {
        int res = 0;
        memcpy(t, g, sizeof g);
        // 按每种方案对应的数值的二进制按下第0排对应的开关
        for(int j = 0; j < 5; j++)
            if(i >> j & 1)
                res++, turn(0, j); 
        // 打开开关的过程以及检查一个方案是否有解用递归解决
        if(check(0, res)) ans = min(ans, res);
        memcpy(g, t, sizeof t);       
    }

    if(ans > 6) return -1;
    return ans;
}

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

算法1

(暴力枚举) $O(n^3)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char g[N][N], t[N][N];
int n;

void turn(int x, int y) {
    int dx[] = { 0, 0, 0, -1, 1 };
    int dy[] = { 0, -1, 1, 0, 0 };
    for(int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a > 4 || b < 0 || b > 4) continue;
        g[a][b] = '0' + !(g[a][b] - '0');
    }
}

int calc() {
    int ans = 1e9;
    // 一共有32种按键方案
    for(int i = 0; i < 1 << 5; i++) {
        int res = 0;
        memcpy(t, g, sizeof g);
        // 按每种方案对应的数值的二进制按下第0排对应的开关
        for(int j = 0; j < 5; j++)
            if(i >> j & 1)
                res++, turn(0, j); 
        // 从第0排开始直到第3排，遍历每一排的开关。
        // 如果是关闭的，才对下一排正下方的开关进行按键操作
        for(int k = 0; k < 4; k++)
            for(int j = 0; j < 5; j++)
                if(g[k][j] == '0')
                   res++, turn(k + 1, j);
        // 检查最后一排的开关是不是全部打开
        // 最后一排的开关全部打开，最初的状态有解
        int claim = 1;
        for(int j = 0; j < 5; j++)
            if(g[4][j] == '0') {
                claim = 0;
                break;
            }
        // 有解求最小解，无解什么都不做
        if(claim) ans = min(ans, res); 
        memcpy(g, t, sizeof t);       
    }
    if(ans > 6) return -1;
    return ans;
}

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