मान लीजिए, हमें h x w आयामों वाला एक मैट्रिक्स दिया गया है। मैट्रिक्स में अंग्रेजी अक्षर हैं। हमें एक और मैट्रिक्स बनाना है जिसमें पैलिंड्रोमिक पंक्तियां और कॉलम हों, यानी प्रत्येक पंक्ति और कॉलम पैलिंड्रोम होंगे। ऐसा करने के लिए, दिए गए मैट्रिक्स से पंक्तियों और कॉलम की कोई भी व्यवस्था की जा सकती है; लेकिन कोई तत्व बदला नहीं जा सकता, यानी 'a' को 'b' में नहीं बदला जा सकता। यदि दिए गए मैट्रिक्स से पैलिंड्रोमिक मैट्रिक्स बनाना संभव है, तो हम true वापस करते हैं; अन्यथा, हम false वापस करते हैं।
उदाहरण के लिए, यदि इनपुट h = 4, w = 4, mat = {"xxyy", "xyxx", "yxxy", "xyyy"} है, तो आउटपुट true होगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
एक मैप mp परिभाषित करें आकार 4 का एक ऐरे count परिभाषित करें। i := 0 से h-1 तक, करें: j := 0 से w-1 तक, करें: tp[mat[i, j]] बढ़ाएं tp के प्रत्येक मान val के लिए, करें: count[val का दूसरा मान mod 4] बढ़ाएं check := true यदि h mod 2, 0 के बराबर है और w mod 2, 0 के बराबर है, तो: यदि count[1] + count[2] + count[3] > 0, तो: check := false अन्यथा जब h mod 2, 1 के बराबर है और w mod 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 mod 2, 1 के बराबर है और count[2] > w / 2, तो: check := false अन्यथा जब w mod 2, 1 के बराबर है और count[2] > h / 2, तो: check := false 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
