5923번: Binary Sudoku

https://www.acmicpc.net/problem/5923

$O(...)$

dp[i][j][k]: 1~i번 행을 xor한 값이 j이고 i번 행을 포함하는 세 개의 3*3 블록에 대해 각 블록마다 xor해서 표현한 세 자리 수가 k일 때, 토글 횟수의 최솟값

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10][1 << 9][1 << 3], a[10];
int f(int x, int y, int z) {
    if (!x) return y ? 99 : 0;
    if (x % 3 == 0 && z) return 99;
    if (dp[x][y][z] ^ -1) return dp[x][y][z];
    int ret = 99;
    for (int i = 1 << 9; i--;) {
        int t = 0, u = 0, v = 0;
        for (int j = 0; j < 9; j++) if (1 << j&i) t ^= 1 << j / 3, u++;
        if (u & 1) continue;
        for (int j = 0; j < 9; j++) if (1 << j&(i^a[x])) v++;
        ret = min(ret, f(x - 1, y^i, z^t) + v);
    }
    return dp[x][y][z] = ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= 9; i++)
        for (int j = 0, x; j < 9; j++) scanf("%1d", &x), a[i] = a[i] * 2 + x;
    printf("%d", f(9, 0, 0));
    return 0;
}