← 返回题目列表

AtCoder · abc277_f

I. 对矩阵进行排序

中文机器翻译题面 查看原题

分数: 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.