Lv3 FloodFill

1492 ワード

質問する


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)