#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <utility>
#include <string>

class Cell
{
  bool is_alive_;

  public:
  Cell();
  bool is_alive() const;
  void born();
  void die();
};

std::ostream& operator<<(std::ostream& os, const Cell& c);

class Rule
{
  std::vector<int> alive_cond_;
  std::vector<int> born_cond_;
  public:
  Rule(const std::string& alive_cond, const std::string& born_cond); 
  bool operator()(bool is_alive, int surround_alives) const;
};

class CellTable
{
  std::vector<Cell> cells_;
  int xmax_, ymax_;

  public:
  CellTable(int xmax, int ymax);

  void proceed_next_gen(const CellTable& current_gen, const Rule& rule);

  void swap(CellTable& ct);

  const Cell& get_cell(int x, int y) const;
  Cell& get_cell(int x, int y);

  private:
  friend
    std::ostream& operator<<(std::ostream& os, const CellTable& ct);
};

std::ostream& operator<<(std::ostream& os, const CellTable& ct);

// Cell の実装
Cell::Cell() : is_alive_(false) {}
bool Cell::is_alive() const { return this->is_alive_; }
void Cell::born() { this->is_alive_ = true; }
void Cell::die() { this->is_alive_ = false; }

std::ostream& operator<<(std::ostream& os, const Cell& c)
{
  return os << "[" << (c.is_alive() ? "*" : " ") << "]";
}

// Rule の実装
Rule::Rule(const std::string& alive_cond, const std::string& born_cond)
{
  std::string::const_iterator cit;
  for ( cit = alive_cond.begin(); cit != alive_cond.end(); ++cit )
    if ( '0' <= *cit && *cit <= '8' )
      alive_cond_.push_back(*cit - '0');
  std::sort(alive_cond_.begin(), alive_cond_.end());

  for ( cit = born_cond.begin(); cit != born_cond.end(); ++cit )
    if ( '0' <= *cit && *cit <= '8' )
      born_cond_.push_back(*cit - '0');
  std::sort(born_cond_.begin(), born_cond_.end());
}

bool Rule::operator()(bool is_alive, int surround_alives)
  const
{
  if ( !is_alive &&
       std::binary_search(born_cond_.begin(), born_cond_.end(), surround_alives) )
    // born
    return true;
  else if ( is_alive && 
      std::binary_search(alive_cond_.begin(), alive_cond_.end(), surround_alives ) )
    // still alive
    return true;

  // die
  return false;
}

// CellTable の実装
CellTable::CellTable(int xmax, int ymax)
  : xmax_(xmax), ymax_(ymax)
{
  if ( xmax_ <= 0 || ymax_ <= 0 )
    throw "invalid xmax or ymax!";
  cells_.resize(xmax_*ymax_);
}

void
CellTable::proceed_next_gen(const CellTable& current_gen, const Rule& rule)
{
  for ( int x = 0; x < xmax_; ++x ) {
    for ( int y = 0; y < ymax_; ++y ) {
      int surround_alives = 0;
      for ( int dx = -1; dx < 2; ++dx )
        for (int dy = -1; dy < 2; ++dy )
          if ( !(dx == 0 && dy == 0) && current_gen.get_cell(x+dx,y+dy).is_alive() )
            ++surround_alives;

      const Cell& current_cell = current_gen.get_cell(x,y);
      Cell& next_cell = this->get_cell(x,y);
      if ( rule(current_cell.is_alive(), surround_alives) )
        // born or alive
        next_cell.born();
      else
        // die
        next_cell.die();
    }
  }
}

void
CellTable::swap(CellTable& ct)
{
  cells_.swap(ct.cells_);
  std::swap(xmax_, ct.xmax_);
  std::swap(ymax_, ct.ymax_);
}

const Cell&
CellTable::get_cell(int x, int y) 
  const
{
  while ( x < 0 ) x += xmax_;
  while ( y < 0 ) y += ymax_;
  return cells_[(x%xmax_)+((y%ymax_)*xmax_)];
}

Cell&
CellTable::get_cell(int x, int y) 
{
  while ( x < 0 ) x += xmax_;
  while ( y < 0 ) y += ymax_;
  return cells_[(x%xmax_)+((y%ymax_)*xmax_)];
}

std::ostream&
operator<<(std::ostream& os, const CellTable& ct)
{
  std::vector<Cell>::const_iterator it = ct.cells_.begin();
  while ( it != ct.cells_.end() ) {
    std::copy(
        it, it+ct.xmax_,
        std::ostream_iterator<Cell>(os, "") );
    os << "\n";
    std::advance(it, ct.xmax_);
  }
  return os;
}

const char* const first_pattern =
// ja.doukaku.org 例題パターン
#if 0
"0100001110"
"0000100110"
"0001001010"
"1011001000"
"0100000010"
"1000101101"
"0100001000"
"0000000001"
"1000001001"
"0000110010";
#endif
// グライダーパターン
#if 1
"0000000000"
"0000000000"
"0000000000"
"0000000000"
"0001000000"
"0010000000"
"0011100000"
"0000000000"
"0000000000"
"0000000000";
#endif

int main(int argc, char** argv)
{
  int xmax = 10, ymax = 10;
  int max_gen = 256;

  CellTable current(xmax,ymax), next(xmax,ymax);

  // create first pattern
  const char *p = first_pattern;
  for ( int y = 0; y < ymax; ++y )
    for ( int x = 0; x < xmax; ++x )
      if (*p++ == '1')
        current.get_cell(x,y).born();

  // ja.doukaku.org 出題の 2/3 ルール
  //const Rule rule("2", "3");
  // 標準的な 23/3 ルール
  const Rule rule("23", "3");

  for (int t = 0; t < max_gen; ++t) {
    std::cout << "t = " << t << "\n" << current;

    next.proceed_next_gen(current, rule);
    current.swap(next);
  } 
  return 0;
}