题解 P1391 【方阵安排】

· · 题解

一、 40分做法

很容易想到枚举矩阵中的每一个数判断其变还是不变，最后判断整个矩阵是否满足条件。但是会TLE，只能过掉40%的数据...

二、100分做法

N的范围只有18，所以第一行只有不超过2^18种可能性，是我们可以枚举的，接下来我们可以根据第一行计算出第二行，再根据第二行又能计算出第三行以此类推……

最后的时间复杂度为O(2^n * n ^ 2)可以承受...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <iterator>
#define LL long long
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int maxn = 20;
const int INF = 10000000000;
int N, A[maxn][maxn], B[maxn][maxn];
int query(int cur){
    mem(B, 0);
    rep(j, 0, N-1){
        if(cur & (1<<j)) B[0][j] = 1;
        else if(A[0][j] == 1) return INF;
    }
    rep(i, 1, N-1) rep(j, 0, N-1){
        int sum = 0;
        if(i > 1) sum += B[i-2][j];
        if(j > 0) sum += B[i-1][j-1];
        if(j < N-1) sum += B[i-1][j+1];
        B[i][j] = sum % 2;
        if(A[i][j] == 1 && B[i][j] == 0) return INF;
    }
    int cnt = 0;
    rep(i, 0, N-1) rep(j, 0, N-1)
        if(A[i][j] != B[i][j]) cnt++;
    return cnt;
}
int main(){
    scanf("%d", &N);
    rep(i, 0, N-1) rep(j, 0, N-1) scanf("%d", &A[i][j]);
    int ans = INF;
    rep(i, 0, (1<<N)-1) ans = min(ans, query(i));
    if(ans == INF) ans = -1;
    printf("%d\n", ans);
    return 0;
}