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 <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1e9;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={0, 1, 0, -1}, dy[4]={-1, 0, 1, 0};
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

/* struct P {
	int x, y, n;
	P(int n, int x, int y):n(n), x(x), y(y){}
	P(){}
}; */


/** Problem0558 : Cheese **/
int main()
{
	int H, W, N; cin>>H>>W>>N;
	char field[1000][1000];
	int sx, sy;
	rep(i, H) {
		rep(j, W) {
			cin>>field[j][i];
			if (field[j][i] == 'S') {
				sx = j, sy = i;
			}
		}
	}
	
	int ans=0;
	for (int i=0; i<N; i++) {
		queue<P> Q;
		int vis[1000][1000] = {0};
		Q.push(P(sx, sy));
		vis[sx][sy] = 0;
		
		while (Q.size()) {
			P p = Q.front(); Q.pop();
			if (field[p.first][p.second] == i+1+'0') {
				ans += vis[p.first][p.second];
				sx = p.first, sy = p.second;
				break;
			}
			
			for (int i=0; i<4; i++ ) {
				int nx = p.first+dx[i], ny = p.second+dy[i];
				if_range(nx, ny, W, H) {
					if (vis[nx][ny] == 0 && field[nx][ny]!='X') {
						vis[nx][ny] = vis[p.first][p.second]+1;
						Q.push(P(nx, ny));
					}
				}
			}
		}
	}
	
	cout << ans << endl;
}

C++: #include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 1000;
const int MAX_M = 1000;
const int MAX_T = 9;
const int INF = 100000000;
int n, m, t;
int sx, sy;
int ans = 0;
char field[MAX_N][MAX_M];
int d[MAX_N][MAX_M];
P factory[MAX_T];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

//从当前起点&#24320;始，&#23547;找第num个&#22902;酪 
int bfs(int x, int y, int num){
	int gx = factory[num].first;
	int gy = factory[num].second;
	queue<P> que;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			d[i][j] = INF;
		}
	}
	d[x][y] = 0;
	que.push(P(x,y));
	
	while(que.size()){
		P p = que.front();
		que.pop();
		int x = p.first;
		int y = p.second;
		if(x == gx && y == gy){
			break;
		}
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m && field[nx][ny] != 'X' && d[nx][ny] == INF){
				d[nx][ny] = d[x][y] + 1;
				que.push(P(nx, ny));
			}
		}
	}
	
	return d[gx][gy];
}

void solve(){
	cin >> n >> m >> t;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> field[i][j];
			if(field[i][j] == 'S'){
				factory[0] = P(i, j);
			}
			if(field[i][j] >= '1' && field[i][j] <= '9'){
				int index = field[i][j] - '0';
				factory[index] = P(i, j);
			}
		}
	}

	int ans = 0;
	
	for(int i = 0; i < t; i++){
		int x = factory[i].first;
		int y = factory[i].second;
		ans += bfs(x, y, i + 1);
	}
	cout << ans;
}

int main(){
	solve();
}

C++: #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int const MAXN=1001;
int const INF=2<<29;
typedef pair<int,int> P;
int h,w;
int sx,sy;
int res=0;
char maze[MAXN][MAXN]={0};
int d[MAXN][MAXN]={0};
int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

void bfs(int n)
{
	queue<P> q;
	q.push(P(sx,sy));
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			d[i][j]=INF;
	d[sx][sy]=0;
	while(q.size())
	{
		P p=q.front();
		q.pop();
		if(maze[p.first][p.second]=='0'+n)
		{
			res+=d[p.first][p.second];
			sx=p.first;
			sy=p.second;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int tx=p.first+next[i][0];
			int ty=p.second+next[i][1];
			if(maze[tx][ty]&&maze[tx][ty]!='X'&&d[tx][ty]==INF)
			{
				d[tx][ty]=d[p.first][p.second]+1;
				q.push(P(tx,ty));
			}
		}
	}		
}

int main()
{
	int n;
	cin>>h>>w>>n;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
		{
			cin>>maze[i][j];
			if(maze[i][j]=='S')
				sx=i,sy=j;
		}
	for(int i=1;i<=n;i++)
		bfs(i);
	cout<<res<<endl;
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int xs[10],ys[10];
int H,W,N;
string S[1002];
int main()
{
	scanf("%d%d%d",&H,&W,&N);
	for(int i=0;i<W+2;i++){
		S[0]+='X';
		S[H+1]+='X';
	}
	for(int i=1;i<=H;i++){
		string x;
		cin >> x;
		S[i]+='X'+x+'X';
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(S[i][j]!='X'&&S[i][j]!='.'){
				if(S[i][j]=='S'){
					xs[0]=j;
					ys[0]=i;
				}
				else{
					xs[S[i][j]-'0']=j;
					ys[S[i][j]-'0']=i;
				}
			}
		}
	}
	int XX[1002][1002];
	int ans=0;
	vector<pair<int,int> >vec1;
	vector<pair<int,int> >vec2;
	int dx[4]={-1,0,0,1};
	int dy[4]={0,-1,1,0};
	for(int x=0;x<N;x++){
		vec1.clear();
		vec2.clear();
		for(int i=0;i<H+2;i++)for(int j=0;j<W+2;j++)XX[i][j]=-1;
		int cou=0;
		XX[ys[x]][xs[x]]=cou;
		vec1.push_back(make_pair(ys[x],xs[x]));
		while(XX[ys[x+1]][xs[x+1]]==-1){
			vec2.clear();
			for(int i=0;i<vec1.size();i++){
				for(int j=0;j<4;j++){
					if(S[vec1[i].first+dy[j]][vec1[i].second+dx[j]]=='X')continue;
					if(XX[vec1[i].first+dy[j]][vec1[i].second+dx[j]]!=-1)continue;
					vec2.push_back(make_pair(vec1[i].first+dy[j],vec1[i].second+dx[j]));
				}
			}
			vec1.clear();
			for(int i=0;i<vec2.size();i++)vec1.push_back(vec2[i]);
			cou++;
			for(int i=0;i<vec1.size();i++){
				XX[vec1[i].first][vec1[i].second]=cou;
			}
		}
		ans+=XX[ys[x+1]][xs[x+1]];
		printf("%d\n",ans);
	}
	printf("%d\n",ans);
	return 0;
}