Connected Cells in a Grid

  • + 0 comments

    I seem to be the only one using the Union Find algorithm:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct {
            size_t *branches;
            size_t num_branches;
    } forest_t;
    
    forest_t new_forest(size_t max_num_trees) {
            forest_t forest = {.branches =
                                   (size_t *)malloc(max_num_trees * sizeof(size_t)),
                               .num_branches = max_num_trees};
            for (size_t i = 0; i < max_num_trees; i++)
                    forest.branches[i] = i;
            return forest;
    }
    
    size_t find_root(const forest_t forest, size_t node_index) {
            while (forest.branches[node_index] != node_index) {
                    node_index = forest.branches[node_index];
            }
            return node_index;
    }
    
    void connect_trees(forest_t forest, size_t left_node, size_t right_node) {
            left_node = find_root(forest, left_node);
            right_node = find_root(forest, right_node);
            forest.branches[right_node] = left_node;
    }
    
    void free_forest(forest_t forest) {
            free(forest.branches);
    }
    
    size_t max(size_t left, size_t right) {
            return left > right ? left : right;
    }
    
    int main() {
            size_t num_rows;
            size_t num_columns;
            scanf("%lu", &num_rows);
            scanf("%lu", &num_columns);
            char *grid = (char *)malloc(num_rows * num_columns + 1);
            {
                    for (size_t i = 0; i < num_rows; i++) {
                            for (size_t j = 0; j < num_columns; j++) {
                                    int c;
                                    scanf("%d", &c);
                                    grid[i * num_columns + j] = c+'0';
                            }
                    }
            }
            forest_t forest = new_forest(num_rows * num_columns);
            for (size_t i = 0; i < num_rows * num_columns; i++) {
                    ssize_t row = i / num_columns;
                    ssize_t col = i % num_columns;
                    for (size_t k = 0; k < 8; k++) {
                            size_t j = (k + 6) % 9;
                            ssize_t row_neighbor = row + (ssize_t)(j / 3) - 1;
                            ssize_t col_neighbor = col + (ssize_t)(j % 3) - 1;
                            size_t l = row_neighbor * num_columns + col_neighbor;
                            if (row_neighbor >= 0 && row_neighbor < num_rows &&
                                col_neighbor >= 0 && col_neighbor < num_columns &&
                                grid[i] == grid[l] &&
                                find_root(forest, i) != find_root(forest, l)) {
                                    connect_trees(forest, i, l);
                            }
                    }
            }
            size_t *root_counts =
                (size_t *)calloc(num_rows * num_columns, sizeof(size_t));
            for (size_t i = 0; i < num_rows * num_columns; i++) {
                    if (grid[i] == '1') {
                            root_counts[find_root(forest, i)]++;
                    }
            }
            size_t max_count = 0;
            for (size_t i = 0; i < num_rows * num_columns; i++) {
                    max_count = max(max_count, root_counts[i]);
            }
            printf("%lu\n", max_count);
    }