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<bits/stdc++.h>
using namespace std;
typedef long long ll;

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

int main(){
 int H,W,N; cin >> H >> W >> N;
  
 vector<vector<char>> S(H,vector<char>(W));
  
  deque<tuple<int,int,int>> starts;
 
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){ 
      cin >> S[i][j];  char c = S[i][j];
      if( c == 'S'){ starts.push_back(make_tuple(0,i,j));}
      else if( 1<= c-'0' && c-'0'<= 9){
        starts.push_back(make_tuple(c-'0',i,j));}
    }
  }
  
  sort(starts.begin(),starts.end());
  
  //BFS
  int length = 0;
  
  for(int i = 0; i < starts.size()-1; i++){
    queue<tuple<int,int,int>> Q;
    
    Q.push(make_tuple(get<1>(starts[i]),get<2>(starts[i]),0));
    // selecting the new start 
    pair<int,int> goal = make_pair(get<1>(starts[i+1]),get<2>(starts[i+1]));
    
    vector<vector<int>> visited(H,vector<int>(W,-1));
    
    visited[get<1>(starts[i])][get<2>(starts[i])] = 0;
    // -1 means this point has not been visited
    while(!Q.empty()){
      tuple<int,int,int> p = Q.front(); Q.pop();
      int x = get<0>(p); int y = get<1>(p);  int L = get<2>(p);
      visited[x][y] = L;
      
      for(int k = 0; k < 4; k++){
        int a = x+dx[k]; int b = y+dy[k];
        if( a < 0 || a >= H || b < 0 || b >= W){ continue;}
        if( visited[a][b] != -1){ continue;}
        if( S[a][b] == 'X' ){ continue;}
        
        visited[a][b] = L+1; Q.push(make_tuple(a,b,L+1));
      }
    }
      length += visited[goal.first][goal.second];
  }
    
    cout << length << endl; return 0;}

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

typedef pair<int,int> P;
const int INF = 1e+8;
// 入力
int w, h, n;
char c[1001][1001];
// 4近傍
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
// d[y][x] := スタートから(x,y)までの最短距離 (未探索のときは INF )
int d[1001][1001];

// 文字 s から文字 s+1 までの最短距離を返す. (s は'0'-'8')
int bfs(char s){
	int sx, sy, gx, gy;
	// 初期化とスタート位置とゴール位置を探す.
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			d[y][x] = INF;
			// 処理しやすいように 'S' を '0' に置き換える.
			if( c[y][x] == 'S' ) c[y][x] = '0';
			if( c[y][x] == s ) sx = x, sy = y;
			if( c[y][x] == s+1 ) gx = x, gy = y;
		}
	}
	// スタート位置をキューに入れる
	queue<P> q;
	q.push( P(sx,sy) );
	d[sy][sx] = 0;
	int res = INF;
	while( !q.empty() ){
		int x = q.front().first;
		int y = q.front().second;
		int cost = d[y][x];
		q.pop();
		
		// ゴールのとき
		if( x == gx && y == gy ){
			res = cost;
			break;
		}
		
		// 4方向探索
		for(int i=0 ; i < 4 ; i++ ){
			int mx = x + dx[i];
			int my = y + dy[i];
			if( mx < 0 || my < 0 || w <= mx || h <= my ) continue;
			if( c[my][mx] == 'X' ) continue;
			
			if( cost+1 < d[my][mx] ){
				d[my][mx] = cost + 1;
				q.push( P(mx,my) );
			}
		}
	}
	return res;
}

int main(){
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> c[y];
	}
	int ans = 0;
	for(int i=0 ; i < n ; i++ ){
		ans += bfs(i+'0');
	}
	cout << ans << endl;
}

C++: #include <cstdio>
#include <iostream>
#include <queue>
#define min(x,y) ((x)<(y)?(x):(y))
#define INFI 65535

using namespace std;
typedef pair<int, int> P;

int Strength = 1;
int Maps[1010][1010];
int dist[1010][1010];
int H, W, N;
int hor[] = {1,0,-1,0};
int ver[] = {0,-1,0,1};
int ans;


void clear();
void show();
P bfs(int cheese,P n);

int main(void) {
    scanf("%d %d %d", &H, &W, &N);
    P s,e;
    for (int i = 0; i<H; i++) {
        getchar();
        for (int j = 0; j<W; j++) {
            Maps[i][j] = getchar();
            if (Maps[i][j]=='S') s.first = i, s.second = j;
        }
    }
    
    P tmp;
    tmp.first = s.first; tmp.second = s.second;
    
    for (int i = 1; i<=N; i++) {
        clear();
        tmp = bfs(i, tmp);
    }
    
    printf("%d\n", ans);
    return 0;
}

P bfs(int cheese,P n) {
    P end;
    queue<P> que;
    que.push(n);
    dist[n.first][n.second] = 0;
    
    while (que.size()) {
        P top = que.front();
        
        que.pop();
        for (int i = 0; i<4; i++) {
            int nv = top.first+ver[i], nh = top.second+hor[i];
            if (nv>=0 && nv<H && nh>=0 && nh<W && dist[nv][nh]==INFI) {
                    if (Maps[nv][nh]=='.' || (isdigit(Maps[nv][nh]) && cheese!=Maps[nv][nh]-'0'))
                        que.push(P(nv,nh)),dist[nv][nh] = min(dist[nv][nh], dist[top.first][top.second]+1);
                    else if (isdigit(Maps[nv][nh]) && cheese==Maps[nv][nh]-'0') {
                        que.push(P(nv,nh));
                        dist[nv][nh] = min(dist[nv][nh], dist[top.first][top.second]+1);
                        end.first = nv; end.second = nh;
                        break;
                    }
            }
        }
    }
    ans += dist[end.first][end.second];
    return end;
}

void clear() {
    for (int i = 0; i<H; i++)
        for (int j = 0; j<W; j++)
            dist[i][j] = INFI;
}