Karen and Game

题目描述

On the way to school, Karen became fixated on the puzzle game on her phone!

The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.

One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

题意概述

给定一个初始全为$0$的矩阵$s$和一个目标矩阵$g$，两矩阵大小均为$n \times m$。每次操作可以将矩阵$s$中某一行或某一列的数全部加一。求一个能将$s$变成$g$且操作数最少的操作序列。

数据范围：$1 \le n, m \le 100, \ 0 \le g_{i, j} \le 500$。

算法分析

可以倒过来思考：每次操作将$g$中某一行或某一列的数全部减一，要求得到所有数均为$0$的矩阵。显然，操作序列满足交换律。因此，只要找到所有数都非$0$的一行或一列，就可以立刻对这一行或一列进行操作。由于要求操作数最少，所以先枚举较短的一条边，再枚举较长的一条边。

代码

#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
    if (!mode) {
        for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
        for (int i = 1; i <= m; ++i) --a[t][i];
        return true;
    } else {
        for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
        for (int i = 1; i <= n; ++i) --a[i][t];
        return true;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    p = n, q = m;
    if (p > q) {
        p ^= q ^= p ^= q;
        f = 1;
    }
    for (int i = 1; i <= p; ++i) while (check(i, f)) {
        ans[++top] = i;
        mode[top] = f;
    }
    for (int i = 1; i <= q; ++i) while (check(i, !f)) {
        ans[++top] = i;
        mode[top] = !f;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << top << endl;
    for (int i = 1; i <= top; ++i) {
        if (!mode[i]) cout << "row ";
        else cout << "col ";
        cout << ans[i] << endl;
    }
    return 0;
}