Sorting a Matrix

题目描述

给出一个矩阵 $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 \lt j \leq H$ 的整数对 $(i, j)$，并交换矩阵 $A$ 的第 $i$ 行和第 $j$ 行。 选择满足 $1 \leq i \lt 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 \lt i'$，那么 $A_{i, j} \leq A_{i', j'}$。 如果 $i = i'$ 且 $j \lt 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$。

3 3
9 6 0
0 4 0
3 0 3

Yes

9 6 8
5 4 4
3 1 3

9 8 6
5 4 4
3 3 1

3 3 1
5 4 4
9 8 6

1 3 3
4 4 5
6 8 9

2 2
2 1
1 2

No

提示

$2 \leq H, W$ $H \times W \leq 10^6$ $0 \leq A_{i, j} \leq H \times W$ 输入中的所有值均为整数。可以按如下操作使 $A$ 满足题目陈述中的条件，因此应该输出 $Yes$。

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

交换第 2 列和第 3 列。此时 $A$ 变为：

交换第 1 行和第 3 行。此时 $A$ 变为：

交换第 1 列和第 3 列。此时 $A$ 变为下列矩阵并满足题目陈述中的条件。
不存在任何操作方法可以使 $A$ 满足题目陈述中的条件，因此应该输出 $No$。

标签: AtCoder|abc277F

来源

AtCoder|abc277F