Official

B - Coloring Matrix Editorial by cn449


行列に対して \(4\) 回操作を行うと元の状態に戻ります。
したがって、\(A\) を回転して得られる行列としてあり得るものは高々 \(4\) 種類です。具体的には、\(A\) に対し \(0\) 回以上 \(3\) 回以下の操作を行ったもののみ考えればよいことがわかります。
よって \(A\) を回転して得られる行列としてあり得るものすべてに対し、\(A_{i,j} = 1\) のとき \(B_{i,j} = 1\) が成り立っているかを調べればよいです。
行列の添え字を \(0\) から始めている場合、問題文中に書いてある操作とプログラム上の添え字が一致しないことに注意してください。

実装例

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> rotate(vector<vector<int>> a) {
	int n = a.size();
	vector<vector<int>> res(n, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[j][n - 1 - i] = a[i][j];
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
	vector<vector<int>> b(n, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> b[i][j];
	for (int _ = 0; _ < 4; _++) {
		bool ok = true;
		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] == 1 && b[i][j] == 0) ok = false;
		if (ok) {
			cout << "Yes\n";
			return 0;
		}
		a = rotate(a);
	}
	cout << "No\n";
}

posted:
last update: