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 <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);

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

struct state {
	int x, y, t;
	state(int x, int y, int t) : x(x), y(y), t(t) {};
};

int main() {
	int H, W, N;
	cin >> H >> W >> N;

	vs field(H);
	REP(i, H) {
		cin >> field[i];
	}
	
	vector<pii> pos(N+1);
	int sx, sy;

	REP(i, H) {
		REP(j, W) {
			switch(field[i][j]) {
			case 'S':
				sx = j;
				sy = i;
				break;
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				int a = field[i][j] - '0';
				pos[a] = make_pair(i, j);
				break;
			}
		}
	}

	queue<state> Q;
	int gx, gy;
	int ans = 0;
	REP(i, N) {
		queue<state> Q;
		if(i != 0) {
			sx = pos[i].second;
			sy = pos[i].first;
		}
		gx = pos[i+1].second;
		gy = pos[i+1].first;
		Q.push(state(sx, sy, 0));
		
		vvi table(H, vi(W, INT_MAX));
		while(!Q.empty()) {
			state st = Q.front();
			Q.pop();

			REP(d, 4) {
				int xx = st.x + dx[d];
				int yy = st.y + dy[d];

				if(0 <= xx && xx < W && 0 <= yy && yy < H) {
					if(xx == gx && yy == gy) {
						ans += st.t+1;
						goto next;
					} else {
						if(field[yy][xx] != 'X') {
							if(table[yy][xx] > st.t+1) {
								table[yy][xx] = st.t+1;
								Q.push(state(xx, yy, st.t+1));
							}
						}
					}
				}
			}
		}
		next:;
	}

	cout << ans << endl;
	return 0;
}

C++: #include <stdio.h>
#include <queue>
using namespace std;
int d[1000][1000], sx, sy;
char s[1000][1000];
int h,w,n;
int k, l;

int bfs(int,int,int,int);

int main(){
  int result = 0;
  int x[10], y[10], v;
  scanf("%d %d %d", &h, &w, &n);
  for(k = 0 ; k < h ; k++){
      scanf("%s",s[k]);
    }
  for( k = 0 ; k < h ; k++ ){
    for( l = 0 ; l < w ; l++){
      if(s[k][l] == 'S'){
	x[0] = l; y[0] = k;
      }
      if('1' <= s[k][l] && s[k][l] <= '9'){
	v = s[k][l]-'1'+1;
	x[v] = l; y[v] = k;
      }
    }
  }
  for (k = 1 ; k <= n ; k++){
   
    result += bfs(x[k-1],y[k-1],x[k],y[k]);
  }
  printf("%d\n", result);
  return 0;
}

int bfs(int sx, int sy, int gx, int gy){
  queue<int> Q;
  int i, j;
  int dx[4]={0, 1, 0, -1};
  int dy[4]={1, 0, -1, 0};
  

  for( i =  0 ; i < h ; i++ ){
    for( j = 0 ; j < w ; j++ ){
      d[i][j] = 100000;
    }
  }

  Q.push(sy*w+sx);
  d[sy][sx]=0; /*スタート地点の初期化*/

  while( !Q.empty() ){
    int u = Q.front(); Q.pop();
    int pi = u/w;
    int pj = u%w;
    if( pi == gy && pj == gx )return d[gy][gx];
    for ( int r = 0; r < 4; r++ ){
      int ni = pi + dy[r];
      int nj = pj + dx[r];
      if ( ni < 0 || nj < 0 || ni >= h || nj >= w ) continue;
      if ( s[ni][nj] == 'X' ) continue;
      if( d[ni][nj] > d[pi][pj]+1 ){
      d[ni][nj] = d[pi][pj] + 1;
      Q.push( ni * w + nj );
      }

    }


  }
  //  printf("%d\n",u);
  return -1;
}

C++: #include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;


int main()
{

	queue < pair<int, int> > q;
	pair<int, int> p;

	char **m;
	char c[10] = { "123456789" };
	int **f;
	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){
					f[i1][i2] = 1;
				}
				else if (i2 == 0 || i2 == k + 1){
					f[i1][i2] = 1;
				}
				else
					f[i1][i2] = -1;
			}
		}

		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;
				}
		}
	}
	
	cout << sum << endl;
	
return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
int h,w,n,Min,f[1001][1001],fx[10],fy[10];
char s[1001][1001];
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int bfs(int sx,int sy,int gx,int gy)
{
	memset(f,0,sizeof(f));
	queue<int>x,y;
	x.push(sx);y.push(sy);f[sx][sy]=1;
	while(!x.empty()){
		int hx=x.front(),hy=y.front();
		x.pop();y.pop();
		if(hx==gx&&hy==gy)break;
		for(int i=0;i<4;i++){
			int nx=hx+dx[i],ny=hy+dy[i];
			if(nx>=1&&nx<=h&&ny>=1&&ny<=w&&s[nx][ny]!='X'&&!f[nx][ny]){
				f[nx][ny]=f[hx][hy]+1;
				x.push(nx);y.push(ny);
			}
		}
	}
	return f[gx][gy]-1;
}
int main()
{
#ifdef debug
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	cin>>h>>w>>n;
	for(int i=1;i<=h;i++)
	 for(int j=1;j<=w;j++){
	 	cin>>s[i][j];
	 	if(s[i][j]=='S'){
	 		fx[0]=i;
	 		fy[0]=j;
		 }
		 else if(s[i][j]>='1'&&s[i][j]<='9'){
		 	fx[s[i][j]-'0']=i;
		 	fy[s[i][j]-'0']=j;
		 }
	 }
	for(int i=1;i<=n;i++)
		Min+=bfs(fx[i-1],fy[i-1],fx[i],fy[i]);
	cout<<Min<<endl;
	return 0;
}