白駿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;
}
Reference
この問題について(白駿2667号団地番号), 我々は、より多くの情報をここで見つけました
https://velog.io/@trevor522/백준-2667번-단지번호붙이기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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;
}
Reference
この問題について(白駿2667号団地番号), 我々は、より多くの情報をここで見つけました https://velog.io/@trevor522/백준-2667번-단지번호붙이기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol