分数: 500 点
问题陈述
给你一个矩阵 A ,其元素为非负整数。 对于一对整数 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W, 让 A_{i, j} 表示位于 i第行和 j第列 A.
让我们执行以下过程 A.
- 首先,替换每个元素 A 即 0 与任意 正整数 (如果有多个元素 0,它们可以替换为不同的正整数)。
-
然后,重复执行以下两个操作之一,每次都可以选择,根据需要多次(可能为零)。
- 选择一对整数 (i, j) 这样 1 \leq i \lt j \leq H 并交换 i-th 和 j第 行 A.
- 选择一对整数 (i, j) 这样 1 \leq i \lt j \leq W 并交换 i-th 和 j第 列 A.
判断是否 可以使 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}.
-
换句话说,对于每两对整数 (i, j) 和 (i', j') 这样 1 \leq i, i' \leq H 和 1 \leq j, j' \leq W,满足以下两个条件。 可以使
- If i \lt i',那么 A_{i, j} \leq A_{i', j'}.
- If i = i' 和 j \lt j',那么 A_{i, j} \leq A_{i', j'}.
约束
- 2 \leq H, W
- H \times W \leq 10^6
- 0 \leq A_{i, j} \leq H \times W
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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}
输出
If A 满足问题陈述中的条件,打印 Yes;否则,打印 No.
示例输入 1
3 3 9 6 0 0 4 0 3 0 3
示例输出 1
Yes
可以执行如下操作来使 A 满足问题陈述中的条件,因此您应该打印 Yes.
- 首先,替换元素 A 是 0,如下图:
9 6 8 5 4 4 3 1 3
- 交换第二列和第三列。然后, A 变为:
9 8 6 5 4 4 3 3 1
- 交换第一行和第三行。然后, A 变为:
3 3 1 5 4 4 9 8 6
- 交换第一列和第三列。然后, A 变为以下内容并满足问题陈述中的条件。
1 3 3 4 4 5 6 8 9
示例输入 2
2 2 2 1 1 2
示例输出 2
No
无法执行使 A 满足问题陈述中的条件,因此您应该打印 No.