题目链接

EXTENDED LIGHTS OUT POJ - 1222

思路

$$ 反转问题，枚举第一行的情况，第一行确定，整个反转也就确定了 $$

时间复杂度

$$ O(2^N*M * N) $$

代码

#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20;
int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
int n, m;

void gao(int x, int y) {
    b[x][y] ^= 1;
    b[x + 1][y] ^= 1;
    b[x - 1][y] ^= 1;
    b[x][y - 1] ^= 1;
    b[x][y + 1] ^= 1;
}

int check(int x) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] = a[i][j];
            c[i][j] = 0;
        }
    }
    int cnt = 0;
    for (int i = m - 1; i >= 0; i--) {
        if ((x >> i) & 1) {
            gao(1, i + 1);
            c[1][i + 1] = 1;
            cnt++;
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i - 1][j] == 1) {
                gao(i, j);
                c[i][j] = 1;
                cnt++;
            }
        }
    }
    for (int j = 1; j <= m; j++) {
        if (b[n][j] == 1) {
            return INF;
        }
    }
    return cnt;
}


int main() {

    n = 5, m = 6;
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
         for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);// don't forget &
            }
        }
        int ans1 = 0, ans2 = INF;
        for (int i = 0; i < (1 << m); i++) {
            int num = check(i);
            if (num < ans2) {
                ans2 = num;
                ans1 = i;
            }
        }
        printf("PUZZLE #%d\n", kase);
        if (ans2 == INF) {
            puts("IMPOSSIBLE");
        } else {
            check(ans1);
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= m; j++) {
                    printf("%d%c", c[i][j], " \n"[j == m]);
                }
            }
        }
    }

    return 0;
}