Grid
(graph/grid.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/grid.hpp"

Overview

Grid is a helper for treating an H x W grid as a graph with H * W vertices. It centralizes the standard conversion:

id(i, j) = i * W + j
pos(v) = {v / W, v % W}

Use it when a problem gives cells as (i, j) but graph algorithms expect a single vertex id.

Blocked cells are not compressed away by the graph builders. The generated graph always has H * W vertices, so grid.id(i, j) remains valid and stable for every cell. Blocked cells simply become isolated if you use a passable predicate.

Graph Orientation

The graph builders create undirected grid graphs. Use graph4 for four-way movement and graph8 for eight-way movement.

How to Use It

Create Grid grid(H, W), then use id(i, j) before calling graph algorithms and pos(v) when you need to convert an answer back to grid coordinates.

For local movement without constructing a graph, use adj4(i, j) or adj8(i, j). These return only cells inside the grid.

For graph construction:

graph4() builds an undirected 4-neighbor graph with every cell passable.
graph8() builds an undirected 8-neighbor graph with every cell passable.
graph4(passable) and graph8(passable) skip edges incident to blocked cells.

The passable predicate must be callable as bool passable(int i, int j).

Fields and Methods

Member	Type / Signature	Meaning	Complexity
`di4`	`static constexpr std::array<int, 4>`	Row offsets for 4-neighbor movement.	$O(1)$
`dj4`	`static constexpr std::array<int, 4>`	Column offsets for 4-neighbor movement.	$O(1)$
`di8`	`static constexpr std::array<int, 8>`	Row offsets for 8-neighbor movement.	$O(1)$
`dj8`	`static constexpr std::array<int, 8>`	Column offsets for 8-neighbor movement.	$O(1)$
Constructor	`Grid()`	Creates an empty grid.	$O(1)$
Constructor	`Grid(int h, int w)`	Creates an `h x w` grid.	$O(1)$
`height`	`int height() const`	Returns `h`.	$O(1)$
`width`	`int width() const`	Returns `w`.	$O(1)$
`size`	`int size() const`	Returns `h * w`.	$O(1)$
`empty`	`bool empty() const`	Returns whether the grid has no cells.	$O(1)$
`inside`	`bool inside(int i, int j) const`	Returns whether `(i, j)` is inside the grid.	$O(1)$
`id`	`int id(int i, int j) const`	Converts cell `(i, j)` to vertex id.	$O(1)$
`pos`	`std::pair<int, int> pos(int v) const`	Converts vertex id `v` to `(i, j)`.	$O(1)$
`adj4`	`std::vector<std::pair<int, int>> adj4(int i, int j) const`	Returns inside 4-neighbor cells of `(i, j)`.	$O(1)$
`adj8`	`std::vector<std::pair<int, int>> adj8(int i, int j) const`	Returns inside 8-neighbor cells of `(i, j)`.	$O(1)$
`adj4_ids`	`std::vector<int> adj4_ids(int v) const`	Returns inside 4-neighbor vertex ids of `v`.	$O(1)$
`adj8_ids`	`std::vector<int> adj8_ids(int v) const`	Returns inside 8-neighbor vertex ids of `v`.	$O(1)$
`graph4`	`Graph<int> graph4() const`	Builds an undirected 4-neighbor graph with all cells passable.	$O(H \cdot W)$
`graph8`	`Graph<int> graph8() const`	Builds an undirected 8-neighbor graph with all cells passable.	$O(H \cdot W)$
`graph4`	`template <class Passable> Graph<int> graph4(Passable passable) const`	Builds an undirected 4-neighbor graph using a passable predicate.	$O(H \cdot W)$
`graph8`	`template <class Passable> Graph<int> graph8(Passable passable) const`	Builds an undirected 8-neighbor graph using a passable predicate.	$O(H \cdot W)$

Example

#include "graph/bfs.hpp"
#include "graph/grid.hpp"
#include <iostream>
#include <string>
#include <vector>

int main() {
    int H = 3, W = 4;
    std::vector<std::string> S = {
        "....",
        ".##.",
        "....",
    };

    m1une::graph::Grid grid(H, W);
    auto passable = [&](int i, int j) {
        return S[i][j] != '#';
    };

    auto g = grid.graph4(passable);
    int s = grid.id(0, 0);
    int t = grid.id(2, 3);

    auto res = m1une::graph::bfs(g, s);
    std::cout << res.dist[t] << "\n";

    for (int v : res.path(t)) {
        auto [i, j] = grid.pos(v);
        std::cout << "(" << i << "," << j << ") ";
    }
    std::cout << "\n";
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_GRID_HPP
#define M1UNE_GRAPH_GRID_HPP 1

#include <array>
#include <cassert>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct Grid {
   private:
    int _h;
    int _w;

   public:
    static constexpr std::array<int, 4> di4 = {-1, 0, 1, 0};
    static constexpr std::array<int, 4> dj4 = {0, 1, 0, -1};
    static constexpr std::array<int, 8> di8 = {-1, -1, -1, 0, 0, 1, 1, 1};
    static constexpr std::array<int, 8> dj8 = {-1, 0, 1, -1, 1, -1, 0, 1};

    Grid() : _h(0), _w(0) {}
    Grid(int h, int w) : _h(h), _w(w) {
        assert(0 <= h);
        assert(0 <= w);
    }

    int height() const {
        return _h;
    }

    int width() const {
        return _w;
    }

    int size() const {
        return _h * _w;
    }

    bool empty() const {
        return size() == 0;
    }

    bool inside(int i, int j) const {
        return 0 <= i && i < _h && 0 <= j && j < _w;
    }

    int id(int i, int j) const {
        assert(inside(i, j));
        return i * _w + j;
    }

    std::pair<int, int> pos(int v) const {
        assert(0 <= v && v < size());
        return {v / _w, v % _w};
    }

    std::vector<std::pair<int, int>> adj4(int i, int j) const {
        assert(inside(i, j));
        std::vector<std::pair<int, int>> result;
        result.reserve(4);
        for (int k = 0; k < 4; k++) {
            int ni = i + di4[k], nj = j + dj4[k];
            if (inside(ni, nj)) result.emplace_back(ni, nj);
        }
        return result;
    }

    std::vector<std::pair<int, int>> adj8(int i, int j) const {
        assert(inside(i, j));
        std::vector<std::pair<int, int>> result;
        result.reserve(8);
        for (int k = 0; k < 8; k++) {
            int ni = i + di8[k], nj = j + dj8[k];
            if (inside(ni, nj)) result.emplace_back(ni, nj);
        }
        return result;
    }

    std::vector<int> adj4_ids(int v) const {
        auto [i, j] = pos(v);
        std::vector<int> result;
        result.reserve(4);
        for (auto [ni, nj] : adj4(i, j)) result.push_back(id(ni, nj));
        return result;
    }

    std::vector<int> adj8_ids(int v) const {
        auto [i, j] = pos(v);
        std::vector<int> result;
        result.reserve(8);
        for (auto [ni, nj] : adj8(i, j)) result.push_back(id(ni, nj));
        return result;
    }

    Graph<int> graph4() const {
        return graph4([](int, int) { return true; });
    }

    Graph<int> graph8() const {
        return graph8([](int, int) { return true; });
    }

    template <class Passable>
    Graph<int> graph4(Passable passable) const {
        Graph<int> g(size());
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                if (!passable(i, j)) continue;
                int v = id(i, j);
                for (auto [ni, nj] : adj4(i, j)) {
                    if (!passable(ni, nj)) continue;
                    int to = id(ni, nj);
                    if (v < to) g.add_edge(v, to);
                }
            }
        }
        return g;
    }

    template <class Passable>
    Graph<int> graph8(Passable passable) const {
        Graph<int> g(size());
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                if (!passable(i, j)) continue;
                int v = id(i, j);
                for (auto [ni, nj] : adj8(i, j)) {
                    if (!passable(ni, nj)) continue;
                    int to = id(ni, nj);
                    if (v < to) g.add_edge(v, to);
                }
            }
        }
        return g;
    }
};

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_GRID_HPP

