#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <vector>
#include "Mylib/Grid/grid.cpp"
#include "Mylib/Grid/grid_bfs.cpp"
#include "Mylib/Grid/grid_find.cpp"
#include "Mylib/IO/input_vector.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int H, W, N;
std::cin >> H >> W >> N;
auto s = hl::input_vector<std::string>(H);
std::vector<hl::cell> ps(N + 1);
ps[0] = hl::grid_find(s, 'S')[0];
for (int i = 1; i <= N; ++i) ps[i] = hl::grid_find(s, (char) ('0' + i))[0];
int ans = 0;
for (int i = 0; i < N; ++i) {
auto dist =
hl::grid_bfs(
H,
W,
{ps[i]},
hl::dir4,
[&](const auto &, const auto &p) {
return s[p.x][p.y] != 'X';
});
ans += *dist[ps[i + 1].x][ps[i + 1].y];
}
std::cout << ans << "\n";
return 0;
}
#line 1 "test/aoj/0558/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <vector>
#line 2 "Mylib/Grid/grid.cpp"
#include <array>
#line 4 "Mylib/Grid/grid.cpp"
#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 2 "Mylib/Grid/grid_bfs.cpp"
#include <optional>
#include <queue>
#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
#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
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 9 "test/aoj/0558/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int H, W, N;
std::cin >> H >> W >> N;
auto s = hl::input_vector<std::string>(H);
std::vector<hl::cell> ps(N + 1);
ps[0] = hl::grid_find(s, 'S')[0];
for (int i = 1; i <= N; ++i) ps[i] = hl::grid_find(s, (char) ('0' + i))[0];
int ans = 0;
for (int i = 0; i < N; ++i) {
auto dist =
hl::grid_bfs(
H,
W,
{ps[i]},
hl::dir4,
[&](const auto &, const auto &p) {
return s[p.x][p.y] != 'X';
});
ans += *dist[ps[i + 1].x][ps[i + 1].y];
}
std::cout << ans << "\n";
return 0;
}
test/aoj/0558/main.test.cpp
Input vector
(Mylib/IO/input_vector.cpp)