AT_abc277_f [ABC277F] Sorting a Matrix

题目描述

给定一个 $H$ 行 $W$ 列、元素为非负整数的矩阵 $A$。对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$，$A$ 的第 $i$ 行第 $j$ 列的元素记为 $A_{i, j}$。

对 $A$ 可以进行如下操作：

• 首先，将 $A$ 中所有为 $0$ 的元素分别替换为任意正整数（如果有多个 $0$，可以分别替换为不同的正整数）。
• 然后，可以任意次（也可以不进行）执行以下两种操作中的任意一种：
  • 选择满足 $1 \leq i < j \leq H$ 的整数对 $(i, j)$，交换 $A$ 的第 $i$ 行和第 $j$ 行。
  • 选择满足 $1 \leq i < j \leq W$ 的整数对 $(i, j)$，交换 $A$ 的第 $i$ 列和第 $j$ 列。

请判断是否可以通过上述操作，使得 $A$ 满足以下条件：

• $A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}$
• 换句话说，对于任意满足 $1 \leq i, i' \leq H$ 且 $1 \leq j, j' \leq W$ 的两个整数对 $(i, j)$ 和 $(i', j')$，都满足以下两个条件：
  • 如果 $i < i'$，则 $A_{i, j} \leq A_{i', j'}$。
  • 如果 $i = i'$ 且 $j < j'$，则 $A_{i, j} \leq A_{i', j'}$。

输入格式

输入按以下格式从标准输入读入。

$H$ $W$ $A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

输出格式

如果可以使 $A$ 满足题目中的条件，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3 3
9 6 0
0 4 0
3 0 3

输出 #1

Yes

输入输出样例 #2

输入 #2

2 2
2 1
1 2

输出 #2

No

说明/提示

限制

• $2 \leq H, W$
• $H \times W \leq 10^6$
• $0 \leq A_{i, j} \leq H \times W$
• 输入均为整数

样例解释 1

可以通过如下步骤操作，使 $A$ 满足题目中的条件，因此输出 Yes。

• 首先，将 $A$ 中的 $0$ 元素替换如下：

  9 6 8
  5 4 4
  3 1 3
  

• 交换第 2 列和第 3 列，结果如下：

  9 8 6
  5 4 4
  3 3 1
  

• 交换第 1 行和第 3 行，结果如下：

  3 3 1
  5 4 4
  9 8 6
  

• 交换第 1 列和第 3 列，结果如下，满足题目条件：

  1 3 3
  4 4 5
  6 8 9
  

样例解释 2

无论如何操作，都无法使 $A$ 满足题目中的条件，因此输出 No。

由 ChatGPT 4.1 翻译