グリッド
(graph/grid.hpp)

• View this file on GitHub
• Last update: 2023-01-18 16:13:28+09:00
• Include: #include "graph/grid.hpp"

概要

• グリッドを扱うのに便利な構造体。

使い方

• grid::set_bound(height, width): [0, height) $\times$ [0, width) で初期化する。
• grid::set_bound(min_y, min_x, max_y, max_x): [min_y, max_y] $\times$ [min_x, max_x] で初期化する。
• grid::grids(): すべてのグリッドを辞書順で列挙する。
• grid::from(i): 辞書順で i 番目のグリッドを求める。
• operator int(): グリッドが辞書順で何番目かを求める。
• neighbors(): グリッドの4近傍であって、範囲内のものを列挙する。
• neighbors_8(): グリッドの8近傍であって、範囲内のものを列挙する。

Verified with

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

Code

#pragma once
#include <vector>
struct grid {
public:
    int y, x;
    grid() {
    }
    grid(int y, int x) : y(y), x(x) {
    }
    static void set_bound(int height, int width) {
        _min_y = 0;
        _min_x = 0;
        _max_y = height - 1;
        _max_x = width - 1;
    }
    static void set_bound(int min_y, int min_x, int max_y, int max_x) {
        _min_y = min_y;
        _min_x = min_x;
        _max_y = max_y;
        _max_x = max_x;
    }
    static std::vector<grid> grids() {
        std::vector<grid> ret;
        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;
    }
    static grid from(int i) {
        return grid(i / (_max_x - _min_x + 1) + _min_y,
                    i % (_max_x - _min_x + 1) + _min_x);
    }
    bool is_valid() {
        return _min_y <= y && y <= _max_y && _min_x <= x && x <= _max_x;
    }
    std::vector<grid> neighbors() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    std::vector<grid> neighbors_8() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta_8) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    operator int() const {
        return (y - _min_y) * (_max_x - _min_x + 1) + (x - _min_x);
    }

private:
    static inline int _min_y, _min_x, _max_y, _max_x;
    static inline const std::vector<std::pair<int, int>> delta = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static inline const std::vector<std::pair<int, int>> delta_8 = {
        {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
};

#line 2 "graph/grid.hpp"
#include <vector>
struct grid {
public:
    int y, x;
    grid() {
    }
    grid(int y, int x) : y(y), x(x) {
    }
    static void set_bound(int height, int width) {
        _min_y = 0;
        _min_x = 0;
        _max_y = height - 1;
        _max_x = width - 1;
    }
    static void set_bound(int min_y, int min_x, int max_y, int max_x) {
        _min_y = min_y;
        _min_x = min_x;
        _max_y = max_y;
        _max_x = max_x;
    }
    static std::vector<grid> grids() {
        std::vector<grid> ret;
        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;
    }
    static grid from(int i) {
        return grid(i / (_max_x - _min_x + 1) + _min_y,
                    i % (_max_x - _min_x + 1) + _min_x);
    }
    bool is_valid() {
        return _min_y <= y && y <= _max_y && _min_x <= x && x <= _max_x;
    }
    std::vector<grid> neighbors() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    std::vector<grid> neighbors_8() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta_8) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    operator int() const {
        return (y - _min_y) * (_max_x - _min_x + 1) + (x - _min_x);
    }

private:
    static inline int _min_y, _min_x, _max_y, _max_x;
    static inline const std::vector<std::pair<int, int>> delta = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static inline const std::vector<std::pair<int, int>> delta_8 = {
        {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
};

Back to top page