#line 1 "graph/grid.hpp"



#include <array>
#include <cassert>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 10 "graph/grid.hpp"

namespace m1une {
namespace graph {

struct Grid {
   private:
    int _h;
    int _w;

   public:
    static constexpr std::array<int, 4> di4 = {-1, 0, 1, 0};
    static constexpr std::array<int, 4> dj4 = {0, 1, 0, -1};
    static constexpr std::array<int, 8> di8 = {-1, -1, -1, 0, 0, 1, 1, 1};
    static constexpr std::array<int, 8> dj8 = {-1, 0, 1, -1, 1, -1, 0, 1};

    Grid() : _h(0), _w(0) {}
    Grid(int h, int w) : _h(h), _w(w) {
        assert(0 <= h);
        assert(0 <= w);
    }

    int height() const {
        return _h;
    }

    int width() const {
        return _w;
    }

    int size() const {
        return _h * _w;
    }

    bool empty() const {
        return size() == 0;
    }

    bool inside(int i, int j) const {
        return 0 <= i && i < _h && 0 <= j && j < _w;
    }

    int id(int i, int j) const {
        assert(inside(i, j));
        return i * _w + j;
    }

    std::pair<int, int> pos(int v) const {
        assert(0 <= v && v < size());
        return {v / _w, v % _w};
    }

