給定一張高度為 $\color{black}{H}$ 像素、寬度為 $\color{black}{W}$ 像素的點陣圖 $\color{black}{P}$,由上至下數來第 $\color{black}{i}$ 個、由左至右數來第 $\color{black}{j}$ 個的像素以 $\color{black}{(i, j)}$ 表示。$\color{black}{(i, j)}$ 的色彩編號為 $\color{black}{C_{ij}}$。
小明用某繪圖軟體開啟點陣圖 $\color{black}{P}$,使用軟體中的「填入色彩」功能:用滑鼠點擊 $\color{black}{S_i,S_j}$,所有與 $\color{black}{S_i,S_j}$ 屬於同一個「連通區塊」像素的色彩編號均會轉換成指定的色彩$\color{black}{Z}$。對於影像$\color{black}{P}$ 上任兩個上、下、左或右相鄰的像素$\color{black}{(i, j)}$ 與$\color{black}{(i', j')}$ (即 $\color{black}{(i', j') ∈{(i-1, j ), (i+1, j ), (i, j-1), (i, j+1)}} )$,如果$\color{black}{C _{ij}}$ 和 $\color{black}{C_{i'j'}}$ 相同,則說$\color{black}{(i, j)}$ 與$\color{black}{(i', j') }$ 同屬於同一個「連通區塊」。
例如有一張 $\color{black}{ H = 5 }$ 像素、$\color{black}{ W = 6 }$ 像素的原始點陣圖 $\color{black}{ P }$ 如圖一所示,用滑鼠點擊$\color{black}{(S_i, S_j) = (3, 2)}$,將所有與其屬於同一個「連通區塊」像素的色彩編號轉換成 $\color{black}{ Z = 4 }$。填入色彩之後的新點陣圖 $\color{black}{ P' }$ 如圖二所表示。
請寫一個程式在給定原始點陣圖 $\color{black}{P}$ 的資訊的情形下,模擬「填入色彩」$\color{black}{Z}$ 之後的新點陣圖 $\color{black}{P'}$。
第一列有五個非負整數依序為 $\color{black}{H}$、$\color{black}{W}$、$\color{black}{S_i}$、$\color{black}{S_j}$ 與 $\color{black}{Z}$,表示原始點陣圖$\color{black}{P}$ 的高度為 $\color{black}{H}$ 像素、寬度為 $\color{black}{W}$ 像素、用滑數點擊$\color{black}{(S_i, S_j)}$、將該連通區塊的色彩改為色彩$\color{black}{Z}$。第 $\color{black}{2}$ 列到第 $\color{black}{H+1}$ 列代表原始點陣圖每個像素的原始顏色,每行都有 $\color{black}{W}$ 個非負整數,彼此以一個空白隔開;第 $\color{black}{i+1}$ 列的第 $\color{black}{j}$ 個數字表示 $\color{black}{(i, j)}$ 的色彩編號 $\color{black}{C_{ij}}$。
測資範圍:
$\color{black}{1≤ H, W ≤ 500}$
$\color{black}{1 ≤ S_i ≤ H}$
$\color{black}{1 ≤ S_j ≤ W}$
$\color{black}{0 ≤ Z ≤ 99}$
$\color{black}{0 ≤ C_{ij} ≤ 99}$
請輸出 $\color{black}{H}$ 行,每一行有 $\color{black}{W}$ 個非負整數,彼此以一個空白隔開,表示「填入色彩」$\color{black}{Z}$ 之後的新點陣圖 $\color{black}{P'}$。
1 5 1 3 3 1 0 0 0 1
1 3 3 3 1
5 6 3 2 4 2 2 2 2 0 0 2 1 0 0 2 0 2 0 1 3 2 0 2 0 0 0 2 0 2 2 2 2 2 0
2 2 2 2 0 0 2 1 0 0 2 0 2 4 1 3 2 0 2 4 4 4 2 0 2 2 2 2 2 0
4 5 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 8 3 4 2 1 0 0 1 0 0 3 0 0 0 3 2 0 0 3 2 0 0 2 3 3 3 3 0 0 0 3 3 3 3 0 0 0 0 3 0 0 3 3 3 3 3 0 0 0 0 0 0
1 0 0 1 0 0 2 0 0 0 3 2 0 0 2 2 0 0 2 2 2 2 2 0 0 0 2 2 2 2 0 0 0 0 2 0 0 2 2 2 3 3 0 0 0 0 0 0
注意用dfs可能會因StackOverFlow而RE
https://zh.wikipedia.org/wiki/%E5%A0%86%E7%96%8A%E6%BA%A2%E4%BD%8D
第一組 (測資點$\color{black}{00\sim05}$):$\color{black}{H = 1}$
第二組 (測資點$\color{black}{06\sim19}$):無特別限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|