ধরুন, আমাদেরকে h x w এর মাত্রা সহ একটি ম্যাট্রিক্স দেওয়া হয়েছে। ম্যাট্রিক্সে ইংরেজি অক্ষর থাকে। আমাদের আরেকটি ম্যাট্রিক্স তৈরি করতে হবে যাতে প্যালিনড্রোমিক সারি এবং কলাম থাকবে, অর্থাৎ প্রতিটি সারি এবং কলাম হবে প্যালিনড্রোম। এটি করার জন্য, প্রদত্ত ম্যাট্রিক্স থেকে সারি এবং কলামগুলির যে কোনও বিন্যাস করা যেতে পারে; কিন্তু কোনো উপাদান পরিবর্তন করা যাবে না, যেমন একটি 'a' পরিবর্তন করে 'b' করা যাবে না। যদি প্রদত্ত ম্যাট্রিক্স থেকে একটি প্যালিনড্রোমিক ম্যাট্রিক্স তৈরি করা সম্ভব হয়, আমরা সত্য ফেরত দিই; অথবা অন্যথায়, আমরা মিথ্যা ফেরত দিই।
সুতরাং, যদি ইনপুটটি h =4, w =4, mat ={"xxyy", "xyxx", "yxxy", "xyyy"} হয়, তাহলে আউটপুটটি সত্য হবে।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one map mp
Define an array count of size 4.
for initialize i := 0, when i < h, update (increase i by 1), do:
for initialize j := 0, when j < w, update (increase j by 1), do:
(increase tp[mat[i, j]] by 1)
for each value val in tp, do:
increase count[second value of val mod 4] by 1
check := true
if h mod 2 is same as 0 and w mod 2 is same as 0, then:
if count[1] + count[2] + count[3] > 0, then:
check := false
otherwise when h mod 2 is same as 1 and w mod 2 is same as 1, then:
if count[1] + count[3] > 1, then:
check := false
otherwise when count[2] > h / 2 + w / 2, then:
check := false
Otherwise
if count[1] + count[3] > 0, then:
check := false
otherwise when h mod 2 is same as 1 and count[2] > w / 2, then:
check := false
otherwise when w mod 2 is same as 1 and count[2] > h / 2, then:
check := false
return check উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
bool solve(int h, int w, vector<string> mat){
map<char, int> tp;
vector<int> count(4);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j)
tp[mat[i][j]]++;
}
for (auto val : tp)
count[val.second % 4]++;
bool check = true;
if (h % 2 == 0 && w % 2 == 0) {
if (count[1] + count[2] + count[3] > 0)
check = false;
}
else if (h % 2 == 1 && w % 2 == 1) {
if (count[1]+count[3] > 1)
check = false;
else if (count[2] > h / 2 + w / 2)
check = false;
} else {
if (count[1] + count[3] > 0)
check = false;
else if (h % 2 == 1 && count[2] > w / 2)
check = false;
else if (w % 2 == 1 && count[2] > h / 2)
check = false;
}
return check;
}
int main() {
int h = 4, w = 4;
vector<string> mat = {"xxyy", "xyxx", "yxxy", "xyyy"};
cout<< solve(h, w, mat);
return 0;
} ইনপুট
4, 4, {"xxyy", "xyxx", "yxxy", "xyyy"} আউটপুট
1
