Giả sử, có hai ảnh vuông n * n pixel thứ nhất và thứ hai. Các pixel có thể là màu đen hoặc trắng. Các hình ảnh được đưa ra dưới dạng biểu diễn ma trận, trong đó nếu một pixel có màu đen thì nó được biểu thị là 'x' và nếu là màu trắng, nó được biểu thị là '.'. Chúng tôi phải kiểm tra hình ảnh thứ hai khớp với hình ảnh đầu tiên sau khi xoay 90 ° và dịch. Nếu đúng, chúng tôi trả về true, ngược lại, chúng tôi trả về false.
Vì vậy, nếu đầu vào là n =4, đầu tiên ={"..x.", "X.x.", "x.xx", "xx .."}, thứ hai ={"..xx", "x. xx "," .x.x "," ..x. "}, thì kết quả đầu ra sẽ là False.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
Define a function find(), this will take an array of pairs x, an array of pairs y,
d1 := first value of y[0] - first value of x[0]
d2 := second value of y[1] - second value of x[1]
for initialize i := 1, when i < size of x, update (increase i by 1), do:
if first value of y[i] - first value of x[i] is not equal to d1 or second value of y[i] - second value of x[i] is not equal to d2, then:
return false
return true
Define a function rotate(), this will take n, an array of pairs a, an array of pairs b,
for initialize i := 0, when i < size of b, update (increase i by 1), do:
b[i] := make_pair(second value of b[i], n - first value of b[i] - 1)
Define two arrays a, b that can contain integer pairs
for initialize i := 0, when i < n, update (increase i by 1), do:
s := first[i]
for initialize j := 0, when j < n, update (increase j by 1), do:
if s[j] is same as 'x', then:
insert pair(i, j) at the end of a
for initialize i := 0, when i < n, update (increase i by 1), do:
s := second[i]
for initialize j := 0, when j < n, update (increase j by 1), do:
if s[j] is same as 'x', then:
insert pair(i, j) at the end of b
if size of a is not equal to size of b, then:
return false
if size of a is same as 0, then:
return true
check := false
sort the array a
for initialize i := 0, when i < 4, update (increase i by 1), do:
sort the array b
if find(a, b), then:
check := true
rotate(n, a, b)
if check is true, then:
return true
Otherwise
return false Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
bool find(vector<pair<int, int>> x, vector<pair<int, int>> y){
int d1 = y[0].first - x[0].first;
int d2 = y[1].second - x[1].second;
for(int i = 1; i < x.size(); i++){
if(y[i].first - x[i].first != d1 || y[i].second - x[i].second != d2){
return false;
}
}
return true;
}
void rotate(int n, vector<pair<int, int>> a, vector<pair<int, int>> b){
for(int i = 0; i < b.size(); i++){
b[i] = make_pair(b[i].second, n - b[i].first - 1);
}
}
bool solve(int n, vector<string> first, vector<string> second){
vector<pair<int, int>> a, b;
for(int i = 0; i < n; i++){
string s = first[i];
for(int j = 0; j < n; j++){
if(s[j] == 'x'){
a.push_back(make_pair(i, j));
}
}
}
for(int i = 0; i < n; i++){
string s = second[i];
for(int j = 0; j < n; j++){
if(s[j] == 'x'){ b.push_back(make_pair(i,j));
}
}
}
if(a.size() != b.size()){
return false;
}
if(a.size() == 0){
return true;
}
bool check = false;
sort(a.begin(),a.end());
for(int i = 0; i < 4; i++){
sort(b.begin(),b.end());
if(find(a,b)){
check = true;
}
rotate(n, a, b);
}
if(check){
return true;
}else{
return false;
}
}
int main() {
int n = 4; vector<string> first = {"..x.", "x.x.", "x.xx", "xx.."}, second = {"..xx", "x.xx", ".x.x", "..x."};
cout<< solve(n, first, second);
return 0;
} Đầu vào
4, {"..x.", "x.x.", "x.xx", "xx.."}, {"..xx", "x.xx", ".x.x", "..x."}
Đầu ra
0