Solution to CF815A

· · 题解

分析

首先分析无解的情况：如果我们找遍了每行每列，然后每次都把那一行或那一列的每个数减掉其中的最小数，最后有不是 0 的数，就无解了。

在有解的基础上，如果 n<m 就要先处理行再处理列，否则先处理列再处理行。我们先看一个比较极端的例子：

5 3
6 6 6
6 6 6
6 6 6
6 6 6
6 6 6

显然是先处理列会快，因为每在列上操作一次减掉的总数值更大，其他情况也可类推。

代码

#include<bits/stdc++.h>
using namespace std;
char res[5000004];
int n,m,cnt,tot,a[104][104];

vector < int > r,c;

void solveR(){
    for(int i=1;i<=n;i++){
        int mini=0x7fffffff;
        for(int j=1;j<=m;j++)
            mini=min(mini,a[i][j]);
        for(int j=1;j<=m;j++)
            a[i][j]-=mini;
        while(mini--){
            ++tot;
            r.push_back(i);
        }
    }
}

void solveC(){
    for(int i=1;i<=m;i++){
        int mini=0x7fffffff;
        for(int j=1;j<=n;j++)
            mini=min(mini,a[j][i]);
        for(int j=1;j<=n;j++)
            a[j][i]-=mini;
        while(mini--){
            ++tot;
            c.push_back(i);
        }
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    if(n<m){
        solveR();
        solveC();
    }
    else{
        solveC();
        solveR();
    }
    bool f=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]!=0)
                f=1;
    if(f){
        puts("-1");
        return 0;
    }
    printf("%d\n",tot);
    for(int i=0;i<r.size();i++)
        printf("row %d\n",r[i]);
    for(int i=0;i<c.size();i++)
        printf("col %d\n",c[i]);
    return 0;
}