Quick actions

cmd+k|ctrl+k

Navigation

Languages

BFS Check size

Snippet info

Language

C

Visibility

public

Author

kim112mgxld

Created

2020-08-19T09:58:29Z

Updated

2020-08-20T01:57:37Z

#include <stdio.h>
#include <stdlib.h>

#define MAX 25
#define INFI 99999

typedef struct _Pos {
    int x;
    int y;
} Pos;

int map[MAX][MAX];

int count = 0;
int number[MAX * MAX];

int posX[] = {-1, 1, 0, 0};
int posY[] = {0, 0, -1, 1};

int compare (void * first, void * second) {
    int value1 = *(int*)first;
    int value2 = *(int*)second;
    
    if (value1 < value2) {
        return -1;
    } else if (value1 > value2) {
        return 1;
    }
    
    return 0;
}

int BFS (int x, int y, int N) {
    Pos queue[INFI];
    int size = 1, rear = -1, front = -1;
    
    rear++;
    queue[rear].x = x;
    queue[rear].y = y;
    
    map[y][x] = 0;
    
    while (front < rear) {
        front++;
        int xx = queue[front].x;
        int yy = queue[front].y;
        
        for (int i = 0; i < 4; i++) {
            int newX = xx + posX[i];
            int newY = yy + posY[i];
            
            if (newX >= 0 && newX < N && newY >= 0 && newY < N) {
                if (map[newY][newX] == 1) {
                    rear++;
                    size++;
                    queue[rear].x = newX;
                    queue[rear].y = newY;
                    
                    map[newY][newX] = 0;
                }
            }
        }
    }
    
    return size;
}

int main(void) {
    int N = 0;
    
    scanf("%d", &N);
    
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            scanf("%1d", &map[y][x]);
        }
    }
    
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            if (map[y][x] == 1) {
                number[count++] = BFS(x, y, N);
            }
        }
    }
    
    printf("%d\n", count);
    
    qsort(number, sizeof(number) / sizeof(int), sizeof(int), compare);
    
    for (int i = 0; i < MAX * MAX; i++) {
        if (number[i] == 0) {
            continue;
        }
        
        printf("%d\n", number[i]);
    }
    
    return 0;
}
INFO