CF1231C.Increasing Matrix

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在本题中，如果一个 $n \times m$ 的矩阵 $a$ 满足：对于每一行 $i$ ，从左到右元素严格递增（即 $a_{i,1} < a_{i,2} < \dots < a_{i,m}$ ）；对于每一列 $j$ ，从上到下元素严格递增（即 $a_{1,j} < a_{2,j} < \dots < a_{n,j}$ ），则称该矩阵为递增矩阵。

现给定一个只包含非负整数的矩阵，需要将其中所有的 $0$ 替换为某个正整数，使得最终得到的矩阵是递增矩阵，并且矩阵所有元素之和最大。如果无法做到，输出 $-1$ 。

保证所有 $0$ 只出现在内部单元格（即不在第一行、最后一行、第一列、最后一列）。

输入格式

第一行包含两个整数 $n$ 和 $m$ （ $3 \le n, m \le 500$ ），表示矩阵 $a$ 的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个非负整数，表示矩阵的每一行： $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ （ $0 \le a_{i,j} \le 8000$ ）。

保证所有 $a_{i,j}=0$ 的位置都满足 $1 < i < n$ 且 $1 < j < m$ 。

输出格式

如果可以将所有 $0$ 替换为正整数，使得矩阵递增，则输出矩阵元素和的最大值。否则输出 $-1$ 。

输入输出样例

输入#1

4 5
1 3 5 6 7
3 0 7 0 9
5 0 0 0 10
8 9 10 11 12

输出#1

输入#2
```
3 3
1 2 3
2 0 4
4 5 6
```
输出#2
```
30
```
输入#3
```
3 3
1 2 3
3 0 4
4 5 6
```
输出#3
```
-1
```
输入#4
```
3 3
1 2 3
2 3 4
3 4 2
```
输出#4
```
-1
```

说明/提示

在第一个样例中，最终矩阵如下：

1 3 5 6 7
3 6 7 8 9
5 7 8 9 10
8 9 10 11 12

在第二个样例中，中间的单元格必须填 $3$ 。

在第三个样例中，不存在满足条件的矩阵。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页