水博客真开心

1. 题目

传送门=￣ω￣=

2. 题解

枚举第一行状态，后面的状态就都知道了。

理论上高斯消元也能做，但是我并不知道怎么找又要 1 的个数最少又要字典序最小。。。

代码：

#include <bits/stdc++.h>

#define NS (20)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, d[NS][NS], ans[NS][NS], tmp[NS][NS], tot = INT_MAX, lst[NS][NS];

void push(int a, int b)
{
    if (a > 1) tmp[a - 1][b] ^= 1;
    if (a < n) tmp[a + 1][b] ^= 1;
    if (b > 1) tmp[a][b - 1] ^= 1;
    if (b < m) tmp[a][b + 1] ^= 1;
    tmp[a][b] ^= 1;
}

void Dfs(int a, int b)
{
    if (b > m) {Dfs(a + 1, 1); return;}
    if (a > n)
    {
        for (int i = 1; i <= m; i += 1)
            if (tmp[n][i] != d[n][i]) return;
        int cnt = 0;
        for (int i = 1; i <= n; i += 1)
            for (int j = 1; j <= m; j += 1)
                cnt += ans[i][j];
        if (cnt >= tot) return;
        memmove(lst, ans, sizeof(lst)), tot = cnt;
        return;
    }
    if (a == 1)
    {
        ans[a][b] = 0, Dfs(a, b + 1);
        ans[a][b] = 1, push(a, b), Dfs(a, b + 1), push(a, b);
    }
    else
    {
        if (tmp[a - 1][b] != d[a - 1][b])
            ans[a][b] = 1, push(a, b), Dfs(a, b + 1), push(a, b);
        else ans[a][b] = 0, Dfs(a, b + 1);
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            IN(d[i][j]);
    Dfs(1, 1);
    if (tot > 1e9) puts("IMPOSSIBLE");
    else for (int i = 1; i <= n; i += 1, putchar(10))
        for (int j = 1; j <= m; j += 1)
            printf("%d ", lst[i][j]);
    return 0;
}