Xoay ma trận

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Cho hai ma trận \(A\) và \(B\) cùng có kích thước \(N\times N\). Các phần tử của hai ma trận chỉ bằng \(0\) hoặc bằng \(1\).

Ta quy ước \(A_{i,j}\) và \(B_{i,j}\) lần lượt là phần tử nằm ở ô giao giữa hàng thứ \(i\) với cột thứ \(j\) của \(A\) và \(B\).

Ma trận \(A\) được tính là tương đồng với ma trận \(B\) nếu \(B_{i,j}=1\) với mọi cặp chỉ số \((i,j)\) thỏa mãn \(A_{i,j}=1\).

Bạn hãy viết chương trình kiểm tra xem ta có thể đưa ma trận \(A\) về trạng thái tương đồng với ma trận \(B\) bằng cách xoay \(A\) một số lần hữu hạn (có thể bằng \(0\)) hay không? Biết rằng sau mỗi lần xoay, mọi phần tử \(A_{i,j}\) sẽ được thay bởi phần tử \(A_{N-j+1,i}\).

Input
  • Dòng đầu chứa số nguyên dương \(N\) \((1\le N\le 100)\).
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa \(N\) số nguyên mô tả các phần tử nằm ở hàng thứ \(i\) của ma trận \(A\). Các phần tử chỉ có thể bằng \(0\) hoặc \(1\).
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa \(N\) số nguyên mô tả các phần tử nằm ở hàng thứ \(i\) của ma trận \(B\). Các phần tử chỉ có thể bằng \(0\) hoặc \(1\).
Output
  • In ra Yes nếu ta có thể xoay ma trận \(A\) một số lần hữu hạng để nó trở nên tương đồng với ma trận \(B\). Ngược lại, in ra No.
Ví dụ
Sample input 01
3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1
Sample output 01
Yes
Giải thích

Ở trạng thái đầu tiên, các phần tử của \(A\) là:

0 1 1
1 0 0
0 1 0

Sau khi xoay một lần, \(A\) trở thành:

0 1 0
1 0 1 
0 0 1

Sau khi xoay tiếp một lần nữa, \(A\) trở thành:

0 1 0
0 0 1
1 1 0

Ở trạng thái này, \(B_{i,j}=1\) với mọi cặp chỉ số \((i,j)\) sao cho \(A_{i,j}=1\), nên câu trả lời là Yes.

Sample input 02
2
0 0
0 0
1 1
1 1
Sample output 02
Yes
Sample input 03
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 03
No