b438.
裁剪尺寸
內容
有辦法縮小圖片，但是不壓扁景物嗎？
那就去掉圖片最平凡的地方吧！最平凡的地方，也許就是變化最小的地方。變化最小的地方，也許就是梯度最小的地方。實驗看看吧！
運用 Sobel Operator，每個像素的變化量，設定成|SXR| + |SYR| + |SXG| + |SYG| + |SXB| + |SYB|。嘗試找到一條變化總和最小的路徑，起點在圖片上緣某個像素，終點在圖片下緣某個像素，每步只能走向「左下↙」、「下↓」、「右下↘」的相鄰像素，每步只能選擇其中一個方向前進。
刪除一條變化總和最小的路徑，圖片寬度剛好減少一！反覆刪除路徑，直到圖片變成預定尺寸。
如果變化總和最小的路徑有許多條，以尾端最靠左的路徑為主。
輸入說明
首先是一個整數 N (0 <= N < W)，請刪除 N 條路徑。
然後是一張圖片：兩個整數 W H (1 <= W, H <= 256)，是圖片的寬和高；接下來的 H 行，每行有 W*3 個整數，是每個像素的 RGB 值 (0 <= R, G, B <= 255)。
輸出說明
請輸出處理後的圖片。
範例輸入
#1
0 1 1 255 255 255
範例輸出
#1
1 1 255 255 255
測資資訊：
記憶體限制：
64
MB
提示 ：
1. 關於Sobel operator的細節，請參考「b436: 圖片的梯度再進化」。
2. 學術上，此問題稱作 Content-Aware Image Resizing，此演算法稱作 Seam Carving。原理是：讓路徑盡量不要穿越景物輪廓，那麼刪除此路徑便不會影響景物形狀。
3. 一口氣找到N條路徑，一口氣刪除N條路徑，理論上才是最佳結果。因為演算法時間複雜度很高（雖然是多項式時間），所以沒有人這麼做，而是採用本題的greedy策略，逐次找到一條路徑，逐次刪除一條路徑。
4. 並不是所有圖片都適合套用此演算法。例如這張：
標籤:
出處:
[管理者：
DJWS
(...)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||