fork(1) download
copy 
  1. #include <queue>
  2. #include <iostream>
  3. #include <memory>
  4. #include <vector>
  5. #include <time.h>
  6. #include <stdlib.h>
  7. #include <stdio.h>
  8. #include <stdint.h>
  9.  
  10. #define VEC_INIT_CAPACITY 100
  11. #define MATRIX_AT(matrix, i, j) (matrix)[(i) * COLS + (j)]
  12.  
  13. static size_t ROWS = 1;
  14. static size_t COLS = 1;
  15. static const uint32_t COLORS_NUM = 3;
  16. static uint64_t SEED = 0xDEADBEEFull;
  17. static uint64_t next = SEED;
  18. uint32_t LCGRand()
  19. {
  20.     next = next * 6364136223846793005 + 1442695040888963407;
  21.     return next >> 32;
  22. }
  23.  
  24. struct Block {
  25.     typedef std::shared_ptr<Block> Ptr;
  26.  
  27.     uint32_t color;
  28.     size_t size;
  29.     Ptr redir;
  30. };
  31.  
  32. size_t main_cpp()
  33. {
  34.     std::vector<Block::Ptr> up_row(COLS);
  35.     size_t max_size = 0;
  36.  
  37.     clock_t start = clock();
  38.     for (size_t row = 0; row < ROWS; row++) {
  39.         Block::Ptr left;
  40.  
  41.         for (size_t col = 0; col < COLS; col++) {
  42.             uint32_t color = LCGRand() % COLORS_NUM;
  43.  
  44.             Block::Ptr &up = up_row[col];
  45.             while (up && up->redir)
  46.                 up = up->redir;
  47.  
  48.             Block::Ptr cur;
  49.             if (left && (left->color == color)) {
  50.                 cur = left;
  51.  
  52.                 if (up && (up->color == color) && (up != left)) {
  53.                     left->size += up->size;
  54.                     up->redir = left;
  55.                 }
  56.             } else if (up && (up->color == color)) {
  57.                 cur = up;
  58.             } else {
  59.                 cur = std::make_shared<Block>(Block{ color, 0, nullptr });
  60.             }
  61.  
  62.             max_size = std::max(max_size, ++cur->size);
  63.             left = up = cur;
  64.         }
  65.     }
  66.  
  67.     //std::cout << "Max block size: " << max_size << std::endl
  68.     //    << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
  69.     return max_size;
  70. }
  71.  
  72. typedef struct Node_s {
  73.     uint32_t color;
  74.     uint32_t isVisited;
  75. } Node;
  76.  
  77. typedef struct Coords_s {
  78.     intptr_t i;
  79.     intptr_t j;
  80. } Coords;
  81.  
  82. typedef struct Vec_s {
  83.     Coords *arr;
  84.     size_t curSize;
  85.     size_t curCapacity;
  86. } Vec;
  87.  
  88. Vec *vec_create()
  89. {
  90.     Vec *vec = (Vec*)malloc(sizeof(Vec));
  91.     if (!vec) {
  92.         return NULL;
  93.     }
  94.     vec->arr = (Coords*)malloc(VEC_INIT_CAPACITY * sizeof(Coords));
  95.     if (!vec->arr) {
  96.         free(vec);
  97.         return NULL;
  98.     }
  99.     vec->curCapacity = VEC_INIT_CAPACITY;
  100.     vec->curSize = 0;
  101.     return vec;
  102. }
  103.  
  104. int vec_push(Vec *vec, intptr_t i, intptr_t j)
  105. {
  106.     if (vec->curSize >= vec->curCapacity) {
  107.         size_t newCapacity = vec->curCapacity * 2;
  108.         Coords *oldArr = vec->arr;
  109.         vec->arr = (Coords*)realloc(vec->arr, newCapacity * sizeof(Coords));
  110.         if (!vec->arr) {
  111.             vec->arr = oldArr;
  112.             return 0;
  113.         }
  114.         vec->curCapacity = newCapacity;
  115.     }
  116.  
  117.     vec->arr[vec->curSize].i = i;
  118.     vec->arr[vec->curSize].j = j;
  119.     vec->curSize++;
  120.     return 1;
  121. }
  122.  
  123. Coords *vec_pop(Vec *vec)
  124. {
  125.     if (vec->curSize > 0) {
  126.         return &vec->arr[vec->curSize-- - 1];
  127.     } else {
  128.         return NULL;
  129.     }
  130. }
  131.  
  132. void vec_clear(Vec *vec)
  133. {
  134.     vec->curSize = 0;
  135. }
  136.  
  137. void vec_delete(Vec *vec)
  138. {
  139.     if (vec) {
  140.         if (vec->arr) {
  141.             free(vec->arr);
  142.         }
  143.         free(vec);
  144.     }
  145. }
  146.  
  147. inline int isValidCoords(intptr_t i, intptr_t j)
  148. {
  149.     return (i >= 0) && (i < ROWS) && (j >= 0) && (j < COLS);
  150. }
  151.  
  152. size_t visitNode(Node *matrix, intptr_t i, intptr_t j)
  153. {
  154.     static const int MOVES[][2] = {
  155.         { -1, 0 },
  156.         { +1, 0 },
  157.         { 0, -1 },
  158.         { 0, +1 },
  159.     };
  160.  
  161.     size_t blockSize = 0;
  162.     uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
  163.     static Vec *vec = NULL;
  164.     if (!vec) {
  165.         vec = vec_create();
  166.         if (!vec) {
  167.             goto OOM;
  168.         }
  169.     }
  170.  
  171.     if (!vec_push(vec, i, j)) {
  172.         goto OOM;
  173.     }
  174.  
  175.     MATRIX_AT(matrix, i, j).isVisited = 1;
  176.     while (vec->curSize > 0) {
  177.         Coords *coords = vec_pop(vec);
  178.         i = coords->i;
  179.         j = coords->j;
  180.  
  181.         blockSize++;
  182.  
  183.         for (size_t moveIdx = 0; moveIdx < sizeof(MOVES) / sizeof(MOVES[0]); moveIdx++) {
  184.             intptr_t movedI = i + MOVES[moveIdx][0], movedJ = j + MOVES[moveIdx][1];
  185.             if (isValidCoords(movedI, movedJ)) {
  186.                 Node *adjNode = &MATRIX_AT(matrix, movedI, movedJ);
  187.                 if (adjNode->color == targetColor && !adjNode->isVisited) {
  188.                     adjNode->isVisited = 1;
  189.                     if (!vec_push(vec, movedI, movedJ)) {
  190.                         goto OOM;
  191.                     }
  192.                 }
  193.             }
  194.         }
  195.     }
  196.  
  197.     vec_clear(vec);
  198.     return blockSize;
  199.  
  200. OOM:
  201.     perror("OOM");
  202.     vec_delete(vec);
  203.     exit(EXIT_FAILURE);
  204. }
  205.  
  206. void print_matrix(Node *matrix)
  207. {
  208.     for (size_t i = 0; i < ROWS; i++) {
  209.         for (size_t j = 0; j < COLS; j++) {
  210.             putchar(MATRIX_AT(matrix, i, j).color + '0');
  211.         }
  212.         putchar('\n');
  213.     }
  214. }
  215.  
  216. size_t main_c()
  217. {
  218.     Node *matrix = (Node*)calloc(ROWS * COLS, sizeof(Node));
  219.     for (size_t i = 0; i < ROWS * COLS; i++) {
  220.         matrix[i].color = LCGRand() % COLORS_NUM;
  221.     }
  222.     //print_matrix(matrix);
  223.  
  224.     clock_t start = clock();
  225.     size_t maxAdjNodes = 0;
  226.     for (intptr_t i = 0; i < ROWS; i++) {
  227.         for (intptr_t j = 0; j < COLS; j++) {
  228.             if (!MATRIX_AT(matrix, i, j).isVisited) {
  229.                 size_t adjNodes = visitNode(matrix, i, j);
  230.                 if (maxAdjNodes < adjNodes) {
  231.                     maxAdjNodes = adjNodes;
  232.                 }
  233.             }
  234.         }
  235.     }
  236.  
  237.     free(matrix);
  238.     //printf("Max block size: %zd\ntime: %ld", maxAdjNodes, (clock() - start) / (CLOCKS_PER_SEC / 1000));
  239.     return maxAdjNodes;
  240. }
  241.  
  242. int main()
  243. {
  244.     for (ROWS = 1; ROWS < 10; ROWS++) {
  245.         for (COLS = 1; COLS < 100; COLS++) {
  246.             for (int i = -5; i < 5; i++) {
  247.                 next = SEED + i;
  248.                 size_t res_c = main_c();
  249.                 next = SEED + i;
  250.                 size_t res_cpp = main_cpp();
  251.                 if (res_c != res_cpp) {
  252.                     std::cout << "ERROR FOR SEED = " << SEED + i
  253.                         << ", ROWS = " << ROWS << ", COLS = " << COLS << "(" << res_c << " != " << res_cpp << ")" << std::endl;
  254.                     return EXIT_FAILURE;
  255.                 }
  256.             }
  257.         }
  258.     }
  259.     std::cout << "OK" << std::endl;
  260.     return EXIT_SUCCESS;
  261. }
  262.  
  263.  
Success #stdin #stdout 0.2s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
OK
https://ideone.com/4JphF7
language:
C++14 (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!