Score : $500$ points

问题描述

你被给定一个元素为非负整数的矩阵 $A$。对于一对整数 $(i, j)$，满足条件 $1 \leq i \leq H$ 和 $1 \leq j \leq W$，令 $A_{i, j}$ 表示矩阵 $A$ 中第 $i$ 行和第 $j$ 列的元素。

让我们对矩阵 $A$ 执行以下操作：

• 首先，将矩阵 $A$ 中所有值为 $0$ 的元素用任意一个 正整数 替换（若存在多个 $0$ 元素，可以替换为不同的正整数）。

• 然后，重复执行以下两种操作之一，每次可以选择，且可以执行任意多次（可能为零次）：

  • 选择一对整数 $(i, j)$ 满足条件 $1 \leq i < j \leq H$，交换矩阵 $A$ 中第 $i$ 行和第 $j$ 行。

  • 选择一对整数 $(i, j)$ 满足条件 $1 \leq i < j \leq W$，交换矩阵 $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}$。

• 换句话说，对于任意两对整数 $(i, j)$ 和 $(i', j')$，满足条件 $1 \leq i, i' \leq H$ 以及 $1 \leq j, j' \leq W$，同时满足以下两个条件：

  • 若 $i < i'$，则有 $A_{i, j} \leq A_{i', j'}$。

  • 若 $i = i'$ 且 $j < j'$，则有 $A_{i, j} \leq A_{i', j'}$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a matrix $A$ whose elements are non-negative integers. For a pair of integers $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$, let $A_{i, j}$ denote the element at the $i$-th row and $j$-th column of $A$.

Let us perform the following procedure on $A$.

• First, replace each element of $A$ that is $0$ with an arbitrary positive integer (if multiple elements are $0$, they may be replaced with different positive integers).

• Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).

  • Choose a pair of integers $(i, j)$ such that $1 \leq i \lt j \leq H$ and swap the $i$-th and $j$-th rows of $A$.
  • Choose a pair of integers $(i, j)$ such that $1 \leq i \lt j \leq W$ and swap the $i$-th and $j$-th columns of $A$.

Determine whether $A$ can be made to satisfy the following condition.

• $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}$.

• In other words, for every two pairs of integers $(i, j)$ and $(i', j')$ such that $1 \leq i, i' \leq H$ and $1 \leq j, j' \leq W$, both of the following conditions are satisfied.

  • If $i \lt i'$, then $A_{i, j} \leq A_{i', j'}$.
  • If $i = i'$ and $j \lt j'$, then $A_{i, j} \leq A_{i', j'}$.

Constraints

• $2 \leq H, W$
• $H \times W \leq 10^6$
• $0 \leq A_{i, j} \leq H \times W$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

If $A$ can be made to satisfy the condition in the problem statement, print Yes; otherwise, print No.

Sample Input 1

3 3
9 6 0
0 4 0
3 0 3

Sample Output 1

Yes

One can perform the operations as follows to make $A$ satisfy the condition in the problem statement, so you should print Yes.

• First, replace the elements of $A$ that are $0$, as shown below:

9 6 8
5 4 4
3 1 3

• Swap the second and third columns. Then, $A$ becomes:

9 8 6
5 4 4
3 3 1

• Swap the first and third rows. Then, $A$ becomes:

3 3 1
5 4 4
9 8 6

• Swap the first and third columns. Then, $A$ becomes the following and satisfies the condition in the problem statement.

1 3 3
4 4 5
6 8 9

Sample Input 2

2 2
2 1
1 2

Sample Output 2

No

There is no way to perform the operations to make $A$ satisfy the condition in the problem statement, so you should print No.

update @ 2024/3/10 11:40:40