#include <stdio.h>
#include <stdlib.h>
int Box[27][27]; int Visited[27][27]; Queue[9000000]; int H_cnt[500];
int Queue_cnt, Qx, Qy, rear, front, H, N, Sx, Sy, cnt;
void Q_Init() {
for (int i = 0; i < 9000000; i++) { Queue[i] = 0; Queue_cnt = 0; rear = 0; front = 0; Qx = 0; Qy = 0; }
}
int isEmpty() {
if (rear == front) { return 1; }
else { return 0; }
}
void push(int a, int b) {
if (rear < 9000000) {
Queue[rear++] = a; Queue[rear++] = b; Queue_cnt++;
}
}
void pop() {
if (!isEmpty()) {
Qx = Queue[front++]; Qy = Queue[front++]; Queue_cnt--;
}
}
void Start_Point() {//Box를 돌면서 최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
int flag = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (Box[i][j] == 1 && flag == 0) { Sx = i; Sy = j; flag = 1; }
}
}
}
int bfs(int a, int b) {
push(a, b); int House = 0;
while (!isEmpty()) {
pop(); a = Qx; b = Qy;
if (Box[a][b] != 0) {//pop 해 준 항목은 0으로 함.
House++; H--; Box[a][b] = 0;
}
//if(상하좌우에 1이 있고, 방문한 기록이 없으면,
//--> 해당 셀의 주소를 큐에 push 하고, 방문한 기록을 남기고, cnt++ 해 준다)
if (Box[a + 1][b] == 1 && Visited[a + 1][b] != 1) { push(a + 1, b); Visited[a + 1][b]; }
if (Box[a - 1][b] == 1 && Visited[a - 1][b] != 1) { push(a - 1, b); Visited[a - 1][b]; }
if (Box[a][b + 1] == 1 && Visited[a][b + 1] != 1) { push(a, b + 1); Visited[a][b + 1]; }
if (Box[a][b - 1] == 1 && Visited[a][b - 1] != 1) { push(a, b - 1); Visited[a][b - 1]; }
}
return House;
}
void swap(int a, int b) {
int tmp = a; a = b; b = tmp;
}
int main() {
for (int i = 1; i <= N; i++) { //0 번째 행과 0번째 열은 모두 0으로 해 준다.
for (int j = 1; j <= N; j++) {
scanf("%1d", &Box
[i
][j
]); if (Box[i][j] == 1) { H++; } //집의 총 개수 H를 카운트 해 준다
}
}
// H : 집의 개수. 집의 개수가 0이 될때 까지 돌린다 (집의 개수는 방문 할때마다 H-- 해 준다)
while (H) {
Start_Point(); //최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
//단지 0, 1, 2번의 집의 개수 : H_cnt[0], H_cnt[1], H_cnt[2] ...
H_cnt[cnt++] = bfs(Sx, Sy);
}
//H_cnt[] 배열의 각 요소를 오름차순으로 정렬
for (int k = 0; k < cnt; k++) { //단지 개수만큼 돌린다
for (int i = 0; i < cnt; i++) {
if (H_cnt[i] > H_cnt[i + 1]) { swap(H_cnt[i], H_cnt[i + 1]); }
}
}
for (int i = 0; i < cnt; i++) { // 단지 별 가장 작은 수 부터 출력
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBCb3hbMjddWzI3XTsgaW50IFZpc2l0ZWRbMjddWzI3XTsgUXVldWVbOTAwMDAwMF07IGludCBIX2NudFs1MDBdOwppbnQgUXVldWVfY250LCBReCwgUXksIHJlYXIsIGZyb250LCBILCBOLCBTeCwgU3ksIGNudDsKCnZvaWQgUV9Jbml0KCkgewoJZm9yIChpbnQgaSA9IDA7IGkgPCA5MDAwMDAwOyBpKyspIHsgUXVldWVbaV0gPSAwOyBRdWV1ZV9jbnQgPSAwOyByZWFyID0gMDsgZnJvbnQgPSAwOyBReCA9IDA7IFF5ID0gMDsgfQp9CmludCBpc0VtcHR5KCkgewoJaWYgKHJlYXIgPT0gZnJvbnQpIHsgcmV0dXJuIDE7IH0KCWVsc2UgeyByZXR1cm4gMDsgfQp9CnZvaWQgcHVzaChpbnQgYSwgaW50IGIpIHsKCWlmIChyZWFyIDwgOTAwMDAwMCkgewoJCVF1ZXVlW3JlYXIrK10gPSBhOyBRdWV1ZVtyZWFyKytdID0gYjsgUXVldWVfY250Kys7Cgl9Cn0Kdm9pZCBwb3AoKSB7CglpZiAoIWlzRW1wdHkoKSkgewoJCVF4ID0gUXVldWVbZnJvbnQrK107IFF5ID0gUXVldWVbZnJvbnQrK107IFF1ZXVlX2NudC0tOwoJfQp9CnZvaWQgU3RhcnRfUG9pbnQoKSB7Ly9Cb3jrpbwg64+M66m07IScIOy1nOy0iOuhnCDrp4zrgpjripQgMeydhCBTdGFydF9Qb2ludOuhnCDtlbTshJwgU3gsIFN5IOqwkuydhCDshKTsoJXtlZjripQg7ZWo7IiYCglpbnQgZmxhZyA9IDA7Cglmb3IgKGludCBpID0gMTsgaSA8PSBOOyBpKyspIHsKCQlmb3IgKGludCBqID0gMTsgaiA8PSBOOyBqKyspIHsKCQkJaWYgKEJveFtpXVtqXSA9PSAxICYmIGZsYWcgPT0gMCkgeyBTeCA9IGk7IFN5ID0gajsgZmxhZyA9IDE7IH0KCQl9Cgl9Cn0KaW50IGJmcyhpbnQgYSwgaW50IGIpIHsKCXB1c2goYSwgYik7IGludCBIb3VzZSA9IDA7Cgl3aGlsZSAoIWlzRW1wdHkoKSkgewoJCXBvcCgpOyBhID0gUXg7IGIgPSBReTsgCgkJaWYgKEJveFthXVtiXSAhPSAwKSB7Ly9wb3Ag7ZW0IOykgCDtla3rqqnsnYAgMOycvOuhnCDtlaguCgkJCUhvdXNlKys7IEgtLTsgQm94W2FdW2JdID0gMDsKCQl9CgkJLy9pZijsg4HtlZjsoozsmrDsl5AgMeydtCDsnojqs6AsIOuwqeusuO2VnCDquLDroZ3snbQg7JeG7Jy866m0LCAKICAgICAgICAvLy0tPiDtlbTri7kg7IWA7J2YIOyjvOyGjOulvCDtgZDsl5AgcHVzaCDtlZjqs6AsIOuwqeusuO2VnCDquLDroZ3snYQg64Ko6riw6rOgLCBjbnQrKyDtlbQg7KSA64ukKQoJCWlmIChCb3hbYSArIDFdW2JdID09IDEgJiYgVmlzaXRlZFthICsgMV1bYl0gIT0gMSkgeyBwdXNoKGEgKyAxLCBiKTsgVmlzaXRlZFthICsgMV1bYl07IH0KCQlpZiAoQm94W2EgLSAxXVtiXSA9PSAxICYmIFZpc2l0ZWRbYSAtIDFdW2JdICE9IDEpIHsgcHVzaChhIC0gMSwgYik7IFZpc2l0ZWRbYSAtIDFdW2JdOyB9CgkJaWYgKEJveFthXVtiICsgMV0gPT0gMSAmJiBWaXNpdGVkW2FdW2IgKyAxXSAhPSAxKSB7IHB1c2goYSwgYiArIDEpOyBWaXNpdGVkW2FdW2IgKyAxXTsgfQoJCWlmIChCb3hbYV1bYiAtIDFdID09IDEgJiYgVmlzaXRlZFthXVtiIC0gMV0gIT0gMSkgeyBwdXNoKGEsIGIgLSAxKTsgVmlzaXRlZFthXVtiIC0gMV07IH0KCX0KCXJldHVybiBIb3VzZTsKfQp2b2lkIHN3YXAoaW50IGEsIGludCBiKSB7CglpbnQgdG1wID0gYTsgYSA9IGI7IGIgPSB0bXA7Cn0KaW50IG1haW4oKSB7CglzY2FuZigiJWQiLCAmTik7Cglmb3IgKGludCBpID0gMTsgaSA8PSBOOyBpKyspIHsgLy8wIOuyiOynuCDtlonqs7wgMOuyiOynuCDsl7TsnYAg66qo65GQIDDsnLzroZwg7ZW0IOykgOuLpC4KCQlmb3IgKGludCBqID0gMTsgaiA8PSBOOyBqKyspIHsKCQkJc2NhbmYoIiUxZCIsICZCb3hbaV1bal0pOwoJCQlpZiAoQm94W2ldW2pdID09IDEpIHsgSCsrOyB9IC8v7KeR7J2YIOy0nSDqsJzsiJggSOulvCDsubTsmrTtirgg7ZW0IOykgOuLpAoJCX0KCX0KICAgIC8vIEggOiDsp5HsnZgg6rCc7IiYLiDsp5HsnZgg6rCc7IiY6rCAIDDsnbQg65Cg65WMIOq5jOyngCDrj4zrprDri6QgKOynkeydmCDqsJzsiJjripQg67Cp66y4IO2VoOuVjOuniOuLpCBILS0g7ZW0IOykgOuLpCkKCXdoaWxlIChIKSB7ICAKCQlTdGFydF9Qb2ludCgpOyAvL+y1nOy0iOuhnCDrp4zrgpjripQgMeydhCBTdGFydF9Qb2ludOuhnCDtlbTshJwgU3gsIFN5IOqwkuydhCDshKTsoJXtlZjripQg7ZWo7IiYCiAgICAgICAgLy/ri6jsp4AgMCwgMSwgMuuyiOydmCDsp5HsnZgg6rCc7IiYIDogIEhfY250WzBdLCBIX2NudFsxXSwgSF9jbnRbMl0gLi4uCgkJSF9jbnRbY250KytdID0gYmZzKFN4LCBTeSk7IAoJfQoJLy9IX2NudFtdIOuwsOyXtOydmCDqsIEg7JqU7IaM66W8IOyYpOumhOywqOyInOycvOuhnCDsoJXroKwKCWZvciAoaW50IGsgPSAwOyBrIDwgY250OyBrKyspIHsgLy/ri6jsp4Ag6rCc7IiY66eM7YG8IOuPjOumsOuLpAoJCWZvciAoaW50IGkgPSAwOyBpIDwgY250OyBpKyspIHsKCQkJaWYgKEhfY250W2ldID4gSF9jbnRbaSArIDFdKSB7IHN3YXAoSF9jbnRbaV0sIEhfY250W2kgKyAxXSk7IH0KCQl9Cgl9CglwcmludGYoIiVkIiwgY250KTsgLy/ri6jsp4Ag6rCc7IiYIOy2nOugpQoJZm9yIChpbnQgaSA9IDA7IGkgPCBjbnQ7IGkrKykgeyAvLyDri6jsp4Ag67OEIOqwgOyepSDsnpHsnYAg7IiYIOu2gO2EsCDstpzroKUKCQlwcmludGYoIlxuJWQiLCBIX2NudFtpXSk7Cgl9Cn0=