#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <bits/stdc++.h>
#include "../../Graph/Shortest-Path/bfs.hpp"
#include "../../Util/make-four-neighbor-enumerator.hpp"
#include "../../Util/rep-macro.hpp"
#include "../../Util/makeVec.hpp"
#include "../../Util/fillContainer.hpp"
#include "../../Util/IO/var-declaration-with-input.hpp"
int main() {
using P = std::array<int, 2>;
var(int, H, W, N);
std::vector<std::string> mat(H);
std::vector<P> cheeses(N + 1);
rep(i, 0, H) {
std::cin >> mat[i];
rep(j, 0, W) {
if (std::isdigit(mat[i][j])) {
cheeses[mat[i][j] - '0'] = P{i, j};
} else if (mat[i][j] == 'S') {
cheeses[0] = P{i, j};
}
}
}
const auto enumerate4neighbor = makeFourNeighborEnumerator(H, W, [&](auto, auto to, auto f) {
const auto [y, x] = to;
if (mat[y][x] != 'X') f(to);
});
auto dist = makeVec<int>(H, W, -1);
int ans = 0;
rep(level, 0, N) {
const P s = cheeses[level];
const P g = cheeses[level + 1];
fillContainer<int>(dist, -1);
bfs(dist, s, enumerate4neighbor);
ans += arumakan::at(dist, g);
}
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/AOJ/0558-Cheese.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <bits/stdc++.h>
#line 7 "Graph/Shortest-Path/bfs.hpp"
#line 4 "Util/at.hpp"
#include <type_traits>
/**
* @brief at() ()
*/
namespace arumakan {
//! at(a, i) returns a[i]
template <class Array, class Integer, std::enable_if_t<std::is_integral<Integer>::value, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Integer i) -> decltype(a[0])& {
return a[i];
}
//! at(a, Tuple{i}) returns a[i]
template <class Array, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 1, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Tuple index) -> decltype(a[0])& {
return a[std::get<0>(index)];
}
//! at(mat, Tuple{y, x}) returns mat[y][x]
template <class Matrix, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 2, std::nullptr_t> = nullptr>
inline auto at(Matrix&& mat, Tuple index) -> decltype(mat[0][0])& {
return mat[std::get<0>(index)][std::get<1>(index)];
}
//! at(cube, Tuple{z, y, x}) returns cube[z][y][x]
template <class Cube, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 3, std::nullptr_t> = nullptr>
inline auto at(Cube&& cube, Tuple index) -> decltype(cube[0][0][0])& {
return cube[std::get<0>(index)][std::get<1>(index)][std::get<2>(index)];
}
} // namespace arumakan
#line 3 "Util/int-infinity.hpp"
/**
* @brief int-infinity (整数のデカイ値)
* 2倍してもオーバーフローしない & memset()にも使える (需要ある？)
*/
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
#line 10 "Graph/Shortest-Path/bfs.hpp"
/**
* @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応)
*
* @param dist:
* start からの距離を格納する配列。
* 要素数は頂点数以上でなければならない。-1やINFなど、距離として正当でない値でfillされている必要がある。
* 多次元配列でもOK。
*
* @param start:
* 頂点を表すdistの添字。
* distが一次元配列なら整数型,
* distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>,
* distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。
* start = {i, j, k} のとき dist[i][j][k] でアクセスする。
*
* @param enumerateNextVertex:
* fn(from: Vertex, fn(to: Vertex) => void) => void
* 第一引数にVertex, 第二引数に関数をとる関数。
* この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。
*/
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
using arumakan::at;
assert(!dist.empty());
assert(at(dist, start) == -1 || at(dist, start) >= INF);
std::queue<Vertex> que({start});
const auto yetReachedMarker = at(dist, start);
at(dist, start) = 0;
while (!que.empty()) {
const Vertex v = std::move(que.front());
que.pop();
const auto curDist = at(dist, v);
enumerateNextVertex(v, [&](Vertex nxt) {
if (at(dist, nxt) == yetReachedMarker) {
at(dist, nxt) = curDist + 1;
que.push(nxt);
}
});
}
return dist;
}
#line 4 "Util/make-four-neighbor-enumerator.hpp"
/**
* @brief makeFourNeighborEnumerator() (グリッドの四近傍(上下左右)の列挙)
*
* handlerFunc: fn({sy, sx}, {ny, nx}, f)
*/
template <class HandlerFunc>
auto makeFourNeighborEnumerator(int H, int W, HandlerFunc handlerFunc) {
return [H, W, handlerFunc](auto v, auto func) {
using P = decltype(v);
static constexpr int dy[]{0, 1, 0, -1};
const auto y = std::get<0>(v);
const auto x = std::get<1>(v);
for (size_t q = 0; q < 4; ++q) {
const auto ny = y + dy[q];
const auto nx = x + dy[q ^ 1];
if (0 <= ny && ny < H && 0 <= nx && nx < W) handlerFunc(P{y, x}, P{ny, nx}, func);
}
};
}
#line 2 "Util/rep-macro.hpp"
/**
* @brief rep()マクロ
*/
#define rep(i, begin, end) for (int64_t i = (begin), i##_end = (end); i < i##_end; ++i)
#define repc(i, begin, last) for (int64_t i = (begin), i##_last = (last); i <= i##_last; ++i)
#define repr(i, begin, last) for (int64_t i = (begin), i##_last = (last); i >= i##_last; --i)
#line 3 "Util/makeVec.hpp"
/**
* @brief makeVec() (多次元std::vectorの生成)
*/
template <class T>
inline std::vector<T> makeVec(size_t sz, const T& initValue) {
return std::vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto makeVec(size_t sz, Args... args) {
return std::vector<decltype(makeVec<T>(args...))>(sz, makeVec<T>(args...));
}
#line 5 "Util/fillContainer.hpp"
/**
* @brief fillContainer() (コンテナのfill)
*/
template <class T, class Container, class... ConstructorArgs, std::enable_if_t<std::is_same<Container, T>::value, std::nullptr_t> = nullptr>
inline void fillContainer(Container& container, ConstructorArgs&&... constructorArgs) {
container = T(std::forward<ConstructorArgs>(constructorArgs)...);
}
template <class T, class Container, class... ConstructorArgs, std::enable_if_t<!std::is_same<Container, T>::value, std::nullptr_t> = nullptr>
inline void fillContainer(Container& container, ConstructorArgs&&... constructorArgs) {
for (auto& e: container) fillContainer<T>(e, std::forward<ConstructorArgs>(constructorArgs)...);
}
#line 3 "Util/IO/var-declaration-with-input.hpp"
/**
* @brief 複数変数宣言をして同時に入力もするやつ
*/
template <class T>
std::istream& operator,(std::istream& is, T& rhs) {
return is >> rhs;
}
#define var(type, ...) \
type __VA_ARGS__; \
std::cin >> __VA_ARGS__
#line 10 "test/AOJ/0558-Cheese.test.cpp"
int main() {
using P = std::array<int, 2>;
var(int, H, W, N);
std::vector<std::string> mat(H);
std::vector<P> cheeses(N + 1);
rep(i, 0, H) {
std::cin >> mat[i];
rep(j, 0, W) {
if (std::isdigit(mat[i][j])) {
cheeses[mat[i][j] - '0'] = P{i, j};
} else if (mat[i][j] == 'S') {
cheeses[0] = P{i, j};
}
}
}
const auto enumerate4neighbor = makeFourNeighborEnumerator(H, W, [&](auto, auto to, auto f) {
const auto [y, x] = to;
if (mat[y][x] != 'X') f(to);
});
auto dist = makeVec<int>(H, W, -1);
int ans = 0;
rep(level, 0, N) {
const P s = cheeses[level];
const P g = cheeses[level + 1];
fillContainer<int>(dist, -1);
bfs(dist, s, enumerate4neighbor);
ans += arumakan::at(dist, g);
}
std::cout << ans << std::endl;
return 0;
}
test/AOJ/0558-Cheese.test.cpp