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<queue>
#include<string>
using namespace std;
	int a[1000][1000];
	int b[1000][1000];
	string moji[1000];
int main(){
	queue<int> q1;
	int x[10];
	int y[10];
	int e=0;
	int c=0;
	int d=0;
	string g;
	int i=0;
	int j=0;
	int k=0;
	int l=0;
	int s=0;
	int n=0;
	
	for(i=0;i<1000;i++){
		for(j=0;j<1000;j++){
			a[i][j]=10;
			b[i][j]=0;
		}
	}
	g=".123456789XS";
	cin>>e;
	cin>>c;
	cin>>d;
	for(i=0;i<e;i++){
		cin>>moji[i];
	}
	for(i=0;i<e;i++){
		for(j=0;j<c;j++){
			if(moji[i][j]==g[0]){
				a[i][j]=0;
			}else if(moji[i][j]==g[10]){
				a[i][j]=10;
			}else if(moji[i][j]==g[11]){
				a[i][j]=0;
				x[0]=i;
				y[0]=j;
			}else if(moji[i][j]==g[1]){
				a[i][j]=0;
				x[1]=i;
				y[1]=j;
			}else if(moji[i][j]==g[2]){
				a[i][j]=0;
				x[2]=i;
				y[2]=j;
			}else if(moji[i][j]==g[3]){
				a[i][j]=0;
				x[3]=i;
				y[3]=j;
			}else if(moji[i][j]==g[4]){
				a[i][j]=0;
				x[4]=i;
				y[4]=j;
			}else if(moji[i][j]==g[5]){
				a[i][j]=0;
				x[5]=i;
				y[5]=j;
			}else if(moji[i][j]==g[6]){
				a[i][j]=0;
				x[6]=i;
				y[6]=j;
			}else if(moji[i][j]==g[7]){
				a[i][j]=0;
				x[7]=i;
				y[7]=j;
			}else if(moji[i][j]==g[8]){
				a[i][j]=0;
				x[8]=i;
				y[8]=j;
			}else if(moji[i][j]==g[9]){
				a[i][j]=0;
				x[9]=i;
				y[9]=j;
			}
		}
	}
	for(i=0;i<d;i++){
		k=x[i];
		l=y[i];
		for(j=0;j<e*c;j++){
			if(k==x[i+1] && l==y[i+1]){
				break;
			}
			if(a[k+1][l]!=10 && b[k+1][l]==0){
				b[k+1][l]=b[k][l]+1;
				q1.push (k+1);
				q1.push (l);
			}
			if(a[k][l+1]!=10 && b[k][l+1]==0){
				b[k][l+1]=b[k][l]+1;
				q1.push (k);
				q1.push (l+1);
			}
			if(a[k][l-1]!=10 && b[k][l-1]==0){
				b[k][l-1]=b[k][l]+1;
				q1.push (k);
				q1.push (l-1);
			}
			if(a[k-1][l]!=10 && b[k-1][l]==0){
				b[k-1][l]=b[k][l]+1;
				q1.push (k-1);
				q1.push (l);
			}
			k=q1.front();
			q1.pop();
			l=q1.front();
			q1.pop();
		}
		s=s+b[k][l];
		n=q1.size();
		for(j=0;j<n;j++){
			q1.pop();
		}
		for(j=0;j<1000;j++){
			for(k=0;k<1000;k++){
				b[j][k]=0;
			}
		}
	}
	cout<<s;
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int ctoi(char c){
    switch(c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    int d[MAX][MAX];
    int ans=0;
    int sx[10];
    int sy[10];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                sx[0]=i;
                sy[0]=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                sx[ctoi(in)]=i;
                sy[ctoi(in)]=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                d[i][j]=INF;
            }
        }
        que.push(P(sx[k],sy[k]));
        d[sx[k]][sy[k]]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==P(sx[k+1],sy[k+1]))   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.second+dy[l];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]!=INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[sx[k+1]][sy[k+1]];
        queue<P> empty;
        swap(empty,que);
    }
    
    cout<<ans<<endl;
    
    return 0;
}

C++: #include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int dx[4] = {-1,0,0,1}, dy[4] = {0,-1,1,0};
char a[1002][1002];
int b[1002][1002];
queue<pair<int,int> > q;
int main(){
	int h, w, n, t = 0;
	char str[1000][1000];
	rep(i,1002)rep(j,1002)a[i][j] = 'X';
	scanf("%d%d%d", &h, &w, &n);
	rep(i,h)scanf("%s", str[i]);
	rep(i,h)rep(j,w){
		a[i+1][j+1] = str[i][j];
		if(a[i+1][j+1] == 'S'){
			q.push(dmp(i+1, j+1));
		}
	}
	
	pair<int,int> p;
	int x, y, xx, yy, tx, ty, res, ans = 0;
	for(int i = 1;i <= n;i++){
		fill((int*)b, (int*)(b+1002), INF);
		y = q.front().fi, x = q.front().se;
		b[y][x] = 0;
		while(!q.empty()){
			p = q.front();q.pop();
			y = p.fi;x = p.se;t = b[y][x];
			for(int j = 0;j < 4;j++){
				xx = x+dx[j], yy = y+dy[j];
				if(a[yy][xx] != 'X'){
					if(b[yy][xx] == INF)q.push(dmp(yy, xx));
					b[yy][xx] = min(b[yy][xx], t+1);
				}
			}
			if(a[y][x] == i+'0'){
				tx = x;ty = y;
				res = t;
			}
		}
		q.push(dmp(ty, tx));
		ans += res;
	}
	printf("%d\n", ans);
	return 0;
}