费解的开关

https://www.acwing.com/problem/content/97/

思路：

1. 先枚举第一行开关的按法（可用二进制数位表示），并根据按法改变当前矩阵状态
2. 第一行状态确定后，遍历1~4行，每一行若出现 0，则该 0 由下一行同列的位置按下开关改变；最后前四行的状态都是 1
3. 最后遍历第 5 行，如果出现 0，则需要按下开关改变，但因此会改变前四行的全1状态，因此不合法；所以最后一行全 1 才是合法状态

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 10;

int g[N][N], tmp[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void change(int x, int y){
    g[x][y] = !g[x][y];
    for(int i = 0; i < 4; i ++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx > 0 && nx <= 5 && ny > 0 && ny <= 5){
            g[nx][ny] = !g[nx][ny];
        }
    }
}

void solve(){
    int res = 10;
    for(int i = 0; i < 1 << 5; i ++){ // 枚举第一行按法
        memcpy(tmp, g, sizeof g); // 数组备份
        int cnt = 0;
        for(int j = 0; j < 5; j ++){ // 翻转第一行
            if(i & 1 << j){
                cnt ++;
                change(1, j + 1);
            }
        }
        for(int k = 1; k <= 4; k ++){ // 遍历1~4行
            for(int j = 1; j <= 5; j ++){
                if(g[k][j] == 0){
                    cnt ++;
                    change(k + 1, j); // 当前行由下一行翻转改变
                }
            }
        }
        bool flag = true;
        for(int j = 1; j <= 5; j ++){
            if(g[5][j] == 0){
                flag = false;
                break;
            }
        }
        if(flag) res = min(res, cnt);
        memcpy(g, tmp, sizeof g);
    }
    if(res > 6) cout << -1 << '\n';
    else cout << res << '\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T --){
        for(int i = 1; i <= 5; i ++){
            for(int j = 1; j <= 5; j ++){
                char x;
                cin >> x;
                g[i][j] = x - '0';
            }
        }
        solve();
    }
    return 0;
}