ZOJ 3864 EXO徽章識別：圖像壓縮與連通分量解法詳解

問題背景

EXO 是一個中韓男子組合，每位成員擁有獨特的超能力徽章。給定 12 張徽章圖像（可任意旋轉），需識別輸入圖像對應的成員。圖像為 N×N 方陣（100≤N≤900），像素值經二值化為 0（黑）或 1（白）。

圖像壓縮格式

採用行優先游程編碼（RLE）：將像素按行拼接成字串，統計連續相同字符的長度序列。首尾游程必為白色。例如 6×6 圖像壓縮為 7 2 1 1 2 3 4 1 4 1 1 2 7。

核心觀察：拓撲特徵不變性

旋轉不改變圖像的連通分量結構。關鍵特徵：

• 黑色連通分量數量（4連通或8連通）
• 被黑色包圍的白色洞數量（不計最外層白色背景）

12 個徽章的 (黑塊數, 白洞數) 唯一對應：

算法流程

1. 解壓 RLE 還原 N×N 二值矩陣
2. BFS/DFS 統計 8 連通黑色分量（mat[i][j]==1）
3. 統計 4 連通白色分量（mat[i][j]==0），排除邊界連通的背景
4. 根據上表匹配成員，Sehun/Xiumin 需額外比較前 4 大黑塊面積和與第 5 大的比值

關鍵代碼片段

// 8 方向鄰居（黑塊用 8 連通）
int dir[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

int bfs(int x, int y, int color) {
    queue q;
    q.push({x,y});
    vis[x][y] = 1;
    int cnt = 1;
    while (!q.empty()) {
        auto [cx,cy] = q.front(); q.pop();
        for (auto [dx,dy] : dir) {
            int nx = cx+dx, ny = cy+dy;
            if (nx>=0 && nx=0 && ny black, white;
for (int i=0; i

複雜度分析

解壓：O(N²)
BFS 遍歷：O(N²)
總體：O(N²) 時間，O(N²) 空間，滿足 N≤900 限制


避坑指南

白色連通分量必須用 4 連通，黑色用 8 連通（或反之，需與訓練數據一致）
最外層白色背景不計入白洞數
Sehun/Xiumin 判別：前 4 大黑塊面積和 / 第 5 大面積 < 0.4 為 Sehun，否則 Xiumin
輸入可能包含多測試用例，注意重置數組