Go: ///
// File:  0558.go
// Author: ymiyamoto
//
// Created on Sun Mar  4 20:58:45 2018
//
package main

import (
	"fmt"
	"strconv"
	"strings"
)

type pos struct {
	x, y int
}

var H, W, N int
var graph [][]string

func wfs(p pos, index int) (int, pos) {
	var q []pos
	dists := make([][]int, H)
	for i := range dists {
		dists[i] = make([]int, W)
	}

	q = append(q, p)
	for len(q) > 0 {
		p := q[0]
		dist := dists[p.x][p.y]
		q = q[1:]

		for _, d := range []pos{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
			x := p.x + d.x
			y := p.y + d.y
			if 0 <= x && x < H && 0 <= y && y < W && graph[x][y] != "X" && dists[x][y] == 0 {
				dists[x][y] = dist + 1
				q = append(q, pos{x, y})
			}
		}
	}

	for i := range graph {
		for j := range graph[i] {
			if graph[i][j] == strconv.Itoa(index) {
				return dists[i][j], pos{i, j}
			}
		}
	}

	panic("not found")
}

func main() {
	fmt.Scan(&H, &W, &N)

	var start pos

	graph = make([][]string, H)
	for i := range graph {
		var s string
		fmt.Scan(&s)
		graph[i] = strings.Split(s, "")
		for j := range graph[i] {
			if graph[i][j] == "S" {
				start.x = i
				start.y = j
			}
		}
	}

	count := 0
	for i := 1; i <= N; i++ {
		c, s := wfs(start, i)
		start = s
		count += c
	}

	fmt.Println(count)
}

C++: #include <iostream>
#include <vector>
#include <queue>
using namespace std;

int h, w, n;
char M[1000][1000];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
pair<int, int> point[10];


int bfs(){
    int reach[h][w];

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                reach[y][x] = -1;
            }
        }
        
        int sy = point[i].first;
        int sx = point[i].second;
        int goaly = point[i+1].first;
        int goalx = point[i+1].second;
        
        queue < pair <int, int> > Q;
        Q.push(make_pair(sy, sx));
        reach[sy][sx] = 0;
        
        int v, z;
        bool arrive = false;
        while(!Q.empty()){
            v = Q.front().first;
            z = Q.front().second;
            Q.pop();

            for(int k = 0; k < 4; k++){
                int ny = v + dy[k];
                int nx = z + dx[k];
                if(ny < 0 || ny >= h || nx < 0 || nx >= w || reach[ny][nx] != -1 || M[ny][nx] == 'X'){
                    continue;
                }
                
                reach[ny][nx] = reach[v][z] + 1;
                Q.push(make_pair(ny, nx));
                if(ny == goaly && nx == goalx){
                    arrive = true;
                    ans += reach[ny][nx];
                }

            }
            
            if(arrive){
                break;
            }
            
        }
        
    }

    
    return ans;
}


int main(void){
    // Your code here!
    cin >> h >> w >> n;
    int sy, sx;
    char tmp;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> tmp;
            if(tmp == 'S'){
               point[0].first = i;
               point[0].second = j;
            }
            
            if(1 <= tmp - '0' && tmp - '0' <= n){
                point[tmp-'0'].first = i;
                point[tmp-'0'].second = j;
            }
            M[i][j] = tmp;
        }
    }
    
    cout << bfs() << endl;
    
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int bfs(vs& grid,int si,int sj,int gi,int gj)
{
	int h=grid.size(),w=grid[0].size();
	vvi vis(h,vi(w));
	queue<tuple<int,int,int>> q;
	q.emplace(si,sj,0);
	while(q.size()){
		int i,j,d; tie(i,j,d)=q.front(); q.pop();
		if(i<0 || h<=i || j<0 || w<=j || grid[i][j]=='X' || vis[i][j]) continue;
		vis[i][j]=1;
		if(i==gi && j==gj) return d;
		rep(k,4) q.emplace(i+"\xff\x1\0\0"[k],j+"\0\0\xff\x1"[k],d+1);
	}
	return -1;
}

int main()
{
	for(int h,w,n;cin>>h>>w>>n;){
		vs grid(h,"#");
		rep(i,h) cin>>grid[i];
		
		rep(i,h) rep(j,w) if(grid[i][j]=='S') grid[i][j]='0';
		int res=0;
		rep(k,n){
			int si,sj,gi,gj;
			rep(i,h) rep(j,w){
				if(grid[i][j]=='0'+k)
					si=i,sj=j;
				if(grid[i][j]=='0'+k+1)
					gi=i,gj=j;
			}
			res+=bfs(grid,si,sj,gi,gj);
		}
		cout<<res<<endl;
	}
}

C++: #include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue <pair<int, int>> q;
	pair<int, int> p;

	char **m;
	char c[10] = { "123456789" };
	int **f;
	int n, k, i, i1, c1, i2, sum = 0;

	cin >> n;
	cin >> k;
	cin >> c1;

	m = new char *[n + 2];
	f = new int *[n + 2];

	for (i = 0; i < n + 2; i++){
		m[i] = new char[k + 2];
		f[i] = new int[k + 2];
	}

	for (i = 1; i <= n; i++){
		for (i1 = 1; i1 <= k; i1++){
			cin >> m[i][i1];
		}
	}

	for (i = 0; i < n + 2; i++){
		for (i1 = 0; i1 < k + 2; i1++){
			if (i == 0 || i == n + 1){
				m[i][i1] = 'X';
			}
			else if (i1 == 0 || i1 == k + 1){
				m[i][i1] = 'X';
			}
		}
	}

	for (i = 1; i <= n; i++){
		for (i1 = 1; m[i][i1] != '\0'; i1++){
			if (m[i][i1] == 'S'){
				q.push(make_pair(i, i1));
			}
		}
	}



	pair<int, int> temp;

	temp = q.front();

	for (i = 0; i < c1; i++){

		for (i1 = 0; i1 < n + 2; i1++){
			for (i2 = 0; i2 < k + 2; i2++){
				if (i1 == 0 || i1 == n + 1){
					f[i1][i2] = 1;
				}
				else if (i2 == 0 || i2 == k + 1){
					f[i1][i2] = 1;
				}
				else
					f[i1][i2] = -1;
			}
		}

		f[temp.first][temp.second] = 0;

		while (!q.empty()){
			p = q.front();
			q.pop();

			//上への探索
			if (m[p.first - 1][p.second] != 'X' && f[p.first - 1][p.second] == -1){
				q.push(make_pair(p.first - 1, p.second));
				f[p.first - 1][p.second] = f[p.first][p.second] + 1;
			}

			//下への探索
			if (m[p.first + 1][p.second] != 'X' && f[p.first + 1][p.second] == -1){
				q.push(make_pair(p.first + 1, p.second));
				f[p.first + 1][p.second] = f[p.first][p.second] + 1;
			}

			//左への探索
			if (m[p.first][p.second - 1] != 'X' && f[p.first][p.second - 1] == -1){
				q.push(make_pair(p.first, p.second - 1));
				f[p.first][p.second - 1] = f[p.first][p.second] + 1;
			}

			//右への探索
			if (m[p.first][p.second + 1] != 'X' && f[p.first][p.second + 1] == -1){
				q.push(make_pair(p.first, p.second + 1));
				f[p.first][p.second + 1] = f[p.first][p.second] + 1;
			}

			//ゴールかどうか？
			if ( m[p.first][p.second] == c[i]){
				sum += f[p.first][p.second];
				temp = p;
			}

		}
	}
	
	cout << sum << endl;
	
return 0;
}