UVA 1030 Image Is Everything：三維立體重構的迭代剝離算法

題目大意

N×N×N 晶格 (N ≤ 10) 中部分單元立方體存在，每個立方體有顏色。給定 6 個正交視圖（前、左、後、右、上、下），'.' 表示可視穿透。求最大可能體積（立方體數）。

核心算法：迭代約束傳播

1. 初始化 3D 數組 solid[x][y][z] = '*'（候選存在）。
2. 處理 '.' 視圖：對應視線上的所有坐標標記為 '.'（確定不存在）。
3. 迭代處理有色視圖：對每個有色像素，沿視線找第一個未確定 '*' 的坐標，嘗試著色：
   • 若該坐標為 '*' → 著上該顏色。
   • 若已有顏色且不同 → 衝突，標記為 '.'（不存在）。
   • 若顏色相同 → 確定，停止該視線搜索。
4. 重複直到無變化。剩餘非 '.' 的格子即最大體積構型。

坐標映射（關鍵）

視圖索引 k=0..5 對應前/左/後/右/上/下。
視圖上 (i, j)、深度 m 映射到 3D 座標 (x,y,z)：

void mapCoord(int i, int j, int k, int m, int &x, int &y, int &z, int N) {
    switch(k) {
        case 0: x=i; y=j; z=m; break;           // 前
        case 1: x=i; y=m; z=N-1-j; break;       // 左
        case 2: x=i; y=N-1-j; z=N-1-m; break;   // 後
        case 3: x=i; y=N-1-m; z=j; break;       // 右
        case 4: x=m; y=j; z=N-1-i; break;       // 上
        case 5: x=N-1-m; y=j; z=i; break;       // 下
    }
}

C++ 代碼

#include 
using namespace std;
int N;
char view[6][12][12], solid[12][12][12];

void mapCoord(int i, int j, int k, int m, int &x, int &y, int &z) {
    switch(k) {
        case 0: x=i; y=j; z=m; break;
        case 1: x=i; y=m; z=N-1-j; break;
        case 2: x=i; y=N-1-j; z=N-1-m; break;
        case 3: x=i; y=N-1-m; z=j; break;
        case 4: x=m; y=j; z=N-1-i; break;
        case 5: x=N-1-m; y=j; z=i; break;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> N, N) {
        // 讀 6 視圖
        for (int i = 0; i < N; ++i)
            for (int k = 0; k < 6; ++k)
                for (int j = 0; j < N; ++j) {
                    char c; cin >> c;
                    view[k][i][j] = c;
                }
        // 初始化
        for (int x = 0; x < N; ++x)
            for (int y = 0; y < N; ++y)
                for (int z = 0; z < N; ++z)
                    solid[x][y][z] = '*';
        // '.' 視圖剝離
        for (int k = 0; k < 6; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    if (view[k][i][j] == '.')
                        for (int m = 0; m < N; ++m) {
                            int x,y,z; mapCoord(i,j,k,m,x,y,z);
                            solid[x][y][z] = '.';
                        }
        // 迭代著色
        while (true) {
            bool changed = false;
            for (int k = 0; k < 6; ++k)
                for (int i = 0; i < N; ++i)
                    for (int j = 0; j < N; ++j)
                        if (view[k][i][j] != '.') {
                            char col = view[k][i][j];
                            for (int m = 0; m < N; ++m) {
                                int x,y,z; mapCoord(i,j,k,m,x,y,z);
                                if (solid[x][y][z] == '.') continue;
                                if (solid[x][y][z] == '*') {
                                    solid[x][y][z] = col;
                                } else if (solid[x][y][z] != col) {
                                    solid[x][y][z] = '.';
                                    changed = true;
                                }
                                if (solid[x][y][z] == col) break; // 找到匹配，視線終止
                            }
                        }
            if (!changed) break;
        }
        int ans = 0;
        for (int x = 0; x < N; ++x)
            for (int y = 0; y < N; ++y)
                for (int z = 0; z < N; ++z)
                    if (solid[x][y][z] != '.') ++ans;
        cout << "Maximum weight: " << ans << " gram(s)\n";
    }
    return 0;
}

複雜度

• N ≤ 10，狀態空間 1000，迭代極快。
• 時間 O(迭代輪數 × 6 × N³) ≈ 10⁵ 操作級。

總結

UVA 1030 是「多視圖三維重構」的經典約束滿足問題。核心技巧：'.' 先剝離確定空洞 → 有色視圖迭代著色衝突消除 → 收斂得最大體積。同類思想用於醫學成像（CT/MRI 重構）、計算機視覺多視角立體匹配。