首页 > 代码库 > 校内训练0611 矩阵

校内训练0611 矩阵

2024-10-04 12:29:02   216人阅读

【题目大意】

给一个n*n的矩阵，每个位置为0或1。每次可以选择一行和一列，把那列完全赋值为那行的值。求最少多少步使得全为1.

无解输出-1。

n <= 1000

【题解】

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

每一列，只要有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 + 10;
const int mod = 1e9+7;

# 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=1; i<=n; ++i) scanf("%s", mp[i]+1);
    bool all = 1;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            all &= (mp[i][j] == ‘.‘);
    if(all) {
        puts("-1");
        return 0;
    }
    
    int ans = 0;
    for (int i=1; i<=n; ++i) {
        bool have = 0;
        for (int j=1; j<=n; ++j) {
            if(mp[j][i] == ‘.‘) {
                have = 1;
                break;
            }
        }
        ans += have;
        for (int j=1; j<=n; ++j) 
            if(mp[j][i] == ‘#‘) hv[i] = 1;
    }
    
    int tmp = 1e9;
    for (int i=1; i<=n; ++i) {
        // for one line
        int cur = 0;
        for (int j=1; j<=n; ++j) cur += (mp[i][j] == ‘.‘);
        if(cur == 0 || hv[i]) tmp = min(tmp, cur);
        else tmp = min(tmp, cur+1);
    }
    cout << ans + tmp;

    return 0;
}
View Code

 

校内训练0611 矩阵


联系
我们