在小畫家中有一種水桶工具,可以對目標位置 (i, j) 潑灑顏色,
顏色會不斷蔓延,直到超出合法範圍或遇到不能著色的格子為止。
舉例來說,假設對於下圖中心潑灑橘色,得到的結果會是:
對於上述原始圖片,我們可以使用一個二維陣列來儲存,其中 0 為白格,1 為黑格。
潑灑顏色則可以使用遞迴實作,以下是潑灑顏色的遞迴程式碼:
void draw(int i, int j, int color, int x[10][10], int N)
{
if(i < 0 || i >= N || j < 0 || j >= N) // 位置 (i, j) 超出合法範圍
return;
else if(x[i][j] != 0) // 位置 (i, j) 已上色,不能著色
return;
else
{
x[i][j] = color; // 將位置 (i, j) 塗為 color 色
draw(i-1, j, color, x, N); // 往上蔓延著色
draw(i+1, j, color, x, N); // 往下蔓延著色
draw(i, j-1, color, x, N); // 往左蔓延著色
draw(i, j+1, color, x, N); // 往右蔓延著色
}
}
遞迴指的是自己呼叫自己的函式,利用遞迴,可以將許多複雜問題簡化。
同色塊的定義是「與相鄰(上下左右,共四個方向)的格子為相同顏色」,
其中比較特別的是,即使相同顏色,只要不相鄰,即視為不同色塊。
以下圖為例,有 2 個綠色色塊、1 個橘色色塊、1 個紅色色塊、1 個藍色色塊,
共有 5 個不同色塊:
現在有一張 NxN 的圖片( 1 ≤ N ≤ 100),
對於第 i 列第 j 行的格子會有該格的顏色編號 xij ( 0 ≤ xij ≤ 9),
當編號為 0 時表示為白色格子,非 0 時表示為有顏色的格子。
請計算圖片中共有幾個不同色塊。
我們可以利用二維陣列儲存這張 NxN 的圖片,並且利用巢狀迴圈以做掃視。
在掃視的過程中,只要所掃視到的格子 (i, j) 是有顏色的,即以該格為起始點潑灑某些顏色記號。
潑灑顏色的部分,你可以借助和修改前言所提供的遞迴程式碼,以完成本題任務。
本題的虛擬碼如下:
void 調整後的潑灑顏色函式(...)
int main()
{
x[][] ← 讀入圖片
cnt ← 0
for i = 0 到 N-1 do
for j = 0 ~ N-1 do
if 位置 (i, j) 有顏色 do
呼叫遞迴函式以對位置 (i, j) 潑灑某些顏色
cnt ← cnt+1
印出 cnt
}
第一行有一個正整數 N,代表有一張 NxN 的圖片( 1 ≤ N ≤ 10 )
接著有 N 行,每行有 N 個整數,
代表該格的顏色編號( 0 ≤ xij ≤ 9 ),兩兩之間以空格隔開
共有幾個不同色塊
6 1 1 0 0 0 0 1 0 0 1 1 0 0 0 2 1 1 0 0 2 2 0 0 0 0 0 2 0 3 3 4 0 0 0 0 0
5
4 2 2 0 0 2 0 0 8 0 0 5 0 0 5 5 0
3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
24587 | jiuanwey@gma ... (Jane Weyth) | f680 | 966 | 2021-03-07 16:43 |