Chương trình C ++ để tìm hiểu xem một ma trận palindromic có thể được tạo từ một ma trận nhất định hay không

Giả sử, chúng ta được đưa ra một ma trận với kích thước h x w. Ma trận chứa các chữ cái tiếng Anh. Chúng ta phải tạo một ma trận khác chứa các hàng và cột palindromic, tức là mỗi hàng và cột sẽ là palindromes. Để làm điều đó, bất kỳ sự sắp xếp hàng và cột nào cũng có thể được thực hiện từ ma trận đã cho; nhưng không phần tử nào có thể thay đổi được, tức là không thể thay đổi "a" thành "b". Nếu có thể tạo ma trận palindromic từ ma trận đã cho, chúng ta trả về true; hoặc nếu không, chúng tôi trả về false.

Vì vậy, nếu đầu vào là h =4, w =4, mat ={"xxyy", "xyxx", "yxxy", "xyyy"}, thì đầu ra sẽ là true.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

4, 4, {"xxyy", "xyxx", "yxxy", "xyyy"}

Đầu ra

1