मान लीजिए दो n × n पिक्सेल वर्ग छवियाँ first और second हैं। पिक्सेल या तो काले या सफेद हो सकते हैं। छवियों को मैट्रिक्स प्रतिनिधित्व में दिया गया है जहाँ काला पिक्सेल 'x' से और सफेद पिक्सेल '.' से दर्शाया जाता है। हमें जाँचना है कि second छवि 90° घूर्णन और अनुवाद के बाद first छवि से मेल खाती है या नहीं। यदि हाँ तो true लौटाएँ, अन्यथा false।
उदाहरण के लिए, यदि इनपुट है n = 4, first = {"..x.", "x.x.", "x.xx", "xx.."}, second = {"..xx", "x.xx", ".x.x", "..x."}, तो आउटपुट False होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक फंक्शन find() परिभाषित करें जो युग्मों की सरणी x, y लेता है:
d1 := y[0].first - x[0].first
d2 := y[1].second - x[1].second
i := 1 से x के आकार-1 तक:
यदि y[i].first - x[i].first != d1 या y[i].second - x[i].second != d2, तो:
false लौटाएँ
true लौटाएँ
एक फंक्शन rotate() परिभाषित करें जो n, युग्मों की सरणी a, b लेता है:
i := 0 से b के आकार-1 तक:
b[i] := make_pair(b[i].second, n - b[i].first - 1)
दो सरणी a, b परिभाषित करें जो पूर्णांक युग्म रख सकें
i := 0 से n-1 तक:
s := first[i]
j := 0 से n-1 तक:
यदि s[j] == 'x', तो:
युग्म (i, j) को a के अंत में डालें
i := 0 से n-1 तक:
s := second[i]
j := 0 से n-1 तक:
यदि s[j] == 'x', तो:
युग्म (i, j) को b के अंत में डालें
यदि a का आकार != b का आकार, तो false लौटाएँ
यदि a का आकार == 0, तो true लौटाएँ
check := false
a सरणी को सॉर्ट करें
i := 0 से 3 तक:
b सरणी को सॉर्ट करें
यदि find(a, b), तो:
check := true
rotate(n, a, b)
यदि check सत्य है, तो true लौटाएँ अन्यथा 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