An answer of http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

aoj0558.cpp

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
typedef vector<vector<char>> field_t;
 
struct Point
{
    int x;
    int y;
 
    Point() {}
    Point(int x, int y) :x(x), y(y) {}
 
    Point operator+(const Point &other) {
        Point p(this->x + other.x, this->y + other.y);
        return p;
    }
};
 
Point operator+(const Point &lhs, const Point &rhs)
{
    Point p(lhs.x + rhs.x, lhs.y + rhs.y);
    return p;
}
 
auto solve(int h, int w, int n, const field_t &field, const map<char, Point> &m)-> int
{
    const char strs[] = {
        'S', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    };
 
    // 移動方向（上下左右）
    vector<Point> diff = {
        Point(0, -1), Point(0, 1) , Point(-1, 0), Point(1, 0),
    };
 
    auto is_movable = [field, w, h](const Point &p)-> bool {
        if( (0 <= p.x && p.x < w) && (0 <= p.y && p.y < h) ) {
            char c = field[p.y][p.x];
            if(c != 'X') {
                return true;
            }
        }
        return false;
    };
 
    // 探索
    vector<int> time;
    for(size_t i = 0; i < n; ++i) {
        const char from = strs[i];
        const char to = strs[i + 1];
        queue<Point> q;
        q.push( m.at(from) );
 
        int memo[1002][1002];
        for(int y = 0; y <= h; ++y) {
            for(int x = 0; x <= w; ++x) {
                memo[y][x] = 0;
            }
        }
 
        while( !q.empty() ) {
            Point p = q.front(); q.pop();
 
            if(field[p.y][p.x] == to) {
                time.push_back(memo[p.y][p.x]);
                break;
            }
            for(size_t j = 0; j < diff.size(); ++j) {
                Point next_point( p + diff[j] );
                if(is_movable(next_point) && memo[next_point.y][next_point.x] == 0) {
                    q.push(next_point);
                    memo[next_point.y][next_point.x] = memo[p.y][p.x] + 1;
                }
            }
        }
    }
 
    return accumulate( begin(time), end(time), 0 );
 
}
 
int main()
{
    int height, width, n;
    cin >> height >> width >> n;
 
    field_t field;
    map<char, Point> m;
    for(size_t i = 0; i < height; ++i) {
        vector<char> tmp;
        string src;
        cin >> src;
        for(size_t j = 0, length = src.length(); j < length; ++j) {
            char c = src[j];
            if( !(c == '.' || c == 'X') ) {
                m.insert( make_pair(c, Point(j, i)) );
            }
            tmp.push_back(c);
        }
        field.push_back(tmp);
    }
 
    cout << solve(height, width, n, field, m) << endl;
 
    return 0;
}