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>
//#include <iostream>
//#include <queue>
using namespace std;

typedef pair<int, int> P;

static const int MAX_H = 1000;
static const int MAX_W = 1000;
static const int MAX_N = 9;

int H, W, N;
int gh = -1, gw = -1;
char grid[MAX_H][MAX_W + 1];
int count[MAX_H][MAX_W];
P factory[MAX_N + 1];

//#define OCTAS
#ifdef OCTAS
static const int dh[] = {-1, -1, -1, 0, 0, +1, +1, +1};
static const int dw[] = {-1, 0, +1, -1, +1, -1, 0, +1};
#else
static const int dh[] = {-1, 0, 0, +1};
static const int dw[] = {0, -1, +1, 0};
#endif

// CAUTION!!!
// Call init_count() first!!!
//
void init_count() {
  fill_n(::count[0], MAX_H * MAX_W, -1);
}

int bfs(int h, int w) {
  queue<P> que;
  ::count[h][w] = 0;
  que.push(P(h, w));

  while (!que.empty()) {
    P p = que.front();
    que.pop();
    int cnt = ::count[p.first][p.second];
    if (p.first == gh && p.second == gw) {
      return cnt;
    }
    ++cnt;
    for (int i = 0; i < sizeof(dh) / sizeof(int); ++i) {
      int nh = p.first + dh[i];
      int nw = p.second + dw[i];
      if (nh < 0 || nh >= H ||
          nw < 0 || nw >= W ||
          ::count[nh][nw] >= 0 ||
          grid[nh][nw] == 'X')
        continue;
      ::count[nh][nw] = cnt;
      que.push(P(nh, nw));
    }
  }

  return -1;
}

int main() {
  scanf("%d%d%d", &H, &W, &N);
  for (int h = 0; h < H; ++h) {
    scanf("%s", &grid[h][0]);
    for (int w{}; w < W; ++w) {
      if (grid[h][w] == 'S') {
        factory[0].first = h;
        factory[0].second = w;
      } else if ('1' <= grid[h][w] && grid[h][w] <= '9') {
        int i = grid[h][w] & 0xF;
        factory[i].first = h;
        factory[i].second = w;
      }
    }
  }

  int total{};
  for (int i{1}; i <= N; ++i) {
    init_count();
    gh = factory[i].first;
    gw = factory[i].second;
    total += bfs(factory[i-1].first, factory[i-1].second);
  }

  printf("%d\n", total);
  return 0;
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    bool isVisited[MAX][MAX];
    int d[MAX][MAX];
    int ans=0;
    int sx[9];
    int sy[9];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                sx[0]=i;
                sy[0]=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                sx[in-'0']=i;
                sy[in-'0']=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                isVisited[i][j]=false;
                d[i][j]=INF;
            }
        }
        que.push(P(sx[k],sy[k]));
        d[sx[k]][sy[k]]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==P(sx[k+1],sy[k+1]))   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.second+dy[l];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]==INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[start[k+1].first][start[k+1].second];
    }
    
    cout<<ans<<endl;
    
    return 0;
}

C++: #include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second
 
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


const int INF=1e9;

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

struct mouse{
	int y, x, eat, time;
	mouse(){};
	mouse(int y,int x, int eat, int time):y(y),x(x),eat(eat), time(time){};
};

int main(){
	int h, w, n;
	cin>>h>>w>>n;
	vector<string> s(h);
	rep(i, h) cin>>s[i];
	pii p;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(s[i][j]=='S'){
				p = pii(i, j);
			}
		}
		//cout<<s[i]<<endl;
	}
	vector<vector<vector<int> > > v(11, vii(h, vi(w, 0)));
	queue<mouse> q;
	int eat = 0, cnt = 0;
	q.push(mouse(p.fi,p.se,eat, cnt));
	mouse m;
	while(!q.empty()){
		m=q.front();
		q.pop();
		v[m.eat][m.y][m.x]=1;
		if(m.eat==n) break;
		//cout<<"("<<m.y<<", "<<m.x<<", "<<m.eat<<", "<<m.time<<")"<<endl;
		for(int i = 0; i < 4; i++){
			int x = m.x+dx[i], y = m.y+dy[i];
			if(x < 0 || x >= w || y < 0 || y >= h || v[m.eat][y][x]) continue;
			if(s[y][x]=='.'){
				q.push(mouse(y, x, m.eat, m.time+1));
			}
			else if(s[y][x]=='X'){

			}else{
				if(s[y][x]-'1'==m.eat){
					q.push(mouse(y, x, m.eat+1, m.time+1));
				}
				else{
					q.push(mouse(y, x, m.eat, m.time+1));
				}
			}
		}
	}
	cout<<m.time<<endl;
}