POJ 1691 Painting A Board：DFS+拓撲排序最小刷子拾取數

問題建模

N≤15 個矩形，每個有預設顏色 1..20。矩形塗色規則：
1. 僅當正上方所有相鄰矩形已塗色才能塗色（避免顏料向下流混色）
2. 同色矩形可一次拾取刷子連續塗完
3. 換色需重新拾取，甚至相同顏色非連續塗色也需重新拾取
求最小拾取刷子次數。

拓撲關係構建

矩形 A 正上方相鄰 B → 有向邊 A→B（A必須先於B塗色）。判斷水平重疊：

bool overlap(int x, int y) { // x在y上方
    return (rec[x].lx < rec[y].rx && rec[x].rx > rec[y].lx);
}

入度 rec[i].r 記錄未塗色的上方鄰居數。

DFS 狀態搜索

dfs(painted_count, current_color, pickups)：

• current_color=0：需換新刷子，枚舉所有入度為0的未塗色矩形
• current_color>0：嘗試繼續塗同色入度0矩形；無可塗則換色 dfs(painted, 0, pickups+1)
• 剪枝：pickups >= best 返回

關鍵代碼片段

void dfs(int x, int c, int b) {
    if (b >= minn) return;
    if (x == n) { minn = min(minn, b); return; }
    
    if (c == 0) {  // 換刷子
        for (int i=1; i<=n; i++)
            if (rec[i].r==0 && !rec[i].flag) {
                rec[i].flag=1; update_indegree(i, -1);
                dfs(x+1, rec[i].col, b);
                update_indegree(i, +1); rec[i].flag=0;
            }
    } else {  // 繼續同色
        bool found = false;
        for (int i=1; i<=n; i++)
            if (rec[i].col==c && rec[i].r==0 && !rec[i].flag) {
                found = true;
                rec[i].flag=1; update_indegree(i, -1);
                dfs(x+1, c, b);
                update_indegree(i, +1); rec[i].flag=0;
            }
        if (!found) dfs(x, 0, b+1);  // 強制換色
    }
}

複雜度分析

• 狀態空間：N≤15，顏色 ≤20，DFS 可行
• 拓撲排序保證合法塗色順序
• 搜索所有合法塗色序列，記錄最小拾取數

樣例解析

7 個矩形，輸出 3。最優策略：連續塗完所有色塊 1，換色塗 2，再換色塗剩餘 1（因中間隔了色塊 2）。