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<cstring>
#include<queue>
using namespace std ;
struct ST
{
	int x ;
	int y ;
	int cnt = 0 ;
} ;
bool came[ 1000 ][ 1000 ] = {{ 0 }} ;
char map[ 1000 ][ 1000 ] ;
int main()
{
	ST m ,s ;
	queue< ST > que ;
	int n ;
	int w ,h ;
	int kyori = 0 ;
	int mx[ 4 ] = { 0 ,0 ,1 ,-1 } ;
	int my[ 4 ] = { 1 ,-1 ,0 ,0 } ;
	cin >> h >> w >> n ;
	int fx ,fy ;
	char c = '0' ;
	bool a = true ;	
	for( int i = 0 ; i < h ; i++ )
	{
		cin >> map[ i ] ;
		for( int j = 0 ; j < w ; j++ && a )
		{
			if( map[ i ][ j ] == 'S' )
			{
				m.x = j ;
				m.y = i ;
				a = false ;
			}
		}
	}
	que.push( m ) ;
	while( n )
	{
		n-- ;
		c++ ;
		while( !que.empty() )
		{
			m = que.front() ;
			que.pop() ;
			came[ m.y ][ m.x ] = 1 ;
			if( map[ m.y ][ m.x ] == c )
			{
				kyori += m.cnt ;
				while( ! que.empty() )
				{
					que.pop() ;
				}
				break ;
			}
			for( int i = 0 ; i < 4 ; i++ )
			{
				if( m.x + mx[ i ] > -1 && m.x + mx[ i ] < w && m.y +  my[ i ] > -1 && m.y + my[ i ] < h )
				{
					s = m ;
					s.x += mx[ i ] ;
					s.y += my[ i ] ;
					s.cnt++ ;
					if( map[ s.y ][ s.x ] != 'X' && came[ s.y ][ s.x ] == 0 )
					{
						que.push( s ) ;
					}
				}
			}
		}
		memset( came ,0 ,sizeof( came ) ) ;
		m.cnt = 0 ;
		que.push( m ) ;
	}
	cout << kyori << endl ;
	return 0 ;
}

C++: #include <cstdio>
#include <queue>
#define MAX 1010
using namespace std;
typedef pair<int,int> Site;

char G[MAX][MAX];
int Sx[15];
int Sy[15];
int Vec[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int H(0),W(0),N(0);
int res=0;

void BFS()
{
	int i=0;
	int size;
	int step;
	while (Sx[i+1])
	{
		queue<Site> Qs;
		Qs.push (Site(Sx[i],Sy[i]));
		size=1;
		step=1;
		while (Qs.size ())
		{
			Site p=Qs.front ();
			Qs.pop();
			for (int j=0;j<4;++j)
			{
				if (p.first+Vec[j][0]==Sx[i+1]&&p.second+Vec[j][1]==Sy[i+1])
				{
					res+=step;
					goto KK;
				}
				if (G[p.first+Vec[j][0]][p.second+Vec[j][1]]=='.'||G[p.first+Vec[j][0]][p.second+Vec[j][1]]<i+'0')
				{
					G[p.first+Vec[j][0]][p.second+Vec[j][1]]=i+'0';
					Qs.push (Site(p.first+Vec[j][0],p.second+Vec[j][1]));
				}
			}
			--size;
			if (size==0)
			{
				size=Qs.size ();
				++step;
			}
		}
KK:
		++i;
	}

}

void debug()
{  	
	freopen("AOJ-0558-in.txt", "r",stdin);
	freopen("AOJ-0558-out.txt", "w",stdout);

}


int main()
{

// 	debug ();
	
	while (scanf("%d%d%d",&H,&W,&N),H)
	{
		for (int tt=0;tt<15;++tt)
		{
			Sx[tt]=Sy[tt]=0;
		}
		for (int ni=0;ni<H+2;++ni)
		{
			G[ni][0]=G[ni][W+1]='X';
		}
		for (int mi=0;mi<W+2;++mi)
		{
			G[0][mi]=G[H+1][mi]='X';
		}

		for (int iH=0;iH<H;++iH)
		{
			for (int iW=0;iW<W;++iW)
			{
				scanf ("%c",&G[iH+1][iW+1]);
				while (G[iH+1][iW+1]=='\n'||G[iH+1][iW+1]==' ')
				{
					scanf ("%c",&G[iH+1][iW+1]);
				}
				char t=G[iH+1][iW+1];
				if (t>='1'&&t<='9')
				{
					Sx[t-'0']=iH+1;
					Sy[t-'0']=iW+1;
					G[iH+1][iW+1]='.';
				}
				else if (t=='S')
				{
					Sx[0]=iH+1;
					Sy[0]=iW+1;
					G[iH+1][iW+1]='.';
				}
			}
		}
// 		for (int x=0;x<H+2;++x)
// 		{
// 			for(int y=0;y<W+2;++y)
// 			{
// 				printf ("%c",G[x][y]);
// 			}
// 			printf ("\n");
// 		}
		BFS();
		printf ("%d\n",res);
		res=0;
		H=0;
	}
	return 0;

}

C++: #include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dij[] = {0, 1, 0, -1, 0};
int main() {
    int h, w, n; cin >> h >> w >> n;
    vector<string> grid(h);
    for (string &s: grid) cin >> s;
    int si, sj;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (grid[i][j] == 'S') si = i, sj = j;
    }
    int gi, gj;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (grid[i][j] == '0' + n) gi = i, gj = j;
    }
    using vvi = vector<vector<int>>;
    vector<vvi> dp(n + 1, vvi(h, vector<int>(w, -1)));
    queue<tuple<int, int, int>> que;
    dp[0][si][sj] = 0; que.emplace(0, si, sj);
    while (!que.empty()) {
        int d, i, j;
        tie(d, i, j) = que.front(); que.pop();
        for (int k = 0; k < 4; k++) {
            int ni = i + dij[k];
            int nj = j + dij[k + 1];
            if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if (grid[ni][nj] == 'X') continue;
            int nd = d + (grid[ni][nj] == '0' + d + 1);
            if (~dp[nd][ni][nj]) continue;
            dp[nd][ni][nj] = dp[d][i][j] + 1;
            que.emplace(nd, ni, nj);
        }
    }
    cout << dp[n][gi][gj] << endl;
    return 0;
}

C++: #include <algorithm>
#include <cmath>
#include <climits>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map> //pair is also included in this library
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define fst first
#define snd second
#define MP make_pair //incase c++11 or later is not available

using namespace std;

typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//prefer define statement
//for reason that const int ver. of INF will raise a silly warning (unused variable)
#define INF (INT_MAX/3)
#define LIM_INF (INT_MAX)
//const int INF = INT_MAX/3;

/*------------------------------------------------------------------------------*/

int cost[1100][1100];

int main(){
  int H, W, N;
  cin >> H >> W >> N;
  vector<string> s;

  s.push_back(string(W+2, 'X'));
  REP(i, 0, H){
    string tmp;
    cin >> tmp;
    s.push_back('X' + tmp + 'X');
  }
  s.push_back(string(W+2, 'X'));

  vector<PII> v(N+1);
  REP(i, 0, H+2){
    REP(j, 0, W+2){
      char c = s[i][j];
      if(c >= '1' && c <= '9'){
        v[c-'0'] = {i, j};
      } else if(c == 'S'){
        v[0] = {i, j};
      }
    }
    //cout << s[i] << endl;
  }

  int dest = 0, res = 0;
  REP(i, 0, N){
    queue<PII> q;
    q.push(v[dest]);
    memset(cost, -1, sizeof(cost));
    cost[v[dest].fst][v[dest].snd] = 0;
    while(!q.empty()){
      PII a = q.front(); q.pop();
      const int dx[4] = {-1, 0, 1, 0};
      const int dy[4] = {0, -1, 0, 1};
      if(s[a.fst][a.snd] == i + '1'){
        res += cost[a.fst][a.snd];
        dest++;
        break;
      }
      REP(i, 0, 4){
        int ny = a.fst + dy[i];
        int nx = a.snd + dx[i];
        if(s[ny][nx] != 'X' && !(cost[ny][nx] + 1)){//cost[ny][nx] + 1 == 0 if not searched
          cost[ny][nx] = cost[a.fst][a.snd] + 1;
          q.push({ny, nx});
        }
      }
    }
  }
  cout << res << endl;

  return 0;
}