#2723. [ABC264C] 矩阵缩减(Matrix Reducing)

    ID: 2723 Type: Default 1000ms 256MiB Tried: 2 Accepted: 2 Difficulty: 10 Uploaded By: Tags>ABC入门算法闯关算法设计策略STL与数据结构

[ABC264C] 矩阵缩减(Matrix Reducing)

题目描述

给定一个矩阵 AA 有 H1H_1 行和 W1W_1列,以及一个矩阵 BB 有 H2H_2 行和 W2W_2 列。

  • 对于所有满足 1 ≤ i ≤ H1 1\ \leq\ i\ \leq\ H_1 且 1 ≤ j ≤ W1 1\ \leq\ j\ \leq\ W_1 的整数对 (i, j) (i,\ j) ,矩阵 AA 的第 ii 行第 jj 列的元素为 Ai,j A_{i,j} 。
  • 对于所有满足 1 ≤ i ≤ H2 1\ \leq\ i\ \leq\ H_2 且 1 ≤ j ≤ W2 1\ \leq\ j\ \leq\ W_2 的整数对 (i, j) (i,\ j) ,矩阵 BB 的第 ii 行第 jj 列的元素为 Bi,jB_{i,j}。 你可以对矩阵 AA 执行以下操作任意次(可能为 00 次):
  • 选择 A A 的任意一行并删除它。
  • 选择 AA 的任意一列并删除它。

判断是否可能通过这些操作使矩阵 AA 等于矩阵 BB 。

输入格式

输入按以下格式从标准输入给出:

H1 H_1 W1 W_1

A1, 1 A_{1,\ 1} A1, 2 A_{1,\ 2} … \ldots A1, W1 A_{1,\ W_1}

A2, 1 A_{2,\ 1} A2, 2 A_{2,\ 2} … \ldots A2, W1 A_{2,\ W_1}

⋮ \vdots

AH1, 1 A_{H_1,\ 1} AH1, 2 A_{H_1,\ 2} … \ldots AH1, W1 A_{H_1,\ W_1}

H2 H_2 W2 W_2

B1, 1 B_{1,\ 1} B1, 2 B_{1,\ 2} … \ldots B1, W2 B_{1,\ W_2}

B2, 1 B_{2,\ 1} B2, 2 B_{2,\ 2} … \ldots B2, W2 B_{2,\ W_2}

⋮ \vdots

BH2, 1 B_{H_2,\ 1} BH2, 2 B_{H_2,\ 2} … \ldots BH2, W2 B_{H_2,\ W_2}

输出格式

如果可以使矩阵 AA 等于矩阵 BB,则输出 Yes;否则输出 No。

注意判断是区分大小写的。

样例

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19
Yes
3 3
1 1 1
1 1 1
1 1 1
1 1
2
No

提示

样例说明 1

从初始的 AA 中删除第 22 列得到:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

然后从 AA 中删除第 33 行得到:

1 3 4 5
6 8 9 10
16 18 19 20

然后从 AA 中删除第 11 行得到:

6 8 9 10
16 18 19 20

然后从 AA 中删除第 44 列得到:

6 8 9
16 18 19

现在矩阵等于矩阵 BB 。 因此,我们可以通过重复这些操作使矩阵 AA 等于矩阵 BB,所以应该输出 Yes。

样例说明 2

无论如何执行操作,我们都无法使矩阵 AA 等于矩阵 BB,所以应该输出 No。

数据范围

  • 1 ≤ H2 ≤ H1 ≤ 10 1\ \leq\ H_2\ \leq\ H_1\ \leq\ 10
  • 1 ≤ W2 ≤ W1 ≤ 10 1\ \leq\ W_2\ \leq\ W_1\ \leq\ 10
  • 1 ≤ Ai, j ≤ 109 1\ \leq\ A_{i,\ j}\ \leq\ 10^9
  • 1 ≤ Bi, j ≤ 109 1\ \leq\ B_{i,\ j}\ \leq\ 10^9
  • 所有输入值都是整数。