Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 298 B問題 Coloring Matrix

AtCoder ABC ABC298 B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

各要素が $0$ か $1$ である $N$ 行 $N$ 列の行列 $A,B$ が与えられる.

$A$ に何回か回転を施すことで, 以下を満たすようにできるか?

任意の $1$ 以上 $N$ 以下の整数 $i,j$ に対して, $A_{i,j} \Rightarrow B_{i,j}$ が成り立つ.

なお, $N$ 行 $N$ 列の行列 $X$ を回転した行列とは, 次のようにして定義される.

回転後の $i$ 行 $j$ 列の要素は $X_{N+1-j,i}$ である.

制約

$1 \leq N \leq 100$
$A_{i,j}, B_{i,j} \in \{0,1\}$

解法

行列を $4$ 回行うと, 元の行列と一致するので, 行列の回転の回数は $0,1,2,3$ のどれかであるとしてもよい.

各場合について, 実際に条件を満たすかどうかを判定すれば良い.

ここで, Python において, 行列 $A$ の回転は次のように記述することで, $1$ 行で記述できる.

A=[list(a)[::-1] for a in zip(*A)]