โปรแกรม C ++ เพื่อดูว่าเมทริกซ์พาลินโดรมสามารถสร้างจากเมทริกซ์ที่กำหนดได้หรือไม่

สมมติว่าเราได้รับเมทริกซ์ที่มีขนาด 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