Lv3 FloodFill

質問する

n x mサイズの図面に描画された図の色を2次元リストとする.同じ色が同じ数字で表示されている場合、図に全部で何個の領域があるか知りたいです.領域とは上下左右に接続された同じ色の空間を指す.
例えば、リスト[1,2,3],[3,2,1]は、以下のように表すことができる.

この図には5つの領域があります.
画用紙の大きさnとmを画用紙に塗った色画像を与える場合は、resolution関数を書いて、図のいくつかの領域を返します.
せいげんじょうけん

nおよびmは、1または250以下の整数である.

図の色は、1または30000未満の整数にすぎない.

I/O例
nmimages正解23[1,2,3],[3,2,1]532[1,2],[1,2],[4,5]4
I/O例#1
前に述べたように.
I/O例#2
与えられた画像は、以下のように表すことができる.

したがって、この画像には4つの領域が含まれています.

に答える

ブラウズコンテキストを再帰的に呼び出すことで解決します.Pythonでは、リターンコール制限がありますので、予め指定する必要があります.

コード#コード#

import sys
sys.setrecursionlimit(30000)

def solution(n, m, image):
    answer = 0
    for i in range(n):
        for j in range(m):
            if image[i][j] != 0:
                answer += 1 
                area_check(image[i][j],i,j,n-1,m-1,image)
    return answer

def area_check(t,i,j,n,m,image):
    image[i][j] = 0
    #상
    if 0 <= i-1 <=n and image[i-1][j] == t:
        area_check(t,i-1,j,n,m,image)
    #하
    if i+1 <= n and image[i+1][j] == t:
        area_check(t,i+1,j,n,m,image)
    #좌
    if 0 <= j-1 <= m and image[i][j-1] == t:
        area_check(t,i,j-1,n,m,image)
    #우
    if j+1 <= m and image[i][j+1] == t:
        area_check(t,i,j+1,n,m,image)