loj6030 「雅礼集训 2017 Day1」矩阵

传送门：https://loj.ac/problem/6030

【题解】

以下把白称为0，黑称为1.

发现只有全空才是无解，否则考虑构造。

每一列，只要有0的格子都需要被赋值1次，所以设有x列有含有0的格子，则至少要赋值x次。

现在我们就需要一个全1的行来给这些有0的列赋值。

考虑构造一个全1的行。我们枚举第i行，假装要把他弄成全1的。

设第i行的0的数量为y，那么考虑第i列是否含有1，如果含有1那么就可以用含有1的那列的那行给第i行所有0的地方赋值，需要y步。

如果第i列不含有1，我们要花1次操作给第i列搞个1出来，所以答案是y+1步。

取最小值即可。

这签到题我怎么没做出来啊。。

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 1e3 + ;

const int mod = 1e9+;

# define RG register

# define ST static

int n, a[M];

char mp[M][M];

bool hv[M];

int main() {

//    freopen("matrix.in", "r", stdin);

//    freopen("matrix.out", "w", stdout);

    cin >> n;

    for (int i=; i<=n; ++i) scanf("%s", mp[i]+);

    bool all = ;

    for (int i=; i<=n; ++i)

        for (int j=; j<=n; ++j)

            all &= (mp[i][j] == '.');

    if(all) {

        puts("-1");

        return ;

    }

    int ans = ;

    for (int i=; i<=n; ++i) {

        bool have = ;

        for (int j=; j<=n; ++j) {

            if(mp[j][i] == '.') {

                have = ;

                break;

            }

        }

        ans += have;

        for (int j=; j<=n; ++j)

            if(mp[j][i] == '#') hv[i] = ;

    }

    int tmp = 1e9;

    for (int i=; i<=n; ++i) {

        // for one line

        int cur = ;

        for (int j=; j<=n; ++j) cur += (mp[i][j] == '.');

        if(cur ==  || hv[i]) tmp = min(tmp, cur);

        else tmp = min(tmp, cur+);

    }

    cout << ans + tmp;

    return ;

}