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