fork(5) download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <vector>
  4.  
  5. static const uint64_t SEED = 0xDEADBEEFull;
  6. static const size_t ROWS = 100;
  7. static const size_t COLS = 100;
  8. static const uint32_t COLORS_NUM = 3;
  9.  
  10. uint32_t LCGRand()
  11. {
  12.     static uint64_t seed = SEED;
  13.     seed = seed * 6364136223846793005 + 1442695040888963407;
  14.     return seed >> 32;
  15. }
  16.  
  17. struct Block {
  18. 	uint32_t color;
  19. 	size_t size;
  20. };
  21.  
  22. using BlockPtr = std::shared_ptr<Block>;
  23.  
  24. struct Proxy {
  25. 	BlockPtr block;
  26. };
  27.  
  28. using ProxyPtr = std::shared_ptr<Proxy>;
  29.  
  30. int main()
  31. {
  32. 	std::vector<ProxyPtr> up_row(COLS);
  33. 	size_t max_size = 0;
  34.  
  35.     for (size_t row = 0; row < ROWS; row++) {
  36.     	ProxyPtr left;
  37.  
  38.     	for (size_t col = 0; col < COLS; col++) {
  39.     		uint32_t color = LCGRand() % COLORS_NUM;
  40.  
  41.     		ProxyPtr &up = up_row[col];
  42.  
  43.     		ProxyPtr cur;
  44.     		if (left && (left->block->color == color)) {
  45.     			cur = left;
  46.  
  47.     			if (up && (up->block->color == color) && (up->block != left->block)) {
  48.     				left->block->size += up->block->size;
  49.     				up->block = left->block;
  50.     			}
  51.     		} else if (up && (up->block->color == color)) {
  52.     			cur = up;
  53.     		} else {
  54.     			BlockPtr block = std::make_shared<Block>(Block{color, 0});
  55.     			cur = std::make_shared<Proxy>(Proxy{block});
  56.     		}
  57.  
  58.     		++cur->block->size;
  59.     		if (cur->block->size > max_size)
  60.     			max_size = cur->block->size;
  61.  
  62.     		left = up = cur;
  63.     	}
  64.     }
  65.  
  66.     std::cout << "Max block size: " << max_size << std::endl;
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 4136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max block size: 55
https://ideone.com/UEJlLe
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!