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

#define SEED 0xDEADBEEFull
#define ROWS 100
#define COLS 100
#define COLORS_NUM 3

#define VEC_INIT_CAPACITY 15
#define MATRIX_AT(matrix, i, j) (matrix)[(i) * COLS + (j)]

uint32_t LCGRand()
{
    static uint64_t seed = SEED;
    seed = seed * 6364136223846793005 + 1442695040888963407;
    return seed >> 32;
}

typedef struct Node_s {
    uint32_t color;
    uint32_t isVisited;
} Node;

typedef struct Coords_s {
    intptr_t i;
    intptr_t j;
} Coords;

typedef struct Vec_s {
    Coords *arr;
    size_t curSize;
    size_t curCapacity;
} Vec;

Vec *vec_create()
{
    Vec *vec = calloc(1, sizeof(Vec));
    if (!vec) {
        return NULL;
    }
    vec->arr = calloc(VEC_INIT_CAPACITY, sizeof(Coords));
    if (!vec->arr) {
        free(vec);
        return NULL;
    }
    vec->curCapacity = VEC_INIT_CAPACITY;
    vec->curSize = 0;
    return vec;
}

int vec_push(Vec *vec, intptr_t i, intptr_t j)
{
    if (vec->curSize >= vec->curCapacity) {
        size_t newCapacity = vec->curCapacity * 2;
        Coords *oldArr = vec->arr;
        vec->arr = realloc(vec->arr, newCapacity * sizeof(Coords));
        if (!vec->arr) {
            vec->arr = oldArr;
            return 0;
        }
        vec->curCapacity = newCapacity;
    }

    vec->arr[vec->curSize].i = i;
    vec->arr[vec->curSize].j = j;
    vec->curSize++;
    return 1;
}

Coords *vec_pop(Vec *vec)
{
    if (vec->curSize > 0) {
        return &vec->arr[vec->curSize-- - 1];
    } else {
        return NULL;
    }
}

void vec_clear(Vec *vec)
{
    vec->curSize = 0;
}

void vec_delete(Vec *vec)
{
    if (vec) {
        if (vec->arr) {
            free(vec->arr);
        }
        free(vec);
    }
}

inline int isValidCoords(intptr_t i, intptr_t j)
{
    return (i >= 0) && (i < ROWS) && (j >= 0) && (j < COLS);
}

size_t visitNode(Node *matrix, intptr_t i, intptr_t j)
{
    static const int MOVES[][2] = {
        { -1, 0 },
        { +1, 0 },
        { 0, -1 },
        { 0, +1 },
    };

    Vec *vec = vec_create();
    if (!vec) {
        goto OOM;
    }

    if (!vec_push(vec, i, j)) {
        goto OOM;
    }

    size_t blockSize = 0;
    uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
    MATRIX_AT(matrix, i, j).isVisited = 1;
    while (vec->curSize > 0) {
        Coords *coords = vec_pop(vec);
        i = coords->i;
        j = coords->j;

        blockSize++;

        for (size_t moveIdx = 0; moveIdx < sizeof(MOVES) / sizeof(MOVES[0]); moveIdx++) {
            intptr_t movedI = i + MOVES[moveIdx][0], movedJ = j + MOVES[moveIdx][1];
            if (isValidCoords(movedI, movedJ)) {
                Node *adjNode = &MATRIX_AT(matrix, movedI, movedJ);
                if (adjNode->color == targetColor && !adjNode->isVisited) {
                    MATRIX_AT(matrix, movedI, movedJ).isVisited = 1;
                    if (!vec_push(vec, movedI, movedJ)) {
                        goto OOM;
                    }
                }
            }
        }
    }

    vec_delete(vec);
    return blockSize;

OOM:
    perror("OOM");
    vec_delete(vec);
    exit(EXIT_FAILURE);
}

void print_matrix(Node *matrix)
{
    for (size_t i = 0; i < ROWS; i++) {
        for (size_t j = 0; j < COLS; j++) {
            putchar(MATRIX_AT(matrix, i, j).color + '0');
        }
        putchar('\n');
    }
}

int main()
{
    Node *matrix = calloc(ROWS * COLS, sizeof(Node));
    for (size_t i = 0; i < ROWS * COLS; i++) {
        matrix[i].color = LCGRand() % COLORS_NUM;
    }
    //print_matrix(matrix);

    size_t maxAdjNodes = 0;
    for (intptr_t i = 0; i < ROWS; i++) {
        for (intptr_t j = 0; j < COLS; j++) {
            if (!MATRIX_AT(matrix, i, j).isVisited) {
                size_t adjNodes = visitNode(matrix, i, j);
                if (maxAdjNodes < adjNodes) {
                    maxAdjNodes = adjNodes;
                }
            }
        }
    }

    printf("Max block size: %zd\n", maxAdjNodes);
    return 0;
}