Coloring Matrix

题目描述

给定大小为 $N$-by-$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}$。

输入格式

输入从标准输入按以下格式给出： $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$ 的整数对 $(i, j)$ 都有 $B_{i,j} = 1$，则输出 $Yes$；否则，输出 $No$。

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

Yes

0 1 1
1 0 0
0 1 0

0 1 0
1 0 1 
0 0 1

0 1 0
0 0 1
1 1 0

2
0 0
0 0
1 1
1 1

Yes

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

No

提示

$1 \leq N \leq 100$ 矩阵 $A$ 和 $B$ 的每个元素为 $0$ 或 $1$。 输入中的所有数值均为整数。最初，$A$ 为：

在执行一次该操作之后，$A$ 为：

再次执行一次该操作之后，$A$ 为：

此时，对于所有满足 $A_{i,j} = 1$ 的整数对 $(i, j)$ 都有 $B_{i,j} = 1$，因此应输出 $Yes$。

标签: AtCoder|abc298B

来源

AtCoder|abc298B