グリッドのマス
(graph/cell.hpp)

• View this file on GitHub
• Last update: 2026-10-19 19:51:05+09:00
• Include: #include "graph/cell.hpp"

概要

• グリッドのマスを表す構造体。

使い方

• cell::set_bound(height, width): 範囲を [0, height) $\times$ [0, width) にする。
• cell::set_bound(min_y, min_x, max_y, max_x): 範囲を [min_y, max_y] $\times$ [min_x, max_x] にする。
• cell::height(), cell::width(), cell::size(): 範囲の高さ・幅・マス数。
• cell(y, x): 座標からマスを作る。
• cell(i): 辞書順で i 番目のマスを作る。
• operator int(): マスが辞書順で何番目かを返す。d[v] のように配列の添字にそのまま使える。
• cell::cells(): 全マスを辞書順で列挙する。
• is_valid(): 範囲内か判定する。
• neighbors(), neighbors_8(): 範囲内の 4 近傍・8 近傍。range-for で回す。
• cell::delta, cell::delta_8: 近傍への変位 (dy, dx) の std::pair。
• u + d, u - d: (dy, dx) だけ移動したマス。範囲外のマスも作れるので、必要なら is_valid() で確かめる。
• ==, !=

cell::set_bound(h, w);
std::vector<int> d(cell::size(), -1);
for (cell v : u.neighbors()) { ... }
for (auto [dy, dx] : cell::delta) {
    cell v = cell(u.y + dy * k, u.x + dx * k);
    if (!v.is_valid()) continue;
}

Verified with

• test/aoj/0558.test.cpp
• test/aoj/1160.test.cpp

Code

#pragma once
#include <array>
#include <cassert>
#include <utility>
#include <vector>
struct cell {
public:
    // (dy, dx)
    static constexpr std::array<std::pair<int, int>, 4> delta = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
    static constexpr std::array<std::pair<int, int>, 8> delta_8 = {
        {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}}};

    int y, x;
    cell() : y(0), x(0) {
    }
    cell(int y, int x) : y(y), x(x) {
    }
    // 辞書順で i 番目のマス
    explicit cell(int i) {
        assert(_set);
        assert(0 <= i && i < size());
        y = i / width() + _min_y;
        x = i % width() + _min_x;
    }
    static void set_bound(int height, int width) {
        set_bound(0, 0, height - 1, width - 1);
    }
    static void set_bound(int min_y, int min_x, int max_y, int max_x) {
        assert(min_y <= max_y && min_x <= max_x);
        _min_y = min_y;
        _min_x = min_x;
        _max_y = max_y;
        _max_x = max_x;
        _set = true;
    }
    static int height() {
        assert(_set);
        return _max_y - _min_y + 1;
    }
    static int width() {
        assert(_set);
        return _max_x - _min_x + 1;
    }
    static int size() {
        return height() * width();
    }
    static std::vector<cell> cells() {
        assert(_set);
        std::vector<cell> ret;
        ret.reserve(size());
        for (int y = _min_y; y <= _max_y; y++) {
            for (int x = _min_x; x <= _max_x; x++) {
                ret.emplace_back(y, x);
            }
        }
        return ret;
    }
    bool is_valid() const {
        return _min_y <= y && y <= _max_y && _min_x <= x && x <= _max_x;
    }
    operator int() const {
        return (y - _min_y) * width() + (x - _min_x);
    }
    cell operator+(std::pair<int, int> d) const {
        return cell(y + d.first, x + d.second);
    }
    cell operator-(std::pair<int, int> d) const {
        return cell(y - d.first, x - d.second);
    }
    bool operator==(const cell& o) const {
        return y == o.y && x == o.x;
    }
    bool operator!=(const cell& o) const {
        return !(*this == o);
    }

    template <int K>
    struct neighbor_view {
        std::array<cell, K> a;
        int n;
        const cell* begin() const {
            return a.data();
        }
        const cell* end() const {
            return a.data() + n;
        }
        int size() const {
            return n;
        }
    };
    neighbor_view<4> neighbors() const {
        return collect<4>(delta);
    }
    neighbor_view<8> neighbors_8() const {
        return collect<8>(delta_8);
    }

private:
    static inline bool _set = false;
    static inline int _min_y, _min_x, _max_y, _max_x;
    template <int K>
    neighbor_view<K> collect(const std::array<std::pair<int, int>, K>& ds) const {
        neighbor_view<K> ret;
        ret.n = 0;
        for (auto d : ds) {
            cell v = *this + d;
            if (v.is_valid()) ret.a[ret.n++] = v;
        }
        return ret;
    }
};

#line 2 "graph/cell.hpp"
#include <array>
#include <cassert>
#include <utility>
#include <vector>
struct cell {
public:
    // (dy, dx)
    static constexpr std::array<std::pair<int, int>, 4> delta = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
    static constexpr std::array<std::pair<int, int>, 8> delta_8 = {
        {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}}};

    int y, x;
    cell() : y(0), x(0) {
    }
    cell(int y, int x) : y(y), x(x) {
    }
    // 辞書順で i 番目のマス
    explicit cell(int i) {
        assert(_set);
        assert(0 <= i && i < size());
        y = i / width() + _min_y;
        x = i % width() + _min_x;
    }
    static void set_bound(int height, int width) {
        set_bound(0, 0, height - 1, width - 1);
    }
    static void set_bound(int min_y, int min_x, int max_y, int max_x) {
        assert(min_y <= max_y && min_x <= max_x);
        _min_y = min_y;
        _min_x = min_x;
        _max_y = max_y;
        _max_x = max_x;
        _set = true;
    }
    static int height() {
        assert(_set);
        return _max_y - _min_y + 1;
    }
    static int width() {
        assert(_set);
        return _max_x - _min_x + 1;
    }
    static int size() {
        return height() * width();
    }
    static std::vector<cell> cells() {
        assert(_set);
        std::vector<cell> ret;
        ret.reserve(size());
        for (int y = _min_y; y <= _max_y; y++) {
            for (int x = _min_x; x <= _max_x; x++) {
                ret.emplace_back(y, x);
            }
        }
        return ret;
    }
    bool is_valid() const {
        return _min_y <= y && y <= _max_y && _min_x <= x && x <= _max_x;
    }
    operator int() const {
        return (y - _min_y) * width() + (x - _min_x);
    }
    cell operator+(std::pair<int, int> d) const {
        return cell(y + d.first, x + d.second);
    }
    cell operator-(std::pair<int, int> d) const {
        return cell(y - d.first, x - d.second);
    }
    bool operator==(const cell& o) const {
        return y == o.y && x == o.x;
    }
    bool operator!=(const cell& o) const {
        return !(*this == o);
    }

    template <int K>
    struct neighbor_view {
        std::array<cell, K> a;
        int n;
        const cell* begin() const {
            return a.data();
        }
        const cell* end() const {
            return a.data() + n;
        }
        int size() const {
            return n;
        }
    };
    neighbor_view<4> neighbors() const {
        return collect<4>(delta);
    }
    neighbor_view<8> neighbors_8() const {
        return collect<8>(delta_8);
    }

private:
    static inline bool _set = false;
    static inline int _min_y, _min_x, _max_y, _max_x;
    template <int K>
    neighbor_view<K> collect(const std::array<std::pair<int, int>, K>& ds) const {
        neighbor_view<K> ret;
        ret.n = 0;
        for (auto d : ds) {
            cell v = *this + d;
            if (v.is_valid()) ret.a[ret.n++] = v;
        }
        return ret;
    }
};

Back to top page