f680: 色塊數量
Tags : BFS 廣度優先 連通塊
Accepted rate : 99人/102人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-23 00:19

Content

前言:

在小畫家中有一種水桶工具,可以對目標位置 (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-do
            if 位置 (i, j) 有顏色 do
                呼叫遞迴函式以對位置 (i, j) 潑灑某些顏色
                cnt ← cnt+1

    印出 cnt

}

Input

第一行有一個正整數 N,代表有一張 NxN 的圖片( 1 ≤ N ≤ 10 )

接著有 N 行,每行有 N 個整數,
代表該格的顏色編號( 0 ≤ xij ≤ 9 ),兩兩之間以空格隔開

Output

共有幾個不同色塊

Sample Input #1
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
Sample Output #1
5
Sample Input #2
4
2 2 0 0
2 0 0 8
0 0 5 0
0 5 5 0
Sample Output #2
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#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
Hint :
Tags:
BFS 廣度優先 連通塊
出處:
教學題 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
24587
jiuanwey@gma... (Jane Weyth)
f680
for Python
321 2021-03-07 16:43