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 <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                                                  it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;

// up right down left
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};

const double EPS = 1e-9;
const int days[]     = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

int main(){

    int H,W,N;
    cin >> H >> W >> N;

    vector<vector<char> > F(H,vector<char>(W));


    map<char,int> M;
    int nx,ny;
    rep(i,H) rep(j,W){
        cin >> F[i][j];
        if(F[i][j] == 'S'){
            F[i][j] = '0';
            ny = i;nx = j;
        }
    }

    int cnt = 0;
    for(int i='1';i<=N+'0';i++){
        vector<vector<char> > A(H,vector<char>(W,false));
        //y x depth
        queue<pair<pair<int,int>,int> >  Q;
        Q.push(mp(mp(ny,nx),0));
        while(not Q.empty()){
            int y = Q.front().first.first;
            int x = Q.front().first.second;
            int d = Q.front().second;
            Q.pop();

            if(A[y][x]) continue;
            A[y][x] = true;

            if(F[y][x] eq i){
                cnt += d;
                ny = y;nx = x;
                break;
            }
            for(int j=0;j<4;j++){
                int nowx = x + dx[j];
                int nowy = y + dy[j];
                if(nowx >= W or nowx < 0 or nowy >= H or nowy < 0) continue;
                if(F[nowy][nowx] eq 'X') continue;
                Q.push(mp(mp(nowy,nowx),d+1));
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int maxn = 1004;
const int INF = 0x3f3f3f3f;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, step;
};

int m, n, ans, tot;
bool vis[maxn][maxn];
int G[maxn][maxn];
int posx[12], posy[12];

int bfs(int sx, int sy, char e) {
    queue<Node> que;
    que.push((Node){sx, sy, 0});
    while(!que.empty()) {
        Node t = que.front(); que.pop();
        vis[t.x][t.y] = true;
        if(G[t.x][t.y] == e) return t.step;
        for(int i = 0; i < 4; ++i) {
            int x = t.x + dx[i];
            int y = t.y + dy[i];
            if(x < 0 || y < 0 || x >= m || y >= n)
                continue;
            if(!vis[x][y] && G[x][y] != 'X') {
                vis[x][y] = true;
                que.push((Node){x, y, t.step + 1});
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d%d%d", &m, &n, &tot);
    int sx, sy;
    for(int i = 0; i < m; ++i) {
        getchar();
        for(int j = 0; j < n; ++j) {
            G[i][j] = getchar();
            if(G[i][j] == 'S')
                G[i][j] = '0';
            if(G[i][j] <= '9' && G[i][j] >= '0') {
                int t = G[i][j] - '0';
                posx[t] = i;
                posy[t] = j;
            }
        }
    }
    for(int i = 0; i < tot; ++i) {
        ans += bfs(posx[i], posy[i], i + 1 + '0');
        memset(vis, 0, sizeof(vis));
    }
    printf("%d\n", ans);
    return 0;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int dy[]={-1,0,1,0};
int dx[]={0,-1,0,1};

int H,W,N;
char fld[1010][1010];


int sy,sx,gy,gx;
int dist[1010][1010];
int bfs(int s,int g){
    rep(i,H)rep(j,W){
        if(fld[i][j]==s+'0')sy=i,sx=j;
        if(fld[i][j]==g+'0')gy=i,gx=j;
    }
    fill_n(*dist,1010*1010,1001001001);
    dist[sy][sx]=0;

    queue<pint>que;que.push(pint(sy,sx));
    while(que.size()){
        int y,x;
        tie(y,x)=que.front();
        que.pop();
        rep(i,4){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||ny>=H||nx<0||nx>=W||fld[ny][nx]=='X'||dist[ny][nx]!=1001001001)continue;
            dist[ny][nx]=dist[y][x]+1;
            que.push(pint(ny,nx));
        }
    }

    return dist[gy][gx];
}

signed main(){
    scanf("%lld%lld%lld",&H,&W,&N);
    rep(i,H)rep(j,W){
        scanf(" %c",&fld[i][j]);
        if(fld[i][j]=='S')fld[i][j]='0';
    }

    int ans=0;
    rep(i,N)ans+=bfs(i,i+1);
    cout<<ans<<endl;
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int H, W, N;

int Sx, Sy;
int st[10], ed[10];

vector<string> map, smap;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

struct State {
	int x, y, d;
	State (int _x, int _y, int _d) : x(_x), y(_y), d(_d) {}
};

int bfs(int sx, int sy, int ex, int ey) {
	queue<State> q;
	q.push(State(sx, sy, 0));
	smap[sy][sx] = '-';
	
	while (!q.empty()) {
		State s = q.front(); q.pop();
		
		if (s.x == ex && s.y == ey) return s.d;
		
		for (int d=0; d<4; d++) {
			int nx = s.x + dx[d], ny = s.y + dy[d];
			
			if (!(0<=nx && nx<W && 0<=ny && ny<H)) continue;
			if (smap[ny][nx]=='-' || smap[ny][nx]=='X') continue;
			
			smap[ny][nx] = '-';
			q.push(State(nx, ny, s.d+1));
		}
	}
	
	return -1;
}

void solve() {
	int ans = 0;
	smap = map;
	ans += bfs(Sx, Sy, st[1], ed[1]);
	
	for (int i=2; i<=N; i++) {
		smap = map;
		ans += bfs(st[i-1], ed[i-1], st[i], ed[i]);
	}
	
	cout << ans << endl;
}

int main() {
	cin >> H >> W >> N;
	for (int i=0; i<H; i++) {
		string s; cin >> s;
		map.push_back(s);
		for (int j=0; j<W; j++) {
			if (s[j]=='S') { Sx = j; Sy = i; }
			if ('1' <= s[j] && s[j] && '9') { st[s[j]-'0'] = j; ed[s[j]-'0'] = i; }
		}
	}
	
	solve();
	
	return 0;
}