费解的开关

AcWing-95-费解的开关

分析

见《进阶指南》第16页。

实现

#include <iostream>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;

int dirx[4] = { -1, 1, 0, 0 };
int diry[4] = { 0, 0, -1, 1 };
int lights[5][5], copy_lights[5][5];

void press (int x, int y) {
    copy_lights[x][y] ^= 1;
    for (int i = 0; i < 4; ++ i) {
        int nx = x + dirx[i], ny = y + diry[i];
        if (nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;
        copy_lights[nx][ny] ^= 1;
    }
}
bool check () {
    for (int j = 0; j < 5; ++ j)
        if (copy_lights[4][j] == 0)
            return false;
    return true;
}

int main () {
    int T;
    scanf("%d", &T);
    while (T --) {
        for (int i = 0; i < 5; ++ i)
            for (int j = 0; j < 5; ++ j)
                scanf("%1d", &lights[i][j]);
        
        int res = inf;
        for (int k = 0; k < (1 << 5); ++ k) { // 00000 ~ 11111
            for (int i = 0; i < 5; ++ i)
                for (int j = 0; j < 5; ++ j)
                    copy_lights[i][j] = lights[i][j];

            int cnt = 0;
            for (int j = 0; j < 5; ++ j) {
                if ((k >> j) & 1) { // 第 j 位是 1
                    press(0, j);
                    ++ cnt;
                }
            }
            for (int i = 0; i < 4; ++ i) {
                for (int j = 0; j < 5; ++ j) {
                    if (copy_lights[i][j] == 0) {
                        press(i + 1, j);
                        ++ cnt;
                    }
                }
            }
            if (check()) res = min(res, cnt);
        }
        printf("%d\n", res <= 6 ? res : -1);
    }
    return 0;
}