[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)