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<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/

int H, W, N;
char field[1005][1005];

queue<int> qh[10], qw[10];
int cou[10][1005][1005];

int dh[4] = { -1,0,0,1 };
int dw[4] = { 0,-1,1,0 };
char num[11] = "0123456789";

int serch(int t)
{
	while (qh[t - 1].size() > 0)
	{
		int h = qh[t - 1].front();
		int w = qw[t - 1].front();
		qh[t - 1].pop();
		qw[t - 1].pop();

		for (int i = 0; i < 4; i++)
		{
			int nh = min(max(h + dh[i], 0), H - 1);
			int nw = min(max(w + dw[i], 0), W - 1);
			if (nh == h && nw == w) continue;

			if (field[nh][nw] == num[t])
			{
				qh[t].push(nh);
				qw[t].push(nw);
				return cou[t - 1][h][w] + 1;
			}

			if (field[nh][nw] != 'X' && field[nh][nw] != num[t-1] && cou[t - 1][nh][nw] == 0)
			{
				qh[t - 1].push(nh);
				qw[t - 1].push(nw);
				cou[t - 1][nh][nw] = cou[t - 1][h][w] + 1;
			}
		}
	}

	return 100000000;
}

int main()
{	
	cin >> H >> W >> N;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> field[i][j];
			if (field[i][j] == 'S')
			{
				field[i][j] = '0';
				qh[0].push(i);
				qw[0].push(j);
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		ans += serch(i + 1);
	}

	cout << ans << endl;

	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int INF=0x3f3f;

int sx,sy;
int xy[][2]={{1,0},{-1,0},{0,1},{0,-1}};
char map[1005][1005];
int dis[1005][1005];
int H,W,N;

bool judge(int x,int y)
{
	return 0<=x&&x<H&&0<=y&&y<W&&map[x][y]!='X'&&dis[x][y]==INF;
}

typedef pair<int,int> P;

int bfs(char c)
{
	for(int i=0;i<H;i++)
		fill(dis[i],dis[i]+W,INF);
	dis[sx][sy]=0;
	queue<P>q;
	q.push(P(sx,sy));
	while(!q.empty())
	{
		P p=q.front();
		q.pop();
		if(map[p.first][p.second]==c)
		{
			sx=p.first;
			sy=p.second;
			break;
		}
		for(int i=0;i<4;i++)
		{
			int xx=p.first+xy[i][0];
			int yy=p.second+xy[i][1];
			if(judge(xx,yy))
			{
				q.push(P(xx,yy));
				dis[xx][yy]=dis[p.first][p.second]+1;
			}
		}
	}
	return dis[sx][sy];
}

int main()
{
	cin>>H>>W>>N;
	int ans=0;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='S')
			{
				sx=i;
				sy=j;
			}
		}
	}
	for(int i=1;i<=N;i++)
		ans+=bfs('0'+i);
	cout<<ans<<endl;
	return 0;
}

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

int H, W, N;
vector<string> g;
vector<vector<int>> dist;

void Bfs(int si, int sj, int gi, int gj) {
  queue<int> qi, qj;
  qi.push(si), qj.push(sj);
  dist[si][sj] = 0;

  while (!qi.empty() && !qj.empty()) {
    int i = qi.front(), j = qj.front();
    qi.pop(), qj.pop();

    int di[] = {1, 0, -1, 0}, dj[] = {0, 1, 0, -1};
    for (int a = 0; a < 4; ++a) {
      int ni = i + di[a], nj = j + dj[a];
      if (ni < 0 || H <= ni || nj < 0 || W <= nj)
        continue;
      if (g[ni][nj] == 'X' || dist[ni][nj] != -1)
        continue;

      qi.push(ni), qj.push(nj);
      dist[ni][nj] = dist[i][j] + 1;
    }
  }
}

int main() {
  cin >> H >> W >> N;
  g.resize(H);
  for (int i = 0; i < H; ++i)
    cin >> g[i];

  int pi, pj;
  for (int i = 0; i < H; ++i)
    for (int j = 0; j < W; ++j)
      if (g[i][j] == 'S')
        pi = i, pj = j;

  int ans = 0;
  for (int a = 0; a < N; ++a) {
    dist.resize(H, vector<int>(W, -1));
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (g[i][j] == '1' + a) {
          Bfs(pi, pj, i, j);
          ans += dist[i][j];
          pi = i, pj = j;
        }
      }
    }

    dist.clear();
  }

  cout << ans << endl;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e8;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int n,m,a;
int solve(){
	vector<int>x(a+1);
	vector<int>y(a+1);
	vector<vector<char> >in(n+2,vector<char>(m+2));
	rep(i,n+2)rep(j,m+2){
		if(!i||!j||i==n+1||j==m+1)in[i][j]='X';
		else cin>>in[i][j];
		if(in[i][j]=='S')in[i][j]='0';
		if(isdigit(in[i][j])){
			int d=in[i][j]-'0';
			x[d]=i;y[d]=j;
		}
	}
	int out=0;
	rep(i,a){
		vector<vector<int> >tmp(n+2,vector<int>(m+2));
		vector<int>nx;
		vector<int>ny;
		rep(j,n+2)rep(k,m+2)tmp[j][k]=inf;
		tmp[x[i]][y[i]]=0;
		nx.pb(x[i]);
		ny.pb(y[i]);
		while(nx.size()){
			//rep(j,n+2){rep(k,m+2)cout<<tmp[j][k];cout<<endl;}
			if(nx[0]==x[i+1]&&ny[0]==y[i+1]){out+=tmp[nx[0]][ny[0]];break;}
			rep(j,4){
				if(in[nx[0]+dx[j]][ny[0]+dy[j]]!='X'&&tmp[nx[0]+dx[j]][ny[0]+dy[j]]>tmp[nx[0]][ny[0]]+1){
					tmp[nx[0]+dx[j]][ny[0]+dy[j]]=tmp[nx[0]][ny[0]]+1;
					nx.pb(nx[0]+dx[j]);
					ny.pb(ny[0]+dy[j]);
				}
			}
			nx.erase(nx.begin());
			ny.erase(ny.begin());
		}
	}
	return out;
}
int main(){
	cin>>n>>m>>a;
	cout<<solve()<<endl;
}