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<iomanip>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	ll h, w, n;
	cin>>h>>w>>n;
	vector<string> a(h);
	vector<vector<ll> > dist(h, vector<ll>(w, INF));
	ll time = 0;
	P sp;
	REP(i, h) cin>>a[i];
	bool det = false;
	REP(i, h) {
		REP(j, w) {
			if(a[i][j] == 'S') {
				sp.first = i;
				sp.second = j;
				det = true;
				break;
			}
		}
		if(det) break;
	}
	REP(i, n) {
		queue<P> c;
		c.push(sp);
		dist[sp.first][sp.second] = 0;
		while(true) {
			P cp = c.front();
			c.pop();
			if(a[cp.first][cp.second] - '1' == i) {
				time += dist[cp.first][cp.second];
				sp = cp;
				break;
			}
			REP(j, 4) {
				ll nx = cp.first + dx[j];
				ll ny = cp.second + dy[j];
				if(nx >= 0 && nx < h && ny >= 0 && ny < w && dist[nx][ny] == INF && (a[nx][ny] == 'S' || a[nx][ny] == '.' || (a[nx][ny] >= '1' && a[nx][ny] <= '9'))) {
					c.push(P(nx, ny));
					dist[nx][ny] = dist[cp.first][cp.second] + 1;
				}
			}
		}
		REP(j, h) {
			REP(k, w) {
				dist[j][k] = INF;
			}
		}
	}
	cout<<time<<endl;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef pair<int,int> P;

#define INF 1000001

int bfs(vector<vector<char> >& mp, P now, P dist, int H, int W) {
    int len[H][W];

    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            len[i][j]=INF;
        }
    }

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

    len[now.first][now.second]=0;
    queue<P> que;
    que.push(now);

    while(!que.empty()) {
        P p=que.front(); que.pop();

        if(p==dist) break;

        for(int i=0; i<4; ++i) {
            int ni=p.first+dy[i];
            int nj=p.second+dx[i];

            if(ni>=0 && ni<H && nj>=0 && nj<W && len[ni][nj]==INF && mp[ni][nj]!='X') {
                len[ni][nj]=len[p.first][p.second]+1;
                que.push(P(ni,nj));
            }
        }
    }

    return len[dist.first][dist.second];
}

int main()
{
    int H,W,N;
    int ans=0;

    cin >> H >> W >> N;

    P pos[N]; // first=H, second=W
    vector<vector<char> > mp; // mp[H][W]

    mp.resize(H+2);

    for(int i=0; i<H; ++i) {
        string instr;
        cin >> instr;
        for(int j=0; j<W; ++j) {
            mp[i].push_back(instr[j]);
            if(instr[j]>='0' && instr[j]<='9') pos[instr[j]-'0']=make_pair(i,j);
            if(instr[j]=='S') pos[0]=make_pair(i,j);
        }
    }

    for(int i=0; i<N; ++i) {
        ans+=bfs(mp,pos[i],pos[i+1],H,W);
    }

    cout << ans << endl;

    return 0;
}

C++: #include <iostream>
#include <queue>
#include <climits>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

typedef pair<int,int> pii;

int main()
{
  int H, W, N;
  const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
  cin >> H >> W >> N;
  char map[H][W];
  int d[H][W], hp = 1;
  fill(d[0],d[H],INT_MAX);
  queue<pii> q;
  REP(i,H){
    REP(j,W){
      cin >> map[i][j];
      if(map[i][j] == 'S'){
        q.push({i,j});
        d[i][j] = 0;
      }
    }
  }
  while(!q.empty()){
    pii p = q.front();
    q.pop();
    if(map[p.first][p.second] >= '1' && map[p.first][p.second] <= '9' && hp == map[p.first][p.second]-'0') hp++;
    if(hp == N+1){
      cout << d[p.first][p.second] << endl;
      return 0;
    }
    REP(i,4){
      pii next_p = {p.first+dx[i],p.second+dy[i]};
      if(next_p.first < 0 || next_p.first >= H || next_p.second < 0 || next_p.second >= W || map[next_p.first][next_p.second] == 'X') continue;
      if(d[next_p.first][next_p.second] > d[p.first][p.second]+1){
        d[next_p.first][next_p.second] = d[p.first][p.second]+1;
        q.push(next_p);
      }
    }
  }
}

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};
int h, w, n;
vector<string> s;

int bfs(pii st, pii g){
	vector<vector<int> > v(h, vi(w, 0));
	queue<pair<pii, int> > q;
	pair<pii, int> p(st, 0);
	q.push(p);
	while(!q.empty()){
		p=q.front();
		q.pop();
		if(g == p.fi){
			return p.se;
		}
		for(int i = 0; i < 4; i++){
			int y = p.fi.fi+dy[i], x = p.fi.se+dx[i];
			if(y < 0 || y >= h || x < 0 || x >= w ||s[y][x]=='X') continue;
			q.push(pair<pii,int>(pii(y, x), p.se+1));
		}
	}
	return -1;
}

int main(){
	cin>>h>>w>>n;
	s = vector<string>(h);
	rep(i, h) cin>>s[i];
	vector<pii> p(n+1);
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(s[i][j]=='S'){
				p[0] = pii(i, j);
			}
			else if(s[i][j]>='1'&&s[i][j]<='9'){
				p[s[i][j]-'0'] = pii(i, j);
			}
		}
	}
	
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans += bfs(p[i], p[i+1]);
	}
	cout<<ans<<endl;
}