fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <boost/assign.hpp>
  4. #include <boost/array.hpp>
  5. #include <vector>
  6. #include <set>
  7.  
  8. namespace mxdetail
  9. {
  10.     typedef size_t cell_id; // row * COLS + col
  11.  
  12.     template <typename T> struct area
  13.     {
  14.         T value;
  15.         typedef std::vector<cell_id> cells_t;
  16.         cells_t cells;
  17.     };
  18.  
  19.     template <typename T, size_t Rows, size_t Cols>
  20.         std::vector<area<T> > getareas(const boost::array<boost::array<T, Cols>, Rows>& matrix)
  21.     {
  22.         typedef boost::array<boost::array<T, Cols>, Rows> mtx;
  23.         std::vector<area<T> > areas;
  24.  
  25.         struct visitor_t
  26.         {
  27.             const mtx& matrix;
  28.             std::set<cell_id> visited;
  29.  
  30.             visitor_t(const mtx& mtx) : matrix(mtx) { }
  31.  
  32.             area<T> start(const int row, const int col)
  33.             {
  34.                 area<T> result;
  35.                 visit(row, col, result);
  36.                 return result;
  37.             }
  38.  
  39.             void visit(const int row, const int col, area<T>& current)
  40.             {
  41.                 const cell_id id = row*Cols+col;
  42.                 if (visited.end() != visited.find(id))
  43.                     return;
  44.  
  45.                 bool matches = current.cells.empty() || (matrix[row][col] == current.value);
  46.  
  47.                 if (matches)
  48.                 {
  49.                     visited.insert(id);
  50.                     current.value = matrix[row][col];
  51.                     current.cells.push_back(id);
  52.  
  53.                     // process neighbours
  54.                     for (int nrow=std::max(0, row-1); nrow < std::min((int) Rows, row+2); nrow++)
  55.                     for (int ncol=std::max(0, col-1); ncol < std::min((int) Cols, col+2); ncol++)
  56.                         /* if (ncol!=col || nrow!=row) */
  57.                             visit(nrow, ncol, current);
  58.                 }
  59.             }
  60.         } visitor(matrix);
  61.  
  62.         for (int r=0; r < (int) Rows; r++)
  63.             for (int c=0; c < (int) Cols; c++)
  64.             {
  65.                 mxdetail::area<int> area = visitor.start(r,c);
  66.                 if (!area.cells.empty()) // happens when startpoint already visited
  67.                     areas.push_back(area);
  68.             }
  69.  
  70.         return areas;
  71.     }
  72. }
  73.  
  74.  
  75. template <typename T, size_t N>
  76.    boost::array<T, N> make_array(const T (&a)[N])
  77. {
  78.     boost::array<T, N> result;
  79.     std::copy(a, a+N, result.begin());
  80.     return result;
  81. }
  82.  
  83. int main()
  84. {
  85.     typedef boost::array<int, 3> row;
  86.  
  87.     int row0[] = { 1  , 2, 3, };
  88.     int row1[] = { 1  , 3, 3, };
  89.     int row2[] = { 1  , 3, 3, };
  90.     int row3[] = { 100, 2, 1, };
  91.  
  92.     boost::array<row, 4> matrix;
  93.     matrix[0] = make_array(row0);
  94.     matrix[1] = make_array(row1);
  95.     matrix[2] = make_array(row2);
  96.     matrix[3] = make_array(row3);
  97.  
  98.     typedef std::vector<mxdetail::area<int> > areas_t;
  99.     typedef areas_t::value_type::cells_t cells_t; 
  100.  
  101.     areas_t areas = mxdetail::getareas(matrix);
  102.     for (areas_t::const_iterator it=areas.begin(); it!=areas.end(); ++it)
  103.     {
  104.         std::cout << "area of " << it->value << ": ";
  105.         for (cells_t::const_iterator pit=it->cells.begin(); pit!=it->cells.end(); ++pit)
  106.         {
  107.             int row = *pit / 3, col = *pit % 3;
  108.             std::cout << "(" << row << "," << col << "), ";
  109.         }
  110.         std::cout << std::endl;
  111.     }
  112.     std::cout << "areas detected: " << areas.size() << std::endl;
  113.  
  114. }
  115.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
area of 1: (0,0), (1,0), (2,0), 
area of 2: (0,1), 
area of 3: (0,2), (1,1), (1,2), (2,1), (2,2), 
area of 100: (3,0), 
area of 2: (3,1), 
area of 1: (3,2), 
areas detected: 6
https://ideone.com/ATY4q
language:
C++ (gcc 8.3)
created:
13 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!