AT_abc298_b [ABC298B] Coloring Matrix

题目描述

给定两个 $N$ 行 $N$ 列的矩阵 $A$ 和 $B$，每个元素均为 $0$ 或 $1$。
用 $A_{i,j}$ 表示 $A$ 的第 $i$ 行第 $j$ 列的元素，用 $B_{i,j}$ 表示 $B$ 的第 $i$ 行第 $j$ 列的元素。
请判断是否可以通过适当旋转 $A$，使得对于所有满足 $A_{i,j}=1$ 的整数对 $(i,j)$，都有 $B_{i,j}=1$。
这里，旋转 $A$ 指的是可以任意多次（也可以不旋转）重复以下操作：

• 对于所有满足 $1 \leq i, j \leq N$ 的整数对 $(i, j)$，同时将 $A_{i,j}$ 替换为 $A_{N+1-j,i}$。

输入格式

输入以如下格式从标准输入读入。

$N$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$
$B_{1,1}$ $B_{1,2}$ $\ldots$ $B_{1,N}$
$\vdots$
$B_{N,1}$ $B_{N,2}$ $\ldots$ $B_{N,N}$

输出格式

如果可以通过适当旋转 $A$，使得对于所有 $A_{i,j}=1$ 的位置都有 $B_{i,j}=1$，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

输出 #1

Yes

输入输出样例 #2

输入 #2

2
0 0
0 0
1 1
1 1

输出 #2

Yes

输入输出样例 #3

输入 #3

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

输出 #3

No

说明/提示

约束条件

• $1 \leq N \leq 100$
• $A$ 和 $B$ 的每个元素都是 $0$ 或 $1$
• 输入均为整数

样例解释 1

初始时，$A$ 为

0 1 1
1 0 0
0 1 0

旋转 $1$ 次后，$A$ 变为

0 1 0
1 0 1
0 0 1

再旋转 $1$ 次后，$A$ 变为

0 1 0
0 0 1
1 1 0

此时，对于所有 $A_{i,j}=1$ 的位置，$B_{i,j}=1$ 都成立，因此输出 Yes。

由 ChatGPT 4.1 翻译