b423: 魔術橡皮擦
Tags : 影像處理
Accepted rate : 28人/30人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-27 19:52

Content



高級的繪圖軟體,例如Adobe Photoshop,皆具備魔術橡皮擦的功能,用來去除圖片的背景,簡稱「去背」。

本題打算請你實現最基本的魔術橡皮擦演算法。指令格式如下:

X Y TYPE DIFF

(X,Y) 是滑鼠擊中的像素座標。X 是橫向,Y 是直向。圖片左上角的像素,座標是 (0,0)。

TYPE 是功能類型,只有 0 與 1 兩種。0 是處理整張圖片。1 是只處理四方向相連的像素,不斷蔓延,直到遭遇不需去背的像素。

DIFF 是顏色差距。以 (X,Y) 的顏色為基礎,顏色差距小於等於 DIFF,就必須去背。差距的計算方式:兩個顏色 (R1 G1 B1) 與 (R2 G2 B2) 的差距是 sqrt((R1-R2)2 + (G1-G2)2 + (B1-B2)2)。即直線距離。

例外處理:(X,Y) 超過圖片邊界,不處理,令圖片保持原樣。TYPE 不是 0 與 1,不處理,令圖片保持原樣。

指令範例:0 0 0 0,檢查圖片每一個像素,如果和像素 (0,0) 顏色相同,則設定為透明。

Input

首先是一道指令:四個整數 X Y TYPE DIFF (-231 <= X, Y, TYPE, DIFF <= 231-1)。

然後是一張圖片:兩個整數 W H (1 <= W, H <= 256),是圖片的寬和高;接下來的 H 行,每行有 W*4 個整數,是每個像素的 RGBA 值 (0 <= R, G, B, A <= 255)。

Output

請輸出處理後的圖片。A 等於 0 表示透明。

Sample Input #1
0 0 0 0
3 2
1 2 3 255 4 5 6 255 7 8 9 255
10 11 12 255 13 14 15 255 16 17 18 255
Sample Output #1
3 2
1 2 3 0 4 5 6 255 7 8 9 255
10 11 12 255 13 14 15 255 16 17 18 255
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (9%): 1.0s , <1M
公開 測資點#1 (9%): 1.0s , <1M
公開 測資點#2 (9%): 1.0s , <1M
公開 測資點#3 (9%): 1.0s , <1M
公開 測資點#4 (9%): 1.0s , <1M
公開 測資點#5 (9%): 1.0s , <1M
公開 測資點#6 (9%): 1.0s , <1M
公開 測資點#7 (9%): 1.0s , <1M
公開 測資點#8 (9%): 1.0s , <1M
公開 測資點#9 (9%): 1.0s , <1K
公開 測資點#10 (10%): 1.0s , <1K
Hint :

1. PNG格式,才擁有透明度資訊;JPEG格式,沒有透明度資訊。

Tags:
影像處理
出處:
[管理者: DJWS(...) ]


ID User Problem Subject Hit Post Date
24061 s1082942@g.n...(sellie) b423
468 2021-01-14 14:55