BFS on a grid
(Mylib/Grid/grid_bfs.cpp)
Operations
Requirements
Notes
Problems
References
Depends on
Verified with
Code
#pragma once
#include <optional>
#include <queue>
#include <vector>
#include "Mylib/Grid/grid.cpp"
namespace haar_lib {
template <typename Directions, typename Checker>
auto grid_bfs(
const int H, const int W,
const std::vector<cell> &starting_points,
const Directions &dir,
const Checker &check_passable) -> std::vector<std::vector<std::optional<int>>> {
std::vector<std::vector<std::optional<int>>> dist(H, std::vector<std::optional<int>>(W));
std::vector<std::vector<bool>> visited(H, std::vector<bool>(W));
std::queue<cell> q;
for (auto &p : starting_points) {
dist[p.x][p.y] = 0;
q.push(p);
}
while (not q.empty()) {
auto cur = q.front();
q.pop();
if (visited[cur.x][cur.y]) continue;
visited[cur.x][cur.y] = true;
for (auto &d : dir) {
auto nxt = cur + d;
if (nxt.x < 0 or nxt.x >= H or nxt.y < 0 or nxt.y >= W or not check_passable(cur, nxt)) continue;
if (not dist[nxt.x][nxt.y]) {
dist[nxt.x][nxt.y] = *dist[cur.x][cur.y] + 1;
q.push(nxt);
} else {
if (*dist[nxt.x][nxt.y] > *dist[cur.x][cur.y] + 1) {
dist[nxt.x][nxt.y] = *dist[cur.x][cur.y] + 1;
q.push(nxt);
}
}
}
}
return dist;
}
} // namespace haar_lib
#line 2 "Mylib/Grid/grid_bfs.cpp"
#include <optional>
#include <queue>
#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 6 "Mylib/Grid/grid_bfs.cpp"
namespace haar_lib {
template <typename Directions, typename Checker>
auto grid_bfs(
const int H, const int W,
const std::vector<cell> &starting_points,
const Directions &dir,
const Checker &check_passable) -> std::vector<std::vector<std::optional<int>>> {
std::vector<std::vector<std::optional<int>>> dist(H, std::vector<std::optional<int>>(W));
std::vector<std::vector<bool>> visited(H, std::vector<bool>(W));
std::queue<cell> q;
for (auto &p : starting_points) {
dist[p.x][p.y] = 0;
q.push(p);
}
while (not q.empty()) {
auto cur = q.front();
q.pop();
if (visited[cur.x][cur.y]) continue;
visited[cur.x][cur.y] = true;
for (auto &d : dir) {
auto nxt = cur + d;
if (nxt.x < 0 or nxt.x >= H or nxt.y < 0 or nxt.y >= W or not check_passable(cur, nxt)) continue;
if (not dist[nxt.x][nxt.y]) {
dist[nxt.x][nxt.y] = *dist[cur.x][cur.y] + 1;
q.push(nxt);
} else {
if (*dist[nxt.x][nxt.y] > *dist[cur.x][cur.y] + 1) {
dist[nxt.x][nxt.y] = *dist[cur.x][cur.y] + 1;
q.push(nxt);
}
}
}
}
return dist;
}
} // namespace haar_lib
Back to top page