fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stdint.h>
  4. #include <time.h>
  5.  
  6. #define ROWS 10000
  7. #define COLS 10000
  8. #define COLORS_NUM 3
  9. #define SEED 0xDEADBEEFull
  10.  
  11. #define VEC_INIT_CAPACITY 100
  12. #define MATRIX_AT(matrix, i, j) (matrix)[(i) * COLS + (j)]
  13.  
  14. uint32_t LCGRand()
  15. {
  16.     static uint64_t seed = SEED;
  17.     seed = seed * 6364136223846793005 + 1442695040888963407;
  18.     return seed >> 32;
  19. }
  20.  
  21. typedef struct Node_s {
  22.     uint32_t color;
  23.     uint32_t isVisited;
  24. } Node;
  25.  
  26. typedef struct Coords_s {
  27.     intptr_t i;
  28.     intptr_t j;
  29. } Coords;
  30.  
  31. typedef struct Vec_s {
  32.     Coords *arr;
  33.     size_t curSize;
  34.     size_t curCapacity;
  35. } Vec;
  36.  
  37. Vec *vec_create()
  38. {
  39.     Vec *vec = malloc(sizeof(Vec));
  40.     if (!vec) {
  41.         return NULL;
  42.     }
  43.     vec->arr = malloc(VEC_INIT_CAPACITY * sizeof(Coords));
  44.     if (!vec->arr) {
  45.         free(vec);
  46.         return NULL;
  47.     }
  48.     vec->curCapacity = VEC_INIT_CAPACITY;
  49.     vec->curSize = 0;
  50.     return vec;
  51. }
  52.  
  53. int vec_push(Vec *vec, intptr_t i, intptr_t j)
  54. {
  55.     if (vec->curSize >= vec->curCapacity) {
  56.         size_t newCapacity = vec->curCapacity * 2;
  57.         Coords *oldArr = vec->arr;
  58.         vec->arr = realloc(vec->arr, newCapacity * sizeof(Coords));
  59.         if (!vec->arr) {
  60.             vec->arr = oldArr;
  61.             return 0;
  62.         }
  63.         vec->curCapacity = newCapacity;
  64.     }
  65.  
  66.     vec->arr[vec->curSize].i = i;
  67.     vec->arr[vec->curSize].j = j;
  68.     vec->curSize++;
  69.     return 1;
  70. }
  71.  
  72. Coords *vec_pop(Vec *vec)
  73. {
  74.     if (vec->curSize > 0) {
  75.         return &vec->arr[vec->curSize-- - 1];
  76.     } else {
  77.         return NULL;
  78.     }
  79. }
  80.  
  81. void vec_clear(Vec *vec)
  82. {
  83.     vec->curSize = 0;
  84. }
  85.  
  86. void vec_delete(Vec *vec)
  87. {
  88.     if (vec) {
  89.         if (vec->arr) {
  90.             free(vec->arr);
  91.         }
  92.         free(vec);
  93.     }
  94. }
  95.  
  96. inline int isValidCoords(intptr_t i, intptr_t j)
  97. {
  98.     return (i >= 0) && (i < ROWS) && (j >= 0) && (j < COLS);
  99. }
  100.  
  101. size_t visitNode(Node *matrix, intptr_t i, intptr_t j)
  102. {
  103.     static const int MOVES[][2] = {
  104.         { -1, 0 },
  105.         { +1, 0 },
  106.         { 0, -1 },
  107.         { 0, +1 },
  108.     };
  109.  
  110.     static Vec *vec = NULL;
  111.     if (!vec) {
  112.         vec = vec_create();
  113.         if (!vec) {
  114.             goto OOM;
  115.         }
  116.     }
  117.  
  118.     if (!vec_push(vec, i, j)) {
  119.         goto OOM;
  120.     }
  121.  
  122.     size_t blockSize = 0;
  123.     uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
  124.     MATRIX_AT(matrix, i, j).isVisited = 1;
  125.     while (vec->curSize > 0) {
  126.         Coords *coords = vec_pop(vec);
  127.         i = coords->i;
  128.         j = coords->j;
  129.  
  130.         blockSize++;
  131.  
  132.         for (size_t moveIdx = 0; moveIdx < sizeof(MOVES) / sizeof(MOVES[0]); moveIdx++) {
  133.             intptr_t movedI = i + MOVES[moveIdx][0], movedJ = j + MOVES[moveIdx][1];
  134.             if (isValidCoords(movedI, movedJ)) {
  135.                 Node *adjNode = &MATRIX_AT(matrix, movedI, movedJ);
  136.                 if (adjNode->color == targetColor && !adjNode->isVisited) {
  137.                     adjNode->isVisited = 1;
  138.                     if (!vec_push(vec, movedI, movedJ)) {
  139.                         goto OOM;
  140.                     }
  141.                 }
  142.             }
  143.         }
  144.     }
  145.  
  146.     vec_clear(vec);
  147.     return blockSize;
  148.  
  149. OOM:
  150.     perror("OOM");
  151.     vec_delete(vec);
  152.     exit(EXIT_FAILURE);
  153. }
  154.  
  155. void print_matrix(Node *matrix)
  156. {
  157.     for (size_t i = 0; i < ROWS; i++) {
  158.         for (size_t j = 0; j < COLS; j++) {
  159.             putchar(MATRIX_AT(matrix, i, j).color + '0');
  160.         }
  161.         putchar('\n');
  162.     }
  163. }
  164.  
  165. int main()
  166. {
  167.     clock_t start = clock();
  168.     Node *matrix = malloc(ROWS * COLS * sizeof(Node));
  169.     for (size_t i = 0; i < ROWS * COLS; i++) {
  170.         matrix[i].color = LCGRand() % COLORS_NUM;
  171.         matrix[i].isVisited = 0;
  172.     }
  173.     //print_matrix(matrix);
  174.  
  175.     size_t maxAdjNodes = 0;
  176.     for (intptr_t i = 0; i < ROWS; i++) {
  177.         for (intptr_t j = 0; j < COLS; j++) {
  178.             if (!MATRIX_AT(matrix, i, j).isVisited) {
  179.                 size_t adjNodes = visitNode(matrix, i, j);
  180.                 if (maxAdjNodes < adjNodes) {
  181.                     maxAdjNodes = adjNodes;
  182.                 }
  183.             }
  184.         }
  185.     }
  186.  
  187.     printf("Max block size: %zd\ntime: %ld", maxAdjNodes, (clock() - start) / (CLOCKS_PER_SEC / 1000));
  188.     free(matrix);
  189.     return 0;
  190. }
  191.  
Success #stdin #stdout 2.75s 782744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max block size: 93
time: 2727
https://ideone.com/bd4g1I
language:
C (clang 8.0)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!