← 返回题目列表

Codeforces · 1136/C

C. Nastya 正在转置矩阵

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

Nastya 来上她的信息学课,顺便说一下,她的老师在这里有点名气,给了她以下任务。

给出两个矩阵 $$$A$$$ 和 $$$B$$$,每个矩阵的大小为 $$$n \times m$$$。 Nastya 可以对矩阵 $$$A$$$ 执行以下操作无限次:

- 取 $$$A$$$ 的任意方方子矩阵并将其转置(即子矩阵中位于 $$$i$$$ 行和 $$$j$$$ 列的子矩阵转置后将位于 $$$j$$$ 行和 $$$i$$$ 列,转置后的子矩阵本身将保留其在矩阵中的位置$$$A$$$)。

Nastya 的任务是检查是否可以将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$。

操作示例

由于可能需要大量操作,因此请您为 Nastya 回答这个问题。

矩阵 $$$M$$$ 的方子矩阵是由来自矩阵 $$$M$$$ 的索引为 $$$x, x+1, \dots, x+k-1$$$ 的行之一以及来自矩阵的索引为 $$$y, y+1, \dots, y+k-1$$$ 的列之一的所有元素组成的矩阵$$$M$$$。 $$$k$$$ 是方形子矩阵的大小。换句话说,正方形子矩阵是形成实心正方形(即没有孔)的源矩阵元素的集合。

输入

第一行包含两个以空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 500$$$) - 分别是 $$$A$$$ 和 $$$B$$$ 中的行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,这些行中第 $$$i$$$ 中的第 $$$j$$$ 数字表示矩阵 $$$A$$$ 第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$1 \leq A_{ij} \leq 10^{9}$$$)。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数,这些行中第 $$$i$$$ 中的第 $$$j$$$ 数字表示矩阵 $$$B$$$ 第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$1 \leq B_{ij} \leq 10^{9}$$$)。

输出

如果可以将 $$$A$$$ 转换为 $$$B$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

2 2
1 1
6 1
1 6
1 1

输出 #1

YES

输入 #2

2 2
4 4
4 5
5 4
4 4

输出 #2

NO

输入 #3

3 3
1 2 3
4 5 6
7 8 9
1 4 7
2 5 6
3 8 9

输出 #3

YES

注意

考虑第三个例子。矩阵 $$$A$$$ 最初看起来如下。

$$$$$$ \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{bmatrix} $$$$$$

然后我们选择整个矩阵作为转置子矩阵,它变成

$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 8\\ 3 & 6 & 9 \end{bmatrix} $$$$$$

然后我们转置单元格 $$$(2, 2)$$$ 和 $$$(3, 3)$$$ 中带有角点的子矩阵。

$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & \textbf{5} & \textbf{8}\\ 3 & \textbf{6} & \textbf{9} \end{bmatrix} $$$$$$

所以矩阵变成

$$$$$$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 6\\ 3 & 8 & 9 \end{bmatrix} $$$$$$

是$$$B$$$。