stripstamp.cc

#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>

template <typename E>
class Matrix {
 public:
  static const int MAX_DIM = 10;

  Matrix() : rows_(0), cols_(0) {}
  Matrix(int rows, int cols, E val) : rows_(rows), cols_(cols) {
    for (int i = 0; i < rows_; i++)
      for (int j = 0; j < cols_; j++)
        matrix_[i][j] = val;
  }

  int rows() const { return rows_; }
  int cols() const { return cols_; }

  E get(int i, int j) const {
    assert(0 <= i && i <= rows_ && 0 <= j && j <= cols_);
    return matrix_[i][j];
  }

  void set(int i, int j, E val) {
    assert(0 <= i && i <= rows_ && 0 <= j && j <= cols_);
    matrix_[i][j] = val;
  }

 protected:
  E matrix_[MAX_DIM][MAX_DIM];
  int rows_, cols_;
};

class Stamp : public Matrix<int> {
 public:
  friend std::istream& operator>>(std::istream& in, Stamp& stamp) {
    stamp.rows_ = stamp.cols_ = 0;
    std::string line;
    while (std::getline(in, line)) {
      std::stringstream row(line);
      int i = 0;
      while (row >> stamp.matrix_[stamp.rows_][i]) {
        assert(0 < stamp.matrix_[stamp.rows_][i]);
        i++;
      }
      assert(stamp.cols_ == 0 || stamp.cols_ == i);
      stamp.cols_ = i;
      stamp.rows_++;
    }
    return in;
  }

  friend std::ostream& operator<<(std::ostream& out, const Stamp& stamp) {
    for (int i = 0; i < stamp.rows_; i++) {
      for (int j = 0; j < stamp.cols_; j++) {
        if (j)
          out << ' ';
        out << stamp.matrix_[i][j];
      }
      out << std::endl;
    }
    return out;
  }
};

class Values {
 public:
  Values(int max_value) : bits_(max_value, false) {}

  int total() const { return bits_.size(); }

  bool get(int value) const {
    assert(0 < value && value <= bits_.size());
    return bits_[value - 1];
  }

  void set(int value) {
    assert(0 < value && value <= bits_.size());
    bits_[value - 1] = true;
  }

 private:
  std::vector<bool> bits_;
};

int Sum(const Stamp& stamp) {
  int sum = 0;
  for (int i = 0; i < stamp.rows(); i++)
    for (int j = 0; j < stamp.cols(); j++)
      sum += stamp.get(i, j);
  return sum;
}

void Search(const Stamp& stamp,
            int y,
            int x,
            int max_depth,
            int current_value,
            Matrix<bool>* visited,
            Values* values) {
  const int deltas[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  if (max_depth == 0)
    return;
  visited->set(y, x, true);
  current_value += stamp.get(y, x);
  values->set(current_value);
  for (int i = 0; i < sizeof(deltas) / sizeof(deltas[0]); i++) {
    int new_y = y + deltas[i][0];
    int new_x = x + deltas[i][1];
    if (new_y < 0 || stamp.rows() <= new_y ||
        new_x < 0 || stamp.cols() <= new_x)
      continue;
    if (!visited->get(new_y, new_x)) {
      Search(stamp, new_y, new_x, max_depth - 1, current_value,
             visited, values);
    }
  }
  visited->set(y, x, false);
}

int main() {
  Stamp stamp;
  std::cin >> stamp;

  Values values(Sum(stamp));
  Matrix<bool> visited(stamp.rows(), stamp.cols(), false);
  int max_depth = stamp.rows() * stamp.cols();
  for (int i = 0; i < stamp.rows(); i++)
    for (int j = 0; j < stamp.cols(); j++)
      Search(stamp, i, j, max_depth, 0, &visited, &values);

  int value = 0;
  while (value + 1 <= values.total() && values.get(value + 1))
    value++;
  std::cout << "max_value=" << value << std::endl;

  return 0;
}