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<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define MP make_pair
long long int map[1002][1002], mmap[1002][1002], tai = 1;
int main()
{
	int n, w, h, s,x,y,siz,cnt=0,flg=0;
	char c[2002];
	pair<int, int> q;
	queue<pair<int,int> > que;
	queue<int>quec;
	quec.push(0);
	scanf("%d %d %d", &h, &w, &n);
	for (int i = 1; i <= h; i++)
	{
		scanf("%s", c);
		for (int j = 1; j <= w; j++)
		{

			if (c[j - 1] == 'S')
			{
				que.push(MP(i, j));
			}
			if (c[j-1] == 'X')
				map[i][j] = -1;
			s = c[j-1];
			if (s > 48 && s < 58)
				map[i][j] = s - 48;
		}
	}
	for (int i = 0; i <= h + 1; i++)
	{
		map[i][0] = -1;
		map[i][w + 1] = -1;
	}
	for (int i = 0; i <= w + 1; i++)
	{
		map[0][i] = -1;
		map[h + 1][i] = -1;
	}
/*	for (int i = 0; i <= h + 3; i++)
	{
		for (int j = 0; j <= w + 3; j++)
		{
			printf("%2lld", map[i][j]);
		}
		cout << endl;
	}*/
	while (!que.empty())
	{
		x = que.front().first;
		y = que.front().second;
		flg = 0;
		cnt = quec.front();
		quec.pop();
		que.pop();
		mmap[x][y] = -1;
		if (map[x - 1][y] != -1&&mmap[x-1][y]!=-1&&flg==0)
		{
			que.push(MP(x - 1, y));
			quec.push(cnt + 1);
			mmap[x - 1][y] = -1;
			if (map[x - 1][y] == tai)
			{
				flg = 1;
				tai++;
				for (int i = 1; i <= h; i++)
				{
					for (int j = 1; j <= w; j++)
					{
						mmap[i][j] = 0;
					}
				}
				while (que.size() > 1)
				{
					que.pop();
					quec.pop();
				}
			}
		}
		if (map[x][y+1] != -1 && mmap[x][y+1] != -1&&flg==0)
		{
			que.push(MP(x , y+1));
			quec.push(cnt + 1);
			mmap[x][y+1] = -1;
			if (map[x][y+1] == tai)
			{
				flg = 1;
				tai++;
				for (int i = 1; i <= h; i++)
				{
					for (int j = 1; j <= w; j++)
					{
						mmap[i][j] = 0;
					}
				}
				while (que.size() > 1)
				{
					que.pop();
					quec.pop();
				}
			}

		}
		if (map[x+1][y] != -1 && mmap[x+1][y] != -1&&flg==0)
		{
			que.push(MP(x + 1, y));
			quec.push(cnt + 1);
			mmap[x+1][y] = -1;
			if (map[x+1][y] == tai)
			{
				flg = 1;
				tai++;
				for (int i = 1; i <= h; i++)
				{
					for (int j = 1; j <= w; j++)
					{
						mmap[i][j] = 0;
					}
				}
				while (que.size() > 1)
				{
					que.pop();
					quec.pop();
				}
			}
		}
		if (map[x][y-1] != -1 && mmap[x][y-1] != -1&&flg==0)
		{
			que.push(MP(x , y-1));
			quec.push(cnt + 1);
			mmap[x][y-1] = -1;
			if (map[x][y-1] == tai)
			{
				flg = 1;
				tai++;
				for (int i = 1; i <= h; i++)
				{
					for (int j = 1; j <= w; j++)
					{
						mmap[i][j] = 0;
					}
				}
				while (que.size() > 1)
				{
					que.pop();
					quec.pop();
				}
			}
		}
		if (tai == n + 1)
			break;
	}
	printf("%d\n", quec.front());
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int clz(int x) { return 31 - __builtin_clz(x); }
int clz(ll x) { return 63 - __builtin_clzll(x); }
int ctz(int x) { return __builtin_ctz(x); }
int ctz(ll x) { return __builtin_ctzll(x); }

class compare {
public:
	bool operator()(tuple<ll, ll> a, tuple<ll, ll> b) {
		return (get<1>(a) > get<1>(b));
	}
};

void solve(){

}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w,n;
	ll ans=0;
	char c;
	cin>>h>>w>>n;
	vl sx(n+1),sy(n+1);
	int tx,ty;
	vvl vv(h+2,vl(w+2,-1));
	rep(i,h){
		rep(j,w){
			cin>>c;
			vv[i+1][j+1]=(c!='X'?INF:-1);
			if(c=='S'){sx[0]=i+1,sy[0]=j+1;}
			if(1<=c-'0'&&c-'0'<=9){sx[c-'0']=i+1;sy[c-'0']=j+1;}
		}
	}
	rep(i,n){

		queue<pll> q;
		vv[sx[i]][sy[i]]=0;
		q.push(pll(sx[i],sy[i]));
		while(!q.empty()){
			tie(tx,ty)=q.front();q.pop();
			rep(i,4){
				if(vv[tx+dx[i]][ty+dy[i]]==INF){
					vv[tx+dx[i]][ty+dy[i]]=vv[tx][ty]+1;
					q.push(pll(tx+dx[i],ty+dy[i]));
				}
			}
		}
		ans+=(vv[sx[i+1]][sy[i+1]]-vv[sx[i]][sy[i]]);
		rep(i,h){
			rep(j,w){
				if(vv[i+1][j+1]!=-1)vv[i+1][j+1]=INF;
			}
		}
	}
	cout<<ans<<endl;
}

C++: #include <iostream>
#include <queue>
#include <utility>
#include <ctype.h>
#include <cstdlib>
using namespace std;

typedef pair<int,int> P;
int H,W,N;
int inf = 10e8;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
char G[1010][1010];
int hp = 1,sum = 0;
int sx,sy;
int times[1010][1010];

bool valid(int x,int y){
	return 0<=x && x<H && 0<=y && y<W && G[x][y]!='X';
}

int bfs(){
	queue<P> q;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			times[i][j] = inf;
		}
	}
	while(hp<=N){
		q.push(P(sx,sy));
		times[sx][sy] = 0;
		while(q.size()){
			P p = q.front();q.pop();
			if(isdigit(G[p.first][p.second]) && hp == atoi(&G[p.first][p.second])){
				hp++;
				sum += times[p.first][p.second];
				sx = p.first;sy = p.second;
				for(int i=0;i<H;i++){
					for(int j=0;j<W;j++){
						times[i][j] = inf;
					}
				}
				while(q.size()){
					q.pop();
				}
				break;
			}
			for(int i=0;i<4;i++){
				int x = p.first + dx[i] , y  = p.second + dy[i];
				if(valid(x,y) && times[x][y]==inf){
					q.push(P(x,y));
					times[x][y] = times[p.first][p.second] + 1;
				}
			}
		}
	}
	return sum;
}

int main(){
	cin >> H >> W >> N;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin >> G[i][j];
			if(G[i][j] == 'S'){
				sx = i;
				sy = j;
			}
		}
	}
	cout << bfs() << endl;
}