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 <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int h,w,n;
char data[1100][1100];
int tesu[1100][1100];
int chx[10];
int chy[10];

bool inrange(int x,int y){
	if(x<0||y<0||x>h-1||y>w-1) return false;
	else return true;
}
queue<int> qx;
queue<int> qy;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int bfs(int chnum){
	while(!qx.empty()){
		int sx = qx.front();
		int sy = qy.front();
		qx.pop(); qy.pop();
		REP(i,4){
			int nx = sx + dx[i];
			int ny = sy + dy[i];
			if(!inrange(nx,ny)) continue;
			if(data[nx][ny]!='X'){
				if(tesu[nx][ny]==-1||tesu[nx][ny]>tesu[sx][sy]+1){
					tesu[nx][ny] = tesu[sx][sy]+1;
					qx.push(nx);
					qy.push(ny);
				}
				if(data[nx][ny]==(chnum+'0')){
					return tesu[nx][ny];
				}
			}
		}
	}
	return -1;
}

int main(){
	cin >> h >> w >> n;
	REP(i,h){
		string tmp;
		cin >> tmp;
		REP(j,tmp.size()) {
			data[i][j] = tmp[j];
			if(data[i][j] == 'S'){
				chx[0] = i;
				chy[0] = j;
			}
			if('1'<=data[i][j]&&data[i][j]<='9'){
				chx[data[i][j]-'0'] = i;
				chy[data[i][j]-'0'] = j;
			}
		}
	}
	ll int ans = 0;
	FOR(i,0,n){
		REP(j,1100) REP(k,1100) tesu[j][k] = -1;
		qx.push(chx[i]);
		qy.push(chy[i]);
		tesu[chx[i]][chy[i]] = 0;
		ans += bfs(i+1);
		while(!qx.empty()) qx.pop();
		while(!qy.empty()) qy.pop();
	}
	/*FOR(i,0,n+1){
		cout << chx[i] << " " << chy[i] << endl;
	}
	REP(i,h){
		REP(j,w) cout << tesu[i][j] << " ";
		cout << endl;
	}*/
	cout << ans << endl;
}

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

#define mp make_pair
#define f first
#define s second

using namespace std;

typedef pair<int,int> P;

const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int h,w;
string grid[1000];
int d[1000][1000];

void bfs(P S){

  queue<P>que;
  que.push(S);
  d[S.f][S.s]=0;

  while(!que.empty()){
    P now=que.front();
    
    que.pop();
    for(int i=0;i<4;i++){
      if(0<=now.f+dx[i] && 0<=now.s+dy[i] &&
	 now.f+dx[i]<h && now.s+dy[i]<w
	 && grid[now.f+dx[i]][now.s+dy[i]]!='X'){

	if(d[now.f][now.s]+1<d[now.f+dx[i]][now.s+dy[i]]){
	  d[now.f+dx[i]][now.s+dy[i]]=d[now.f][now.s]+1;
	  que.push(P(now.f+dx[i],now.s+dy[i]));
	}
      }
    }
  }
}

int main(void){
  int n;
  P v[1001];

  cin >> h >> w >> n;

  for(int i=0;i<h;i++)cin >> grid[i];

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(grid[i][j]=='S')v[0]=mp(i,j);
      if(grid[i][j]!='X'&&grid[i][j]!='.')
	v[grid[i][j]-'0']=mp(i,j);
    }
  }

  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<h;j++)
      for(int k=0;k<w;k++)d[j][k]=100000000;
    bfs(v[i]);
    ans+=d[v[i+1].f][v[i+1].s];
  }

  cout << ans << endl;

  return 0;
}

C++: #include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <array>
#include <stack>
#include <queue>
#include <chrono>
#include <numeric>

#pragma warning(disable:4996)
#define REP(i,n) for(int i = 0 ; i < n ; ++i)
typedef long long Int;

using namespace std;

struct point{
	Int j, i,step;
	point(Int i_, Int j_,Int s) :i(i_), j(j_),step(s){}
};

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

queue<point> que;
char tile[1001][1001];
int H, W;
bool ed[1001][1001];

point solve(char target)
{
	while (!que.empty()){
		point now(que.front());
		//ed[now.i][now.j] = true;
		que.pop();
		REP(i, 4){
			int x = now.j + dx[i];
			int y = now.i + dy[i];

			if (x < 0 || y < 0 || x > W || y > H || ed[y][x])
				continue;

			if (tile[y][x] == target){
				return point(y, x,now.step+1);
			}

			if (tile[y][x] != 'X'){
				que.push(point(y, x, now.step + 1));
				ed[y][x] = true;
			}
		}
	}
}

int main()
{
	cin.tie(0); ios::sync_with_stdio(false);
	//fstream fs("input.txt");
	////////////ここから開始///////////
	int n(0);
	cin >> H >> W >> n;

	REP(i, 1001)REP(j, 1001){ tile[i][j] = 'X'; ed[i][j] = false; }

	REP(i, H)REP(j, W)cin >> tile[i][j];

	REP(i, H)REP(j, W){ if (tile[i][j] == 'S')que.emplace(i, j, 0); }

	for (int i = 0; i < n; ++i){
		REP(i_1, H + 1)REP(j_1, W + 1){ ed[i_1][j_1] = false; }
		point t = solve('1' + i);
		que = {};
		que.emplace(t);
	}

	cout << que.front().step << endl;

	return 0;
}

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

using namespace std;

#define MAX 1001
const char INF = '#';
const int MM = 10000000;
typedef pair<int,int> P;
 
int num,d[MAX][MAX],n,m;
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
char field[MAX+1][MAX+1];
 
int bfs(int sy,int sx,int gy,int gx){
    queue<P> que;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            d[i][j] = MM;
	}
    }
     
    que.push(P(sy,sx));
    d[sy][sx] = 0;
     
    while(que.size()){
        P p = que.front(); que.pop();
        if(p.first == gy && p.second == gx) break;
         
        for(int i = 0 ; i < 4 ; i++){
            int nx = p.first+dx[i];
            int ny = p.second+dy[i];
             
            if(0 <= nx && nx < n && 0 <= ny && ny < m && field[nx][ny] != 'X'
               &&d[nx][ny] == MM){
                que.push(P(nx,ny));
                d[nx][ny] = d[p.first][p.second]+1;
            }
        }
    }
     
    return d[gy][gx];
}
 
int main(){
    fill(field[0],field[MAX],INF);
 
    cin >> n >> m >> num;
    vector<P> v(num+1);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> field[i][j];
            if(field[i][j]=='S'){
                v[0].first = i;
                v[0].second = j;
            }
            if('0' <= field[i][j] && field[i][j] <= '9'){
                v[field[i][j]-'0'].first = i;
                v[field[i][j]-'0'].second = j;
            }
        }
    }
 
    int ans = 0;
    for(int i = 1 ; i < num+1 ; i++){
        ans += bfs(v[i-1].first,v[i-1].second,v[i].first,v[i].second);
    }
    cout << ans << endl;
 
    return 0;
}