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 <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
 
 
 
int main()
{
 
    queue < pair<int, int> > q;
    pair<int, int> p;
 
 
 
    char **m;
    char c[10] = { "123456789" };
    int **f;
	bool flg = false;
    int n, k, i, i1, c1, i2, sum = 0;
    cin >> n;
    cin >> k;
    cin >> c1;
 
    m = new char *[n + 2];
    f = new int *[n + 2];
 
    for (i = 0; i < n + 2; i++){
        m[i] = new char[k + 2];
        f[i] = new int[k + 2];
    }
 
    for (i = 1; i <= n; i++){
        for (i1 = 1; i1 <= k; i1++){
            cin >> m[i][i1];
        }
    }
 
    for (i = 0; i < n + 2; i++){
        for (i1 = 0; i1 < k + 2; i1++){
            if (i == 0 || i == n + 1){
                m[i][i1] = 'X';
            }
            else if (i1 == 0 || i1 == k + 1){
                m[i][i1] = 'X';
            }
        }
    }
 
    for (i = 1; i <= n; i++){
        for (i1 = 1; m[i][i1] != '\0'; i1++){
            if (m[i][i1] == 'S'){
                q.push(make_pair(i, i1));
            }
        }
    }
 
 
 
    pair<int, int> temp;
 
    temp = q.front();
 
    for (i = 0; i < c1; i++){

		for (i1 = 0; i1 < n + 2; i1++){
				for (i2 = 0; i2 < k + 2; i2++){
					if ((i1 == 0 || i1 == n + 1) && !flg){
						f[i1][i2] = 1;
					}
					else if ((i2 == 0 || i2 == k + 1) && !flg){
						f[i1][i2] = 1;
					}
					else
						f[i1][i2] = -1;
				}
		}

		flg = true;

        f[temp.first][temp.second] = 0;
 
		while (!q.empty()){
            p = q.front();
            q.pop();
 
            int x[4] = { -1, 1, 0, 0 }, y[4] = { 0, 0, -1, 1 };
 
            for (int j = 0; j < 4; j++){
 
                //???????????´??????????´¢
                if (m[p.first + x[j]][p.second + y[j]] != 'X' && f[p.first + x[j]][p.second + y[j]] < 0){
                    q.push(make_pair(p.first + x[j], p.second + y[j]));
                    f[p.first + x[j]][p.second + y[j]] = f[p.first][p.second] + 1;
                }
            }
            //??´?????????????????????
            if (m[p.first][p.second] == c[i]){
                sum += f[p.first][p.second];
                temp = p;
                while (!q.empty()){
                    q.pop();
                }
                q.push(p);
                break;
			}
		}
	}
 
    cout << sum << endl;
 
    return 0;
}

C++: #include <iostream>
#include <utility>
#include <queue>
#define N 1001
using namespace std;
int bfs(int,int,int,int);
int h,w,d[N][N];
pair<int,int> P[10];
string str[N];
int main(){
  int n,i,j,sum;
  cin >> h >> w >> n;
  for(i=0;i<=w;i++) str[0]+='X';
  for(i=1;i<=h;i++) cin >> str[i],str[i]='X'+str[i];
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(str[i][j]=='S') P[0].first=i,P[0].second=j;
      if('1'<=str[i][j]&&str[i][j]<='9'){
	P[str[i][j]-'0'].first=i;
	P[str[i][j]-'0'].second=j;
      }
    }
  }
  sum=bfs(P[0].first,P[0].second,P[1].first,P[1].second);
  for(i=1;i<n;i++) sum+=bfs(P[i].first,P[i].second,P[i+1].first,P[i+1].second);
  cout << sum << endl;
}
int bfs(int sx,int sy,int gx,int gy){
  int ux,uy,i,j,ret;
  queue<int> Qx;
  queue<int> Qy;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      d[i][j]=-1;
    }
  }
  Qx.push(sx);
  Qy.push(sy);
  d[sx][sy]=0;
  while(Qx.empty()!=1){
    ux=Qx.front();
    uy=Qy.front();
    if(str[ux][uy]==str[gx][gy]){
      ret=d[ux][uy];
      break;
    }
    Qx.pop(),Qy.pop();
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(ux==i&&uy==j){
	  if(d[i][j-1]==-1&&str[i][j-1]!='X'){
	    d[i][j-1]=d[ux][uy]+1;
	    Qx.push(i);
	    Qy.push(j-1);
	  }
	  if(d[i][j+1]==-1&&str[i][j+1]!='X'){
	    d[i][j+1]=d[ux][uy]+1;
	    Qx.push(i);
	    Qy.push(j+1);
	  }
	  if(d[i-1][j]==-1&&str[i-1][j]!='X'){
	    d[i-1][j]=d[ux][uy]+1;
	    Qx.push(i-1);
	    Qy.push(j);
	  }
	  if(d[i+1][j]==-1&&str[i+1][j]!='X'){
	    d[i+1][j]=d[ux][uy]+1;
	    Qx.push(i+1);
	    Qy.push(j);
	  }
	}
      }
    }
  }
  return ret;
}

C++: #include<cstdio>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> Point;
const int INF = 100000000;
const int MAX_H = 1200;
const int MAX_W = 1200;
int d[MAX_H][MAX_W];
char data[MAX_H][MAX_W];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int solve(Point start, Point goal, int H, int W){
  queue<Point> q;
  q.push(start);
  for(int i = 0 ; i < MAX_H ; i++){
    for(int j = 0 ; j < MAX_W ; j++)
      d[i][j] = INF;
  }
  d[start.first][start.second] = 0;
  while(q.size()){
    Point p = q.front();
    q.pop();
    if(p.first == goal.first && p.second == goal.second)
      return d[p.first][p.second];
    else{
      int i = p.first;
      int j = p.second;
      for(int k = 0 ; k < 4 ; k++){
        int i_ = i + dy[k];
        int j_ = j + dx[k];
        if(i_ >= 0 && i_ < H && j_ >= 0 && j_ < W && data[i_][j_] == '.' && d[i_][j_] == INF){
          q.push(make_pair(i_,j_));
          d[i_][j_] = d[i][j] + 1;
        }
      }
    }
  }
}
int main(){
  int H,W,N;
  scanf("%d %d %d",&H,&W,&N);
  char str[MAX_W];
  Point p[N+1];
  for(int i = 0 ; i < H ; i++){
    scanf("%s",str);
    for(int j = 0 ; j < W ; j++){
      if(str[j] == 'S'){
        p[0] = make_pair(i,j);
        data[i][j] = '.';
      }
      else if(str[j] >= '1' && str[j] <= '9'){
        p[str[j] - '0'] = make_pair(i,j);
        data[i][j] = '.';
      }
      else
        data[i][j] = str[j];
    }
  }
  int ans = 0;
  for(int i = 0 ; i < N ; i++)
    ans += solve(p[i],p[i+1],H,W);
  printf("%d\n",ans);
}