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 <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <queue>
#include <complex>
#include <climits>
#include <cstring>
#include <cstdlib>

typedef long long ll;

using namespace std;

#define INF 1000000

int H, W, N;
int sx, sy;	
int res = 0;
int d[1100][1100];
char maze[1100][1100];
pair<int, int> cheese[10];

void bfs(int HP){
	queue<pair<int, int> > que;

	sx = cheese[HP-1].first, sy = cheese[HP-1].second;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			d[i][j] = INF;
		}
	}	
	que.push(pair<int, int>(sx, sy));
	d[sx][sy] = 0;

	while(que.size()){
		pair<int, int> p = que.front(); que.pop();
		if((maze[p.first][p.second] - '0') == HP) break;
		for(int dx=-1; dx<=1; ++dx)
			for(int dy=-1; dy<=1; ++dy){
				if(abs(dx-dy) != 1) continue;
				int nx = p.first + dx, ny = p.second + dy;
				if(0 <= nx && nx < H && 0 <= ny && ny < W && maze[nx][ny] != 'X' && d[nx][ny] == INF){
					que.push(pair<int, int>(nx, ny));
					d[nx][ny] = d[p.first][p.second] + 1;
				}
			}
	}

	if(HP == N){
		res += d[cheese[HP].first][cheese[HP].second];
		return;
	}

	res += d[cheese[HP].first][cheese[HP].second];
	bfs(HP+1);
	return;
}

int main(void){
	cin >> H >> W >> N;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			cin >> maze[i][j];
			if(maze[i][j] - '0' >= 1 && maze[i][j] - '0' <= N){
				cheese[maze[i][j] - '0'] = pair<int, int>(i, j);
			} else if(maze[i][j] == 'S'){
				cheese[0] = pair<int, int>(i, j);
			}
		}
	}

	bfs(1);
	int r = res;
	cout << r << endl;
	return 0;
}

C++: #include<iostream>
#include<set> 
#include<vector>
#include<stack>
#include<string>
#include<ctype.h>
#include<sstream> 
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<cstring> 
#include<queue>
using namespace std; 
typedef struct{
	int x;
	int y;
}P;//坐标 

char graph[1024][1024];
P aim[10];
P s, g; // s起点，g终点 
int N,W,H;
int vis[1000][1000];//存储距离 
 int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
 	
int bfs(P s, P g);
int main()
{	
	
	int i, j ,t;
	int step = 0;
	cin>>H>>W>>N;
	for(i = 0; i < H; i++){
		for(j = 0; j < W; j++){
			cin>>graph[i][j];
			if(graph[i][j] <= '9' && graph[i][j] >= '1'){
				t = graph[i][j] - '0';
				aim[t].x = i;//1 - N 坐标存到aim 数组 
				aim[t].y = j;
			}
			else if(graph[i][j] == 'S'){
				s.x = i;
				s.y = j;
				graph[i][j] = '.';	//得到起点 
			}
		}
	}
	for(i = 1; i <= N; i++){
		g.x = aim[i].x;
		g.y = aim[i].y;//1 - N 从小到大 每一次把一个座位作为终点 
		step += bfs(s, g);
		s.x = g.x;
		s.y = g.y;//到达终点后变为起点 
		graph[g.x][g.y] = '.';
	}
	cout<<step<<endl;
	return 0;
 } 
 
int bfs(P s, P g)
{
	queue<P> que;
	P n;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			vis[i][j] = -1;
		}
	}
	que.push(s);
	vis[s.x][s.y] = 0;
	while(que.size()){
		P p = que.front();
		que.pop();
		if(p.x == g.x && p.y == g.y) break;
		for(int i = 0; i < 4; i++){
			n.x = p.x + dx[i];
			n.y = p.y + dy[i];
			if(0 <= n.x && n.x < H && n.y < W && n.y >= 0 && graph[n.x][n.y] != 'X' && vis[n.x][n.y] == -1){
				que.push(n);
				vis[n.x][n.y] == vis[p.x][p.y] + 1;
				
			}
		}
	}
	return vis[g.x][g.y];
 
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

struct P {
   int y, x;
};

int H, W, N;
int sy, sx;
char B[1111][1111];
int dist[1111][1111];
P c[11];
const int INF = 1e8;

void print() {
   rep (i, H) {
      rep (j, W) {
         if (dist[i][j] == INF) {
            printf("%3c", 'I');
         } else {
            printf("%3d", dist[i][j]);
         }
      }
      puts("");
   }
}

int bfs(int y, int x, int ty, int tx) {
   rep (i, H) { rep (j, W) { dist[i][j] = INF; } }
   queue<P> que;
   que.push(P{y, x});
   dist[y][x] = 0;
   while (que.size()) {
      P p = que.front(); que.pop();
      if (p.y == ty && p.x == tx) break;
      rep (i, 4) {
         int ny = p.y + dy[i], nx = p.x + dx[i];
         if (ny < 0 || ny >= H || nx < 0 || nx >= W || B[ny][nx] == 'X' || dist[ny][nx] != INF) continue;
         que.push(P{ny, nx});
         dist[ny][nx] = dist[p.y][p.x] + 1;
      }
   }
   return dist[ty][tx];
}

int main() {
   cin >> H >> W >> N;
   rep (i, H) {
      rep (j, W) {
         cin >> B[i][j];
         if (isdigit(B[i][j])) {
            c[B[i][j]-'0'] = P{i, j};
         }
         if (B[i][j] == 'S') {
            sy = i, sx = j;
         }
      }
   }
   c[0] = P{sy, sx};

   ll sum = 0;
   for (int i = 1; i <= N; i++) {
      // printf("(%d, %d) - (%d, %d)\n", c[i].y, c[i].x, c[i-1].y, c[i-1].x);
      // sum += abs(dist[c[i].y][c[i].x] - dist[c[i-1].y][c[i-1].x]);
      int y = c[i-1].y, x = c[i-1].x;
      int ny = c[i].y, nx = c[i].x;
      sum += bfs(y, x, ny, nx);
   }
   cout << sum << endl;

   return 0;
}