    std::vector<std::pair<int, int>> adj4(int i, int j) const {
        assert(inside(i, j));
        std::vector<std::pair<int, int>> result;
        result.reserve(4);
        for (int k = 0; k < 4; k++) {
            int ni = i + di4[k], nj = j + dj4[k];
            if (inside(ni, nj)) result.emplace_back(ni, nj);
        }
        return result;
    }

    std::vector<std::pair<int, int>> adj8(int i, int j) const {
        assert(inside(i, j));
        std::vector<std::pair<int, int>> result;
        result.reserve(8);
        for (int k = 0; k < 8; k++) {
            int ni = i + di8[k], nj = j + dj8[k];
            if (inside(ni, nj)) result.emplace_back(ni, nj);
        }
        return result;
    }

    std::vector<int> adj4_ids(int v) const {
        auto [i, j] = pos(v);
        std::vector<int> result;
        result.reserve(4);
        for (auto [ni, nj] : adj4(i, j)) result.push_back(id(ni, nj));
        return result;
    }

    std::vector<int> adj8_ids(int v) const {
        auto [i, j] = pos(v);
        std::vector<int> result;
        result.reserve(8);
        for (auto [ni, nj] : adj8(i, j)) result.push_back(id(ni, nj));
        return result;
    }

    Graph<int> graph4() const {
        return graph4([](int, int) { return true; });
    }

    Graph<int> graph8() const {
        return graph8([](int, int) { return true; });
    }

    template <class Passable>
    Graph<int> graph4(Passable passable) const {
        Graph<int> g(size());
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                if (!passable(i, j)) continue;
                int v = id(i, j);
                for (auto [ni, nj] : adj4(i, j)) {
                    if (!passable(ni, nj)) continue;
                    int to = id(ni, nj);
                    if (v < to) g.add_edge(v, to);
                }
            }
        }
        return g;
    }

    template <class Passable>
    Graph<int> graph8(Passable passable) const {
        Graph<int> g(size());
        for (int i = 0; i < _h; i++) {
            for (int j = 0; j < _w; j++) {
                if (!passable(i, j)) continue;
                int v = id(i, j);
                for (auto [ni, nj] : adj8(i, j)) {
                    if (!passable(ni, nj)) continue;
                    int to = id(ni, nj);
                    if (v < to) g.add_edge(v, to);
                }
            }
        }
        return g;
    }
};

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Grid
(graph/grid.hpp)

Overview

Graph Orientation

How to Use It

Fields and Methods

Example

Depends on

Required by

Verified with

Code

Grid (graph/grid.hpp)

Overview

Graph Orientation

How to Use It

Fields and Methods

Example

Depends on

Required by

Verified with

Code

Grid
(graph/grid.hpp)