白俊解答-番号2667回だけ貼る

📜 理解问题

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

💡 問題の再定義

集まったつぼを縛り、昇順につぼの中の家の数を印刷します.

▼▼▼計画作成

bfsを使用すると問題を解決できます.(0,0)から(N−1,N−1)まで、家があるかどうかをチェックし、家が存在する場合は、bfsを実行してどれだけの家が集まっているかをチェックし、結果配列に保存します.すべての作業が完了したら、結果値を昇順に並べ替え、順番に出力します.

💻 計画の実行

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    city = []
    visited = [[0 for _ in range(N)] for _ in range(N)]
    open_set = []
    result = []
    count = 0

    for _ in range(N):
        city.append(list(map(int, sys.stdin.readline().rstrip())))

    for i in range(N):
        for j in range(N):
            if city[i][j] == 1 and visited[i][j] == 0:
                open_set.append([i, j])
                visited[i][j] = 1
                count += 1

            while open_set:
                y, x = open_set.pop(0)
                if y - 1 >= 0 and city[y - 1][x] == 1 and visited[y - 1][x] == 0:
                    open_set.append([y - 1, x])
                    visited[y - 1][x] = 1
                    count += 1
                if y + 1 < N and city[y + 1][x] == 1 and visited[y + 1][x] == 0:
                    open_set.append([y + 1, x])
                    visited[y + 1][x] = 1
                    count += 1
                if x - 1 >= 0 and city[y][x - 1] == 1 and visited[y][x - 1] == 0:
                    open_set.append([y, x - 1])
                    visited[y][x - 1] = 1
                    count += 1
                if x + 1 < N and city[y][x + 1] == 1 and visited[y][x + 1] == 0:
                    open_set.append([y, x + 1])
                    visited[y][x + 1] = 1
                    count += 1
            if count > 0:
                result.append(count)
                count = 0
    print(len(result))
    print(*sorted(result), sep='\n')

🤔 振り返る

まず、家があるかどうかを一つ一つチェックする操作はO(N)²)いいですよ.この時家を見つけた時、bfsはO(V)だった.²)いいですよ.上記の「家があるかどうかを検索する」タスクでは、訪問した家はbfsを実行しないため、最終時間の複雑さはO(N)である.²)いいですよ.この問題の入力は5<=N<=25であり,Pythonで実現しても十分な時間がある.