题目描述
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; }