圖片邊界繼續綿延,變成更大張的圖片。
方法很簡單,採用拼圖方式,從原圖片隨機擷取多個相同尺寸的小正方形,拼成更大的圖片。拼圖順序是由左到右,再由上到下。本題簡化問題難度,只做由左到右。
小正方形重疊一半的寬度(四捨五入)。於重疊區域當中,找到像素差異總和最小的路徑(兩個像素的顏色差異,設定為RGB的直線距離四捨五入),作為拼圖接縫(接縫及接縫以右,屬於新的小正方形)。起點在上緣某個像素,終點在下緣某個像素,每步只能走向「左下↙」、「下↓」、「右下↘」的相鄰像素,每步只能選擇其中一個方向前進。
當上述的最佳路徑,像素差異總和大於等於round(L*255/8),表示拼起來效果太差。此時捨棄當前的小正方形,重新找一個小正方形。如果連續捨棄50次,則放棄處理,輸出原始圖片。
另外,為了符合 ZeroJudge 的批改模式,請大家一律採用相同的亂數生成器,擷取小正方形的左上角座標。一步步拼圖、視需要擷取。
首先是一道指令:兩個整數 L N (2 <= L <= W, H) (1 <= N <= 5),L是小正方形尺寸,N是小正方形數量。
然後是一張圖片:兩個整數 W H (2 <= W, H <= 256),是圖片的寬和高;接下來的 H 行,每行有 W*3 個整數,是每個像素的 RGB 值 (0 <= R, G, B <= 255)。
請輸出處理後的圖片。
2 1 2 2 1 2 3 4 5 6 7 8 9 10 11 12
2 2 1 2 3 4 5 6 7 8 9 10 11 12
1. 路徑的概念,也出現在「b438: 裁剪尺寸」。
2. 學術上,此問題稱作 Texture Synthesis,此演算法稱作 Image Quilting。原理是:拼圖,讓接縫處誤差越小越好。
3. 本題的最短路徑,等價於平面圖最小割。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|