您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

SGU 262 Symbol Recognition：狀壓 DP 求最小特徵矩陣

編輯：關於C++

SGU 262 是一道極具啟發性的狀壓動態規劃題目。給定 k 個 n×m 的 01 矩陣 S₁…Sₖ，求一個 1 最少的 n×m 01 矩陣 P，使得 k 個矩陣與 P 的按位 AND 運算結果兩兩不同（即 P 能「區分」所有 Sᵢ）。

一、問題重述與建模

輸入：k ≤ 6, n,m ≤ 10, k 個 01 矩陣。
目標：構造 P，最小化 P 中 1 的個數，滿足 (S_i & P) != (S_j & P) 對於所有 i ≠ j。
等價：對每個 Sᵢ，定義其「特徵向量」Qᵢ = Sᵢ & P。要求所有 Qᵢ 互不相同。

二、核心洞察：狀態壓縮與最小表示

按行優先序枚舉 P 的每個格子 (x,y)。假設當前已處理前 t 個格子，每個 Sᵢ 在這些格子上的 AND 結果形成一個部分特徵 Qᵢ^(t)。將這些部分特徵按最小表示法重新編碼為整數 Tᵢ，使得 Qᵢ = Qⱼ ⇔ Tᵢ = Tⱼ。則整個狀態可壓縮為一個 k 元組 (T₁, T₂, …, Tₖ)，每個 Tᵢ ∈ [0, k-1]，總狀態數 ≤ kᵏ (6⁶ = 46656)。

三、狀態轉移詳解

當前格子 (x,y)，對每個 i 取 bit = Sᵢ[x][y]。若在 P 中放 1，則新特徵 Qᵢ' = Qᵢ * 2 + bit（左移加位）；若放 0，則 Qᵢ' = Qᵢ * 2。對新特徵向量再做最小表示得到新狀態 ns。DP 狀態 f[s] 表示達到狀態 s 所需最少 1 的個數。

四、最小表示算法

對當前 k 個部分特徵（用 pair<int,int> 表示：<原特徵值, 當前bit>），用 map 分配新編碼 0,1,2…，保證相同特徵得同編碼，不同得不同編碼，且編碼按首次出現順序分配（即最小表示）。

五、完整 AC 代碼（C++11）

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

const int MAXK = 7;
const int MAXN = 11;
const int MAXS = 46660;  // 6^6 = 46656
const int INF = 0x3f3f3f3f;

int n, m, k, S;
int g[MAXK][MAXN][MAXN];   // 原始矩陣
int col[MAXN][MAXN];       // 該位置是否有任一矩陣為 1
int f[MAXS], fr[MAXS], fx[MAXS], fy[MAXN];  // DP 與路徑回溯

// 將狀態 s 在 (x,y) 放 1 後轉移到新狀態 ns，更新 f
void upd(int s, int x, int y) {
    int ts = s, add = f[s], tot = 0, ns = 0;
    map<pair<int,int>, int> mp;
    // 分解狀態 s 為 k 位 k 進制數，每位對應一個矩陣的當前特徵編碼
    for (int i = 0, j = 1; i < k; ++i, ts /= k, j *= k) {
        int code = ts % k;           // 矩陣 i 當前的特徵編碼
        int bit = g[i][x][y];        // 矩陣 i 在 (x,y) 的值
        pair<int,int> key = {code, bit};
        if (!mp.count(key)) mp[key] = tot++;
        ns += mp[key] * j;           // 重新編碼為 k 進制
    }
    if (f[ns] > add + 1) {
        f[ns] = add + 1;
        fr[ns] = s;
        fx[ns] = x;
        fy[ns] = y;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> m >> k)) return 0;
    for (int i = 0; i < k; ++i)
        for (int p = 0; p < n; ++p)
            for (int q = 0; q < m; ++q) {
                char ch; cin >> ch;
                g[i][p][q] = ch - '0';
                col[p][q] |= g[i][p][q];
            }
    
    // 狀態總數 = k^k
    S = 1;
    for (int i = 0; i < k; ++i) S *= k;
    fill(f, f + S, INF);
    f[0] = 0;  // 初始狀態：所有特徵均為空，編碼全 0
    
    // 按行優先序枚舉格子，只考慮 col[x][y]==1 的格子（全 0 列放 1 無意義）
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (col[i][j])
                for (int s = 0; s < S; ++s)
                    if (f[s] < INF)
                        upd(s, i, j);
    
    // 終止狀態：所有編碼互不相同，即為 0,1,2,...,k-1 的某排列
    // 最小表示下必為 0,1,...,k-1，對應 k 進制數 end = Σ i * k^i
    int end = 0;
    for (int i = k - 1; i >= 0; --i) end = end * k + i;
    
    cout << f[end] << '\n';
    
    // 回溯構造 P
    vector<vector<int>> ans(n, vector<int>(m, 0));
    int cur = end;
    while (cur) {
        ans[fx[cur]][fy[cur]] = 1;
        cur = fr[cur];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) cout << ans[i][j];
        cout << '\n';
    }
    return 0;
}