Enumerate points satisfying conditions
(Mylib/Grid/grid_find.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Depends on

• Grid template (Mylib/Grid/grid.cpp)

Verified with

• test/aoj/0558/main.graph.test.cpp
• test/aoj/0558/main.test.cpp

Code

#pragma once
#include <vector>
#include "Mylib/Grid/grid.cpp"

namespace haar_lib {
  template <typename C, typename T = typename C::value_type>
  std::vector<cell> grid_find(const std::vector<C> &A, T value) {
    const int H = A.size(), W = A[0].size();

    std::vector<cell> ret;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (A[i][j] == value) {
          ret.emplace_back(i, j);
        }
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Grid/grid_find.cpp"
#include <vector>
#line 2 "Mylib/Grid/grid.cpp"
#include <array>
#include <iostream>
#include <utility>

namespace haar_lib {
  struct cell {
    int x, y;
    cell() : x(0), y(0) {}
    cell(int x, int y) : x(x), y(y) {}
    cell &operator+=(const cell &a) {
      this->x += a.x;
      this->y += a.y;
      return *this;
    }
    cell &operator-=(const cell &a) {
      this->x -= a.x;
      this->y -= a.y;
      return *this;
    }
  };

  cell operator+(const cell &a, const cell &b) { return cell(a.x + b.x, a.y + b.y); }
  cell operator-(const cell &a, const cell &b) { return cell(a.x - b.x, a.y - b.y); }
  bool operator==(const cell &a, const cell &b) { return a.x == b.x and a.y == b.y; }
  bool operator!=(const cell &a, const cell &b) { return !(a == b); }

  bool operator<(const cell &a, const cell &b) {
    return std::make_pair(a.x, a.y) < std::make_pair(b.x, b.y);
  }

  std::ostream &operator<<(std::ostream &os, const cell &a) {
    os << "(" << a.x << "," << a.y << ")";
    return os;
  }

  const auto LEFT  = cell(0, -1);
  const auto RIGHT = cell(0, 1);
  const auto UP    = cell(-1, 0);
  const auto DOWN  = cell(1, 0);

  const std::array<cell, 4> dir4 = {LEFT, RIGHT, UP, DOWN};
  const std::array<cell, 8> dir8 = {LEFT, RIGHT, UP, DOWN, LEFT + UP, LEFT + DOWN, RIGHT + UP, RIGHT + DOWN};
}  // namespace haar_lib
#line 4 "Mylib/Grid/grid_find.cpp"

namespace haar_lib {
  template <typename C, typename T = typename C::value_type>
  std::vector<cell> grid_find(const std::vector<C> &A, T value) {
    const int H = A.size(), W = A[0].size();

    std::vector<cell> ret;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (A[i][j] == value) {
          ret.emplace_back(i, j);
        }
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page