মান লিজিয়ে, দুটি n × n পিক্সেলের বর্গাকার ইমেজ আছে first এবং second। পিক্সেলগুলো কালো বা সাদা হতে পারে। ইমেজগুলো ম্যাট্রিক্স আকারে দেওয়া আছে যেখানে কালো পিক্সেল 'x' এবং সাদা পিক্সেল '.' দিয়ে দেখানো হয়েছে। আমাদের লক্ষ্য হলো second ইমেজটি কি 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-র আকার-১ পর্যন্ত: if y[i].first - x[i].first != d1 বা y[i].second - x[i].second != d2, তবে: return false return true rotate() ফাংশন সংজ্ঞায়িত করুন, যা n, a, b পেয়ার অ্যারে গ্রহণ করবে: i := 0 থেকে b-র আকার-১ পর্যন্ত: 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 পর্যন্ত: if s[j] == 'x', তবে: a-র শেষে pair(i, j) যোগ করুন i := 0 থেকে n-1 পর্যন্ত: s := second[i] j := 0 থেকে n-1 পর্যন্ত: if s[j] == 'x', তবে: b-র শেষে pair(i, j) যোগ করুন if a-র আকার != b-র আকার, তবে: return false if a-র আকার == 0, তবে: return true check := false a অ্যারে সোর্ট করুন i := 0 থেকে ৩ পর্যন্ত: b অ্যারে সোর্ট করুন if find(a, b), তবে: check := true rotate(n, a, b) if check সত্য, তবে: return true অন্যথায়: 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
