白駿2667号団地番号



質問リンク

説明:


基本的にBFSで解きます.
行列時と開始時にcountを用いて家具数を求める.
main文では、図中に1があるがまだアクセスしていない場所がある場合は、housecnt++の後に入るように設計されています.

ソースコード

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dx[] = { -1,1,0,0 };
bool visited[26][26];
int dy[] = { 0,0,1,-1 };
int graph[26][26];
	int cnt = 0;
int k;
int houseCnt = 0;
int houseNum[10000];
void bfs(int start,int now) {
	queue<pair<int, int>> q;
	visited[start][now] = true;
	q.push({ start,now });

	houseNum[houseCnt]++;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (graph[ny][nx] == 0) continue;
			if (nx < 0 || nx >= k || ny < 0 || ny >= k) continue;

			if (!visited[ny][nx]) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				houseNum[houseCnt]++;
			}
		}


	}

	
}
int main()
{

	cin >> k;
	for (int y = 0; y < k; y++) {
		for (int x = 0; x < k; x++) {
			scanf("%1d", &graph[y][x]);
		}
	}
	
	for (int y = 0; y < k; y++) {
		for (int x = 0; x < k; x++) {
			if (visited[y][x] == false && graph[y][x] == 1) {
				houseCnt++;
				bfs(y,x);

			}
	
		}
	}


	cout << houseCnt << endl;
	sort(houseNum + 1, houseNum + houseCnt+1);

	for (int i = 1; i <= houseCnt; i++) {
		cout << houseNum[i] << endl;
	}

	return 0;
}