Chương trình C++ kiểm tra có thể tạo ma trận palindrome từ ma trận cho trước

Cho ma trận h x w chữ cái. Có thể hoán vị hàng và cột tùy ý. Kiểm tra có thể sắp xếp thành ma trận mà mọi hàng và cột đều là palindrome không.

Ví dụ

Với h=4, w=4, mat={xxyy, xyxx, yxxy, xyyy}, đầu ra true (1).

Giải thuật

Đếm tần suất mỗi ký tự. Phân loại theo modulo 4: cnt[0..3]. Kiểm tra điều kiện theo chẵn/lẻ của h,w: (h chẵn, w chẵn) → cnt[1]+cnt[2]+cnt[3]=0; (h lẻ, w lẻ) → cnt[1]+cnt[3]≤1 và cnt[2]≤h/2+w/2; (một chẵn một lẻ) → cnt[1]+cnt[3]=0 và cnt[2]≤chia cho chiều lẻ.

Mã C++

#include <bits/stdc++.h>
using namespace std;

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 / Đầu ra

Input: 4, 4, {"xxyy", "xyxx", "yxxy", "xyyy"}
Output: 1