@jinxonik / UniLecs #234

islands.cxx

// C++17

#include <vector>
#include <random>

#define RAND_SEED -1  // ключ для генерации карты (разные значения дадут разные карты при равных значениях нижеследующих параметров), -1 означает использование random_device
#define ISLAND_SIZE 35  // 30 - малые, 35 - средние, 40 - большие, 45 - огромные острова
#define ISLAND_COUNT_COEF 50  // коэффициент кол-ва островов: рекомендую - 100 для ISLAND_SIZE 30; 50 для ISLAND_SIZE 35; 25 для ISLAND_SIZE 40; 10 для ISLAND_SIZE 45

class Islands
{
public:
  using UInt = unsigned long long;

  Islands(UInt width, UInt height, bool generate = true) : m_width(width), m_height(height) {
    m_map.resize(width * height);
    if (generate) { generate_map(); }
  }

  bool get(UInt x, UInt y) {
    return m_map[x + y * m_width];
  }

  void set(UInt x, UInt y, bool value) {
    m_map[x + y * m_width] = value;
  }

  UInt width() {
    return m_width;
  }
  
  UInt height() {
    return m_height;
  }
  
  void generate_map() {
    static std::uniform_int_distribution<UInt> rand_width(0, m_width - 1);
    static std::uniform_int_distribution<UInt> rand_height(0, m_height - 1);
    for (UInt i = 0, lim = m_width * m_height * (ISLAND_COUNT_COEF)/1000; i < lim; ++i) {
      UInt x = rand_width(m_rng);
      UInt y = rand_height(m_rng);
      fill_random(x, y);
    };
  }

  // !!! Очищает карту после работы !!!
  UInt count() {
    UInt num = 0;
    for (UInt y = 0; y < m_height; ++y) {
      for (UInt x = 0; x < m_width; ++x) {
        if (get(x, y)) {
          ++num;
          flood_fill(x, y);
        }
      }
    }
    return num;
  }

private:
  void fill_random(const UInt x, const UInt y) {
    static std::uniform_int_distribution<UInt> rand_fill{0, 99};
    if (get(x, y) || rand_fill(m_rng) >= (ISLAND_SIZE)) { return; }
    set(x, y, true);
    if (x > 0) { fill_random(x - 1, y); }
    if (y > 0) { fill_random(x, y - 1); }
    if (x < m_width - 1) { fill_random(x + 1, y); }
    if (y < m_height - 1) { fill_random(x, y + 1); }
  }

  void flood_fill(const UInt x, const UInt y) {
    UInt left = x, right = x;
    set(x, y, false);
    while(left > 0 && get(left - 1, y)) { --left; set(left, y, false); }
    while(right < m_width - 1 && get(right + 1, y)) { ++right; set(right, y, false); }
    for (; left <= right; ++left) {
      if (y > 0 && get(left, y - 1)) { flood_fill(left, y - 1); }
      if (y < m_height - 1 && get(left, y + 1)) { flood_fill(left, y + 1); }
    }
  }

  UInt m_width;
  UInt m_height;
  std::vector<bool> m_map;

#if RAND_SEED == -1
  std::random_device m_rd;
  std::mt19937_64 m_rng{m_rd()};
#else
  std::mt19937_64 m_rng{RAND_SEED};
#endif
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <string>
#include <chrono>

int main()
{
  const Islands::UInt map_width = 10000;
  const Islands::UInt map_height = 10000;

  std::cout << "Generating map..." << std::endl;
  Islands islands(map_width, map_height, true);

  if constexpr (map_width <= 1000 && map_height <= 1000) {
    std::cout << std::endl;
    std::string s(map_width, {});
    for (Islands::UInt y = 0; y < map_height; ++y) {
      for (Islands::UInt x = 0; x < map_width; ++x) {
        s[x] = (islands.get(x, y) ? 'O' : '.');
      }
      std::cout << s << std::endl;
    }
    std::cout << std::endl;
  }

  std::cout << "Calculating island count..." << std::endl;
  using Clock = typename std::conditional<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>::type;
  auto start_time = Clock::now();
  Islands::UInt num = islands.count();
  auto stop_time = Clock::now();
  double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();

  std::cout << std::endl;
  std::cout << "Number of islands: " << num << std::endl;
  std::cout << "Elapsed time: " << duration << " sec" << std::endl;
}