सी ++ प्रोग्राम यह पता लगाने के लिए कि क्या किसी दिए गए मैट्रिक्स से पैलिंड्रोमिक मैट्रिक्स बनाया जा सकता है

मान लीजिए, हमें आयाम h x w के साथ एक मैट्रिक्स दिया गया है। मैट्रिक्स में अंग्रेजी अक्षर हैं। हमें एक और मैट्रिक्स बनाना होगा जिसमें पैलिंड्रोमिक रो और कॉलम होंगे, यानी प्रत्येक पंक्ति और कॉलम पैलिंड्रोम होंगे। ऐसा करने के लिए, दिए गए मैट्रिक्स से पंक्तियों और स्तंभों की कोई भी व्यवस्था की जा सकती है; लेकिन कोई तत्व नहीं बदला जा सकता है, यानी 'ए' को 'बी' में नहीं बदला जा सकता है। यदि दिए गए मैट्रिक्स से पैलिंड्रोमिक मैट्रिक्स बनाना संभव है, तो हम सही लौटते हैं; या अन्यथा, हम झूठी वापसी करते हैं।

इसलिए, यदि इनपुट 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"}