মান লিখুন: h x w ডাইমেনশনের একটি ম্যাট্রিক্স দেওয়া আছে। ম্যাট্রিক্সে ইংরেজি অক্ষর আছে। আমাদের আরেকটি ম্যাট্রিক্স তৈরি করতে হবে যাতে প্রতিটি সারি এবং কলাম প্যালিনড্রোম হয়। এর জন্য দেওয়া ম্যাট্রিক্সের সারি ও কলাম যেকোনোভাবে রিঅ্যারেঞ্জ করা যাবে; কিন্তু কোনো এলিমেন্ট পরিবর্তন করা যাবে না (অর্থাৎ 'a' কে 'b' বানানো যাবে না)। যদি প্যালিনড্রোমিক ম্যাট্রিক্স তৈরি করা সম্ভব হয়, তবে true রিটার্ন করুন, অন্যথায় false।
উদাহরণ
যদি ইনপুট হয় h = 4, w = 4, mat = {"xxyy", "xyxx", "yxxy", "xyyy"}, তবে আউটপুট হবে true।
সমাধানের ধাপসমূহ
mp ম্যাপ
count অ্যারে (আকার ৪)
for i := 0 থেকে h-1:
for j := 0 থেকে w-1:
mp[mat[i][j]]++
mp-এর প্রতিটি value val এর জন্য:
count[val % 4]++
check := true
যদি h%2==0 এবং w%2==0:
যদি count[1]+count[2]+count[3] > 0: check := false
অন্যথায় যদি h%2==1 এবং w%2==1:
যদি count[1]+count[3] > 1: check := false
অন্যথায় যদি count[2] > h/2 + w/2: check := false
অন্যথায়:
যদি count[1]+count[3] > 0: check := false
অন্যথায় যদি h%2==1 এবং count[2] > w/2: check := false
অন্যথায় যদি w%2==1 এবং count[2] > h/2: check := false
check রিটার্ন করুন
C++ বাস্তবায়ন
#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
