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

คำอธิบายปัญหา

สมมติว่าเรามีเมทริกซ์ขนาด h x w มีตัวอักษรภาษาอังกฤษ ต้องการสร้างเมทริกซ์ใหม่ที่แถวและคอลัมน์ทั้งหมดเป็นพาลินโดรม สามารถจัดเรียงแถวและคอลัมน์ได้จากเมทริกซ์เดิม แต่ห้ามเปลี่ยนตัวอักษร (a ไม่กลายเป็น b) ถ้าทำได้คืน true มิฉะนั้น false

ตัวอย่าง: h = 4, w = 4, mat = {"xxyy", "xyxx", "yxxy", "xyyy"} ผลลัพธ์คือ true

ขั้นตอนการแก้ปัญหา

กำหนด map mp
กำหนดอาร์เรย์ count ขนาด 4
สำหรับ i := 0 ถึง h-1:
    สำหรับ j := 0 ถึง w-1:
        เพิ่ม mp[mat[i,j]] ขึ้น 1
สำหรับค่า val ใน mp:
    เพิ่ม count[val mod 4] ขึ้น 1
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

ตัวอย่างโค้ด C++

#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