前言：
在小畫家中有一種水桶工具，可以對目標位置 (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
公開 測資點#0 (5%): 0.1s , <1K
公開 測資點#1 (5%): 0.1s , <1K
公開 測資點#2 (5%): 0.1s , <1K
公開 測資點#3 (5%): 0.1s , <1K
公開 測資點#4 (5%): 0.1s , <1K
公開 測資點#5 (5%): 0.1s , <1K
公開 測資點#6 (5%): 0.1s , <1K
公開 測資點#7 (5%): 0.1s , <1K
公開 測資點#8 (5%): 0.1s , <1K
公開 測資點#9 (5%): 0.1s , <1K
公開 測資點#10 (5%): 0.1s , <1K
公開 測資點#11 (5%): 0.1s , <1K
公開 測資點#12 (5%): 0.1s , <1K
公開 測資點#13 (5%): 0.1s , <1K
公開 測資點#14 (5%): 0.1s , <1K
公開 測資點#15 (5%): 0.1s , <1K
公開 測資點#16 (5%): 0.1s , <1K
公開 測資點#17 (5%): 0.1s , <1K
公開 測資點#18 (5%): 0.1s , <1K
公開 測資點#19 (5%): 0.1s , <1K
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 24587 |
|
f680 | 961 | 2021-03-07 16:43 |