#include <queue>
#include <iostream>
#include <memory>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

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

static size_t ROWS = 1;
static size_t COLS = 1;
static const uint32_t COLORS_NUM = 3;
static uint64_t SEED = 0xDEADBEEFull;
static uint64_t next = SEED;
uint32_t LCGRand()
{
    next = next * 6364136223846793005 + 1442695040888963407;
    return next >> 32;
}

struct Block {
    typedef std::shared_ptr<Block> Ptr;

    uint32_t color;
    size_t size;
    Ptr redir;
};

size_t main_cpp()
{
    std::vector<Block::Ptr> up_row(COLS);
    size_t max_size = 0;

    clock_t start = clock();
    for (size_t row = 0; row < ROWS; row++) {
        Block::Ptr left;

        for (size_t col = 0; col < COLS; col++) {
            uint32_t color = LCGRand() % COLORS_NUM;

            Block::Ptr &up = up_row[col];
            while (up && up->redir)
                up = up->redir;

            Block::Ptr cur;
            if (left && (left->color == color)) {
                cur = left;

                if (up && (up->color == color) && (up != left)) {
                    left->size += up->size;
                    up->redir = left;
                }
            } else if (up && (up->color == color)) {
                cur = up;
            } else {
                cur = std::make_shared<Block>(Block{ color, 0, nullptr });
            }

            max_size = std::max(max_size, ++cur->size);
            left = up = cur;
        }
    }

    //std::cout << "Max block size: " << max_size << std::endl
    //    << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
    return max_size;
}

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 = (Vec*)malloc(sizeof(Vec));
    if (!vec) {
        return NULL;
    }
    vec->arr = (Coords*)malloc(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 = (Coords*)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 },
    };

    size_t blockSize = 0;
    uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
    static Vec *vec = NULL;
    if (!vec) {
        vec = vec_create();
        if (!vec) {
            goto OOM;
        }
    }

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

    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) {
                    adjNode->isVisited = 1;
                    if (!vec_push(vec, movedI, movedJ)) {
                        goto OOM;
                    }
                }
            }
        }
    }

    vec_clear(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');
    }
}

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

    clock_t start = clock();
    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;
                }
            }
        }
    }

    free(matrix);
    //printf("Max block size: %zd\ntime: %ld", maxAdjNodes, (clock() - start) / (CLOCKS_PER_SEC / 1000));
    return maxAdjNodes;
}

int main()
{
    for (ROWS = 1; ROWS < 10; ROWS++) {
        for (COLS = 1; COLS < 100; COLS++) {
            for (int i = -5; i < 5; i++) {
                next = SEED + i;
                size_t res_c = main_c();
                next = SEED + i;
                size_t res_cpp = main_cpp();
                if (res_c != res_cpp) {
                    std::cout << "ERROR FOR SEED = " << SEED + i
                        << ", ROWS = " << ROWS << ", COLS = " << COLS << "(" << res_c << " != " << res_cpp << ")" << std::endl;
                    return EXIT_FAILURE;
                }
            }
        }
    }
    std::cout << "OK" << std::endl;
    return EXIT_SUCCESS;
}