HDU 5386 Cover：逆向剝離 + 貪心構造操作序列

題目大意

n×n 矩陣，兩類操作：
L x y：第 x 列全置 y
H x y：第 x 行全置 y
給初始矩陣、目標矩陣、m 個操作（順序未定）。求操作排列順序使初始變為目標。

核心洞察：逆向思維「撕膠布」

最後執行的操作，其影響的行/列在目標矩陣中必須完全呈現該操作的顏色（忽略已被後續操作覆蓋的格子）。因此可反向模擬：

1. 從目標矩陣出發，尋找某行/列（扣除已標記格子）顏色均一致於某未用操作。
2. 將該操作標記為「最後一步」，並將該行/列格子標記為「已剝離」（設為 INF）。
3. 重複 m 次，得到逆序操作序列，反轉即為正序。

判定邏輯

bool check(int x, int color, char type) {
    if(type=='H') for(int i=1;i<=n;++i)
        if(tar[x][i]!=INF && tar[x][i]!=color) return false;
    else for(int i=1;i<=n;++i)
        if(tar[i][x]!=INF && tar[i][x]!=color) return false;
    return true;
}

void setColor(int x, char type) {
    if(type=='H') for(int i=1;i<=n;++i) tar[x][i]=INF;
    else for(int i=1;i<=n;++i) tar[i][x]=INF;
}

完整流程

void solve() {
    int cnt=0;
    while(cnt < m) {
        for(i=0;i<nh;++i) if(!visH[i] && check(H[i].x, H[i].color, 'H')) {
            setColor(H[i].x, 'H'); visH[i]=1; order[cnt++]=H[i].id;
        }
        for(i=0;i<nL;++i) if(!visL[i] && check(L[i].x, L[i].color, 'L')) {
            setColor(L[i].x, 'L'); visL[i]=1; order[cnt++]=L[i].id;
        }
    }
    // 逆序輸出 order[m-1] ... order[0]
}

正確性證明

每步選擇的操作在當前殘留矩陣中「顏色純淨」，說明它必須是最後執行的（否則會被後續操作污染）。貪心選擇任一滿足條件的操作均可，因為操作間無相互依賴（覆蓋關係只由順序決定）。