ZOJ 1067 顏色映射：最近歐氏距離匹配

問題描述

給定 16 個基準 RGB 顏色（0~255）。隨後輸入多個查詢顏色，對每個查詢找到與其歐氏距離平方最小的基準色（距離定義：d² = (R1-R2)² + (G1-G2)² + (B1-B2)²）。輸入以 -1 -1 -1 結束。輸出格式：(R,G,B) maps to (R',G',B')。

解法：暴力枚舉

• 基準色固定 16 個，查詢數未給上限但極小。
• 對每個查詢，遍歷 16 個基準色計算距離平方，記錄最小值對應索引。
• 時間 O(Q × 16) 可忽略，無需 KD-Tree 等加速結構。

完整代碼

#include 
#include 
using namespace std;

int base[16][3];

int main() {
    for (int i = 0; i < 16; ++i)
        cin >> base[i][0] >> base[i][1] >> base[i][2];

    int R, G, B;
    while (cin >> R >> G >> B) {
        if (R == -1 && G == -1 && B == -1) break;
        int bestIdx = -1, bestDist = -1;
        for (int i = 0; i < 16; ++i) {
            int dr = R - base[i][0];
            int dg = G - base[i][1];
            int db = B - base[i][2];
            int dist = dr*dr + dg*dg + db*db;
            if (bestDist == -1 || dist < bestDist) {
                bestDist = dist;
                bestIdx = i;
            }
        }
        printf("(%d,%d,%d) maps to (%d,%d,%d)\n",
               R, G, B, base[bestIdx][0], base[bestIdx][1], base[bestIdx][2]);
    }
    return 0;
}

樣例驗證

輸入前 16 行基準色，隨後查詢：

(0,0,0) maps to (0,0,0)
(255,255,255) maps to (255,255,255)
(253,254,255) maps to (255,255,255)
(77,79,134) maps to (128,128,128)
(81,218,0) maps to (126,168,9)

均符合最近距離原則。

注意事項

• 距離用平方避免 sqrt，不影響大小比較，更快。
• 輸入可能含多空格/換行，cin >> 自動處理。
• 輸出格式嚴格：括號、逗號、空格完全匹配樣例。
• 基準色固定 16 個，無動態增刪，數組大小常量即可。

擴展思考

若基準色數量大（如 10⁵），需構建 3D KD-Tree 或八叉樹，查詢 O(log N)。本題 16 個暴力最優。

總結

ZOJ 1067 是簡單的最近鄰搜索入門題：固定小規模參考集，暴力計算歐氏距離平方即可。核心考察輸入輸出格式處理、距離計算避免開方、邊界條件（-1 終止）。代碼短小精悍，適合熱身。