Chương trình C++ đếm số cách tô màu lưới 2×n bằng 3 màu

Mô tả bài toán

Cho lưới 2 hàng, n cột được phủ bởi n thanh domino (mỗi thanh chiếm 2 ô liền kề). Cần tô mỗi thanh bằng một trong 3 màu (đỏ, xanh lá, xanh dương) sao cho hai thanh chung cạnh không cùng màu. Tính số cách tô màu modulo 10^9+7. Cấu hình thanh được cho bởi 2 chuỗi ký tự: ô cùng ký tự = cùng một thanh.

Ví dụ

n = 4, lưới = {"abbd", "accd"}. Đầu ra: 6.

Thuật toán

1. Nén lưới thành mảng s: s[i] = 1 nếu thanh dọc (cùng cột), 2 nếu thanh ngang (chiếm 2 cột).
2. DP: tvec[0] = 3 nếu s[0]==1 else 6.
3. Chuyển trạng thái:
   • 2→2: nhân 3
   • 2→1: giữ nguyên
   • 1→2: nhân 2
   • 1→1: nhân 2
4. Kết quả là tvec.back().

Đoạn mã C++

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

int solve(int n, vector<string> grid) {
    const int MOD = 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());
    tvec[0] = (s[0] == 1) ? 3 : 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 % MOD;
        else if(s[i-1] == 2 && s[i] == 1) tvec[i] = tvec[i-1];
        else if(s[i-1] == 1 && s[i] == 2) tvec[i] = (long long)tvec[i-1] * 2 % MOD;
        else tvec[i] = (long long)tvec[i-1] * 2 % MOD;
    }
    return tvec.back();
}

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

Đầu vào / Đầu ra

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

Output: 6