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 <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

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

class Data {
   public:
    int x, y, count;
    Data() {}
    Data(int x, int y, int count) : x(x), y(y), count(count) {}
};
int main() {
    int h, w, n;
    cin >> h >> w >> n;
    Data start;
    int ans = 0;
    for (int i = 0; i < h; i++) {
        cin >> field[i];
        for (int j = 0; j < w; j++) {
            if (field[i][j] == 'S') {
                start = Data(j, i, 0);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        queue<Data> Q;
        Q.push(start);
        bool flg[1000][1000] = {{0}};
        while (!Q.empty()) {
            Data d = Q.front(); Q.pop();
            if (field[d.y][d.x] == i + '0') {
                start = Data(d.x, d.y, d.count);
                break;
            }
            if (flg[d.y][d.x]) continue;
            flg[d.y][d.x] = true;
            for (int j = 0; j < 4; j++) {
                int px = d.x + dx[j], py = d.y + dy[j];
                if (px < 0 || py < 0 || px >= w || py >= h) continue;
                if (field[py][px] == 'X') continue;
                Q.push(Data(px, py, d.count + 1));
            }
        }
        ans = start.count;
    }

    cout << ans << endl;
    return 0;
}

C++: #include <stdio.h>
#include <stdlib.h>

#include <queue>

using namespace std;

typedef struct State_Def {
	int y;
	int x;
} S;

const int INF = 1e+8;
int h, w, n;
int x[4] = {1, 0, -1, 0};
int y[4] = {0, 1, 0, -1};
char **data;
int **dist;
int *fX;
int *fY;

int bfs(int sI, int sJ, int gI, int gJ)
{
	int res = INF;
	int i, j;
	queue<S> q;

	S s = {sI, sJ};	
	q.push(s);	

	for (i=0; i<h; i++)
		for (j=0; j<w; j++)
			dist[i][j] = INF;
	dist[sI][sJ] = 0;

	while (q.size()) {
		S t = q.front();
		q.pop();

		if (t.x == gJ && t.y == gI) break;

		for (i=0; i<4; i++) {
			int nx = t.x + x[i];
			int ny = t.y + y[i];

			if (0<=nx && nx<w && 0<=ny && ny<h && data[ny][nx] != 'X' && dist[ny][nx] == INF) {
				dist[ny][nx] = dist[t.y][t.x] + 1;
				S u = {ny, nx};
				q.push(u);
			}
		}
	}

	return dist[gI][gJ];
}

int main()
{
	int i, j;
	int sI, sJ;	
	int res;

	scanf("%d%d%d ", &h, &w, &n);
	data = (char **)calloc(h, sizeof(char *));;
	for (i=0; i<h; i++)
		data[i] = (char *)calloc(w, sizeof(char));

	fX = (int *)calloc(n, sizeof(int));;
	fY = (int *)calloc(n, sizeof(int));;

	for (i=0; i<h; i++) {
		for (j=0; j<w; j++)
			scanf("%c ", &(data[i][j]));
	}

	for (i=0; i<h; i++) {
		for (j=0; j<w; j++) {
			if (data[i][j] == 'S') {
				sI = i;
				sJ = j;
			} else if (0 < data[i][j] - '0' && data[i][j] - '0' <= n) {
				fX[ (int)(data[i][j] - '0') - 1 ] = j;  	
				fY[ (int)(data[i][j] - '0') - 1 ] = i;  	
			}
		}
	}

	dist = (int **)calloc(h, sizeof(int *));;
	for (i=0; i<h; i++) 
		dist[i] = (int *)calloc(w, sizeof(int));

	res = bfs(sI, sJ, fY[0], fX[0]);
	for (i=1; i<n; i++) 
		res += bfs(fY[i-1], fX[i-1], fY[i], fX[i]);

	printf("%d\n", res);

	for (i=0; i<h; i++)
		free(data[i]);
	free(data);

	for (i=0; i<h; i++)
		free(dist[i]);
	free(dist);

	free(fX);
	free(fY);

	return 0;
}

C++: //↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double pi = acos(-1);
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
	for (auto &e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

//↑template↑




int a, b, c, ans, dis[1005][1005];
char area[1005][1005];

int bfs(int n, int m, int o, int p) {
	queue<pair<int, int>>q;
	q.emplace(n, m);
	memset(dis, -1, sizeof(dis));
	dis[n][m] = 0;

	while (!q.empty()) {
		pair<int, int>mon = q.front();
		q.pop();
		if (mon.first == o && mon.second == p) { return dis[mon.first][mon.second]; }

		for (int i = 0; i < 4; ++i) {
			int nn = mon.first + dy[i], mm = mon.second + dx[i];
			if (nn < 0 || mm < 0 || nn >= a || mm >= b || dis[nn][mm] != -1 || area[nn][mm] == 'X') { continue; }
			dis[nn][mm] = dis[mon.first][mon.second] + 1;
			q.emplace(nn, mm);
		}
	}

	return -1;
}

int main() {
	cin >> a >> b >> c;
	vector<pair<int, int>>v(c + 1);
	for (int i = 0; i < a; ++i) {
		for (int j = 0; j < b; ++j) {
			cin >> area[i][j];
			if (area[i][j] == 'S') { v[0] = make_pair(i, j); }
			else if (isdigit(area[i][j])) { v[area[i][j] - '0'] = make_pair(i, j); }
		}
	}

	for (int i = 1; i < c + 1; ++i) {
		ans += bfs(v[i - 1].first, v[i - 1].second, v[i].first, v[i].second);
	}

	cout << ans << endl;
}

C++: #include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct PP{
	int x;
	int y;
	int Z;
	int c;
};
char s[1002][1002],C[11]={"0123456789"};
int D[1002][1002];
int A[1002][1002],d;
int main(){
	PP S;
	queue<PP> P;
	int  w,h;
	int d=0,i=0,j=0,l=-1;
	int x[4]={ 1, 0,-1,0};
	int y[4]={ 0 ,1,0,-1};
	scanf("%d %d %d",&h,&w,&d);
	memset(A,0,sizeof(A));
   memset(D,0,sizeof(D));
		for(i=0;i<h;i++){
		scanf("%s",s[i]);
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
		if(s[i][j]=='S'){
			S.x=j;
			S.y=i;
			S.Z=0;
			S.c=1;
			A[S.y][S.x]=1;
			P.push(S);
		}
		}
	}
	while(1){
		l++;
		
		if(l==4) {
			l=0;
			P.pop();
		}
		S=P.front();

		S.x+=x[l];
		S.y+=y[l];
		S.Z++;

		if(A[S.y][S.x]==1||s[S.y][S.x]=='X'||S.y==h||S.x==w||S.x==-1||S.y==-1){
		continue;
		}
				A[S.y][S.x]=1;
		if(C[S.c]==s[S.y][S.x]){
				S.c++;
				if(S.c==d+1){
				break;
				}
				while(!P.empty()){
				P.pop();
				
				}
			//memset(A,0,sizeof(A));
			l=-1;

		} 
		P.push(S);
	}
	printf("%d\n",S.Z);
	return 0;
}