मान लीजिए, पहले और दूसरे दो n * n पिक्सेल वर्ग चित्र हैं। पिक्सल या तो काला या सफेद हो सकता है। छवियों को एक मैट्रिक्स प्रतिनिधित्व में दिया जाता है जहां यदि एक पिक्सेल काला है तो इसे 'x' के रूप में दर्शाया जाता है और यदि यह सफेद है, तो इसे '.' के रूप में दर्शाया जाता है। हमें 90° घुमावों और अनुवादों के बाद पहली छवि के साथ दूसरी छवि मिलान की जांच करनी होगी। अगर ऐसा होता है तो हम सही लौटते हैं, अन्यथा हम झूठे लौटते हैं।
इसलिए, यदि इनपुट n =4 जैसा है, तो पहला ={"..x", "x.x.", "x.xx", "xx.."}, दूसरा ={"..xx", "x. xx", ".x.x", "..x"}, तो आउटपुट गलत होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-
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 उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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;
} इनपुट
4, {"..x.", "x.x.", "x.xx", "xx.."}, {"..xx", "x.xx", ".x.x", "..x."}
आउटपुट
0