Score : $200$ points

问题描述

给定两个 $N$×$N$ 的矩阵 $A$ 和 $B$，其中每个元素为0或1。

令 $A_{i,j}$ 和 $B_{i,j}$ 分别表示矩阵 $A$ 和 $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}$。

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

Problem Statement

You are given $N$-by-$N$ matrices $A$ and $B$ where each element is $0$ or $1$.
Let $A_{i,j}$ and $B_{i,j}$ denote the element at the $i$-th row and $j$-th column of $A$ and $B$, respectively.
Determine whether it is possible to rotate $A$ so that $B_{i,j} = 1$ for every pair of integers $(i, j)$ such that $A_{i,j} = 1$.
Here, to rotate $A$ is to perform the following operation zero or more times:

• for every pair of integers $(i, j)$ such that $1 \leq i, j \leq N$, simultaneously replace $A_{i,j}$ with $A_{N + 1 - j,i}$.

Constraints

• $1 \leq N \leq 100$
• Each element of $A$ and $B$ is $0$ or $1$.
• All values in the input are integers.

Input

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

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

Output

If it is possible to rotate $A$ so that $B_{i,j} = 1$ for every pair of integers $(i, j)$ such that $A_{i,j} = 1$, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

Initially, $A$ is :

0 1 1
1 0 0
0 1 0

After performing the operation once, $A$ is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, $A$ is :

0 1 0
0 0 1
1 1 0

Here, $B_{i,j} = 1$ for every pair of integers $(i, j)$ such that $A_{i,j} = 1$, so you should print Yes.

Sample Input 2

2
0 0
0 0
1 1
1 1

Sample Output 2

Yes

Sample Input 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

Sample Output 3

No

update @ 2024/3/10 12:21:40