This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <queue>
#include "graph/grid.hpp"
int main() {
int h, w, n;
std::cin >> h >> w >> n;
grid::set_bound(h, w);
std::vector<std::string> s(h);
std::vector<grid> p(n + 1);
for (int y = 0; y < h; y++) {
std::cin >> s[y];
for (int x = 0; x < w; x++) {
if (s[y][x] == 'S') p[0] = grid(y, x);
if (std::isdigit(s[y][x])) p[s[y][x] - '0'] = grid(y, x);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
std::vector<int> d(h * w, -1);
std::queue<grid> q;
d[p[i]] = 0, q.push(p[i]);
while (!q.empty()) {
grid u = q.front();
q.pop();
for (grid v : u.neighbors()) {
if (s[v.y][v.x] == 'X') continue;
if (d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
ans += d[p[i + 1]];
}
std::cout << ans << '\n';
}
#line 1 "test/aoj/0558.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <queue>
#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}};
};
#line 6 "test/aoj/0558.test.cpp"
int main() {
int h, w, n;
std::cin >> h >> w >> n;
grid::set_bound(h, w);
std::vector<std::string> s(h);
std::vector<grid> p(n + 1);
for (int y = 0; y < h; y++) {
std::cin >> s[y];
for (int x = 0; x < w; x++) {
if (s[y][x] == 'S') p[0] = grid(y, x);
if (std::isdigit(s[y][x])) p[s[y][x] - '0'] = grid(y, x);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
std::vector<int> d(h * w, -1);
std::queue<grid> q;
d[p[i]] = 0, q.push(p[i]);
while (!q.empty()) {
grid u = q.front();
q.pop();
for (grid v : u.neighbors()) {
if (s[v.y][v.x] == 'X') continue;
if (d[v] != -1) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
ans += d[p[i + 1]];
}
std::cout << ans << '\n';
}