โปรแกรม C++ หาจำนวนวิธีการระบายสีกริดที่มีแผ่นปิด

โจทย์ให้กริดขนาด 2 × n ที่ต้องปิดทับด้วย n แผ่น (ไม่ทับซ้อนกัน) แต่ละแผ่นต้องระบายสีเป็นสีแดง น้ำเงิน หรือเขียว โดยเงื่อนไขคือแผ่นที่ติดกันไม่สามารถมีสีเดียวกันได้ (ไม่จำเป็นต้องใช้สีทั้ง 3 สี) การจัดวางแผ่นในกริดระบุโดยอาร์เรย์ grid ที่แผ่นเดียวกันใช้ตัวอักษรอังกฤษตัวเดียวกัน แผ่นต่างกันใช้ตัวอักษรต่างกัน ต้องการหาจำนวนวิธีการระบายสีที่เป็นไปได้

ตัวอย่าง: n = 4, grid = {"abbd", "accd"} ผลลัพธ์คือ 6 วิธี

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

1. กำหนดค่าคงที่ MODVAL = 1e9 + 7
2. สร้างอาร์เรย์ s โดยอ่านคอลัมน์ซ้ายไปขวา:
   • ถ้า grid[0][i] == grid[1][i] (แผ่นตั้งตรง) ใส่ 1 ลง s, เพิ่ม i++
   • มิฉะนั้น (แผ่นนอน 2 คอลัมน์) ใส่ 2 ลง s, เพิ่ม i += 2
3. สร้างอาร์เรย์ tvec ขนาดเท่ากับ s:
   • tvec[0] = 3 ถ้า s[0] == 1 มิฉะนั้น 6
   • สำหรับ i = 1 ถึง s.size()-1 คำนวณตามกรณีของ s[i-1] และ s[i]:
     • 2, 2 → tvec[i] = tvec[i-1] * 3 % MODVAL
     • 2, 1 → tvec[i] = tvec[i-1]
     • 1, 2 → tvec[i] = tvec[i-1] * 2 % MODVAL
     • 1, 1 → tvec[i] = tvec[i-1] * 2 % MODVAL
4. คืนค่า tvec.back()

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

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

int solve(int n, vector<string> grid) {
    const int MODVAL = 1e9 + 7;
    vector<int> s;
    for (int i = 0; i < n;) {
        if (grid[0][i] == grid[1][i]) {
            s.push_back(1);
            i++;
        } else {
            s.push_back(2);
            i += 2;
        }
    }
    vector<int> tvec(s.size());
    if (s[0] == 1) tvec[0] = 3;
    else tvec[0] = 6;
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i-1] == 2 && s[i] == 2) tvec[i] = (long long)tvec[i-1] * 3 % MODVAL;
        if (s[i-1] == 2 && s[i] == 1) tvec[i] = tvec[i-1];
        if (s[i-1] == 1 && s[i] == 2) tvec[i] = (long long)tvec[i-1] * 2 % MODVAL;
        if (s[i-1] == 1 && s[i] == 1) tvec[i] = (long long)tvec[i-1] * 2 % MODVAL;
    }
    return tvec.back();
}

int main() {
    int n = 4;
    vector<string> grid = {"abbd", "accd"};
    cout << solve(n, grid);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, {"abbd", "accd"}

Output: 6