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 <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<P, int> PI; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };
bool visited[1000][1000];
char stage[1000][1000];
int h, w, n;

int main(void)
{
	ios::sync_with_stdio(false);
	while(cin >> h >> w >> n && n)
	{
		PArray goals(n + 1);
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> stage[i][j];
				if(stage[i][j] == 'S') goals[0] = P(i, j);
				int num = stage[i][j] - '0';
				if(inRange(n + 1, num)) goals[num] = P(i, j);
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			P start = goals[i], goal = goals[i + 1];
			memset(visited, false, sizeof(visited));
			queue<PI> que;
			que.push(PI(start, 0));
			while (!que.empty())
			{
				PI pi = que.front(); que.pop();
				if(goal == pi.first)
				{
					ans += pi.second;
					break;
				}
				int r = pi.first.first, c = pi.first.second;
				visited[r][c] = true;

				for (int i = 0; i < 4; i++)
				{
					int nr = r + dr[i], nc = c + dc[i];
					if(!inRange(h, nr) || !inRange(w, nc) || stage[nr][nc] == 'X' || visited[nr][nc]) continue;
					que.push(PI(P(nr, nc), pi.second + 1));
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

typedef pair<int, int> pii;

int m, n, N;
char mat[1002][1002];
int d[1002][1002];
int sx[10], sy[10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int ans;

int bfs(int sx, int sy, int tx, int ty) {
  memset(d, -1, sizeof(d));
  d[sx][sy] = 0;
  queue<pii> q;
  q.push(make_pair(sx, sy));
  int x, y, xx, yy;
  while (!q.empty()) {
    pii cur = q.front();
    q.pop();
    x = cur.first;
    y = cur.second;
    for (int i = 0; i < 4; ++i) {
      xx = x + dx[i];
      yy = y + dy[i];
      if (xx >= 0 && xx < m && yy >= 0 && yy < n && mat[xx][yy] != 'X' && d[xx][yy] == -1) {
        d[xx][yy] = d[x][y] + 1;
        if (xx == tx && yy == ty) {
          return d[xx][yy];
        }
        q.push(make_pair(xx, yy));
      }
    }
  }

}

void solve() {
  ans = 0;
  for (int i = 0; i < m; ++i) {
    cin >> mat[i];
    for (int j = 0; j < n; ++j) {
      if (mat[i][j] == 'S') {
        sx[0] = i;
        sy[0] = j;
      } else if (mat[i][j] >= '1' && mat[i][j] <= '9') {
        int t = mat[i][j] - '0';
        sx[t] = i;
        sy[t] = j;
      }
    }
  }
  for (int i = 1; i <= N; ++i) {
    int tmp = bfs(sx[i - 1], sy[i - 1], sx[i], sy[i]);
    ans += tmp;
  }
}

int main() {
  cin >> m >> n >> N;
  solve();
  cout << ans << endl;
  return 0;
}

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

struct p{
	int x, y;
};
typedef struct p P;
const int INF = 1e+7;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int w,h,n;
string m[1001];
P cheese[11];
int ans = 0;
int d[1001][1001];

void bfs(){
	for(int i=1 ; i <= n ; i++ ){
		P sp = cheese[i-1];
		int sx = cheese[i-1].x;
		int sy = cheese[i-1].y;
		int gx = cheese[i].x;
		int gy = cheese[i].y;
		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				d[y][x] = INF;
			}
		}
		
		queue<P> q;
		q.push( sp );
		d[sy][sx] = 0;
		while( !q.empty() ){
			P now = q.front();
			q.pop();
			int x = now.x;
			int y = now.y;
			if( x == gx && y == gy ){
				ans += d[gy][gx];
				break;
			}
			for(int i=0 ; i < 4 ; i++ ){
				int mx = x + dx[i];
				int my = y + dy[i];
				if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
				if( m[my][mx] != 'X' ){
					P next;
					
					next.x = mx;
					next.y = my;
					if( d[my][mx] == INF ){
						d[my][mx] = d[y][x] + 1;
						q.push( next );
					}
				}
			}
		}
	}
}

int main(){
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> m[y];
	}
	
	
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			char c = m[y][x];
			if( c == 'S' ){
				cheese[0].x = x;
				cheese[0].y = y;
			}
			if( c >= '1' && c <= '9' ){
				cheese[ c - '0' ].x = x;
				cheese[ c - '0' ].y = y;
			}
		}
	}
	bfs();
	cout << ans << endl;
}