[python]伯準/番号のみ/2667番/グラフ


質問する
番号付き問題リンクのみ
図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.

入力
1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
しゅつりょく
最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.
3
7
8
9
方法

  • 二重複文で各要素を探索する

  • 要素が1の場合は0に変更し、単数を1に初期化してsearch関数を実行します.

  • search関数は,現在位置に基づいて上下左右をブラウズし,1時に0となり,その位置を再帰的にsearch関数を実行する.
    search関数実行時、セル数をカウントして記録する

  • search関数が終わると,初めて出会った1と上下左右に接続されたすべての1が0になり,個数を答えに追加するだけで二重複文を探索し続ける.
  • コード#コード#
    
    # url : https://www.acmicpc.net/problem/2667
    # 난이도 : silver 1
    
    import sys
    
    def search(i,j):
        global house
        if i < n-1 and map[i+1][j] == 1:
            house += 1
            map[i+1][j] = 0
            search(i+1,j)
        if j < n-1 and map[i][j+1] == 1:
            house += 1
            map[i][j+1] = 0
            search(i,j+1)
        if i > 0 and map[i-1][j] == 1:
            house += 1
            map[i-1][j] = 0
            search(i-1,j)
        if j > 0 and map[i][j-1] == 1:
            house += 1
            map[i][j-1] = 0
            search(i,j-1)
    
    n = int(input())
    
    map = [[ int(i) for i in sys.stdin.readline().rstrip()] for _ in range(n)]
    
    answer = []
    for i in range(n):
        for j in range(n):
            if map[i][j] == 1:
                map[i][j] = 0
                house = 1
                search(i,j)
                answer.append(house)
    
    
    print(len(answer))
    
    for i in sorted(answer):
        print(i)