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<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
struct  node
{
	int x;
	int y;
	int step;
}cur,nxt;
int v[1010][1010];
int x[1010];
int y[1010];
int f[1010][1010];
int n,m,s1=0,s=0,t=1,ans=0;
int bfs(int a1,int b1)
{	
	memset(v,0,sizeof(v));
	cur.x=x[a1];
	cur.y=y[a1]; 
	cur.step=0;
	v[cur.x][cur.y]=1;
	queue<node> q;
	q.push(cur);
	while(!q.empty())
	{
		cur=q.front();
		q.pop();
		if (cur.x==x[b1]&&cur.y==y[b1])
		{
			return cur.step;
		}
		for (int i=0;i<4;i++)
			{
				nxt.x=cur.x+dx[i];
				nxt.y=cur.y+dy[i];
				if (nxt.x>=0&&nxt.y>=0&&nxt.x<n&&nxt.y<m&&v[nxt.x][nxt.y]==0&&f[nxt.x][nxt.y]==0)
				{	
					nxt.step=cur.step+1;
					q.push(nxt);
					v[nxt.x][nxt.y]=1;
				}
			}
		
	}
}
int main()
{
	memset(f,0,sizeof(f));
	cin>>n>>m>>s;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			char c;
			cin>>c;
			if (c=='S')
			{
				x[0]=i;
				y[0]=j;
				cur.step=0;
				f[i][j]=1;
			}
			if (c=='.')
			{
				f[i][j]=0;
			}
			if (c=='X')
			{
				f[i][j]=1;
			}
			if (c>=49&&c<=57)
			{
				f[i][j]=0;
				x[c-48]=i;
				y[c-48]=j;
			}
		}
	ans=bfs(0,1);
	for (int i=2;i<=s;i++)
	{
		ans=ans+bfs(i-1,i);
	}
	cout<<ans<<endl;
	return 0;
}

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

struct ge
{
	int x;
	int y;
};

int h,w,n,sx,sy,ex,ey,ans;
int a[1010][1010];
int b[1010][1010];
int xx[]={-1,1,0,0};
int yy[]={0,0,-1,1};
int x[11];            //奶酪厂的横坐标数组 
int y[11];            //奶酪厂的纵坐标数组 

int main()
{
	cin>>h>>w>>n;
	memset(a,0,sizeof(a));
	queue<ge> q;
	bool flag = false;
	ans = 0;
	for(int i = 1;i <= h;i++)
	{
		for(int j = 1;j <= w;j++)
		{
			char c;
			cin>>c;
			if(c == 'S')
			{
				a[i][j] = 1;
				x[0] = i;y[0] = j;
			}
			else if(c >= '1'&&c <= '9')
			{
				a[i][j] = 1;
				x[c-'0'] = i;
				y[c-'0'] = j;
			}
			else if(c == '.')
			{
				a[i][j] = 1;
			}
			else
			    ;
		}
	}
	for(int i = 1;i <= n;i++)
	{
		flag = false;
		memset(b,-1,sizeof(b));
		while(!q.empty())
		{
			q.pop();
		}
		sx = x[i-1];sy = y[i-1];
		b[sx][sy] = 0;
		ex = x[i];ey = y[i];
		ge g;
		g.x = sx;g.y = sy;
		q.push(g); 
		while(!q.empty()&&flag == false)
		{
			ge now = q.front();
			q.pop();
			for(int i = 0;i < 4;i++)
			{
				int dx,dy;
				dx = now.x + xx[i];
				dy = now.y + yy[i];
				if(dx >= 1&&dx <= h&&dy >= 1&&dy <= w&&a[dx][dy] == 1)  //可以通过 
				{
					if(b[dx][dy] != -1)     //已经访问过 
					{
						continue;
					}
					else
					{
						b[dx][dy] = b[now.x][now.y] + 1;
						if(dx == ex&&dy == ey)
						{
							flag = true;
							ans = ans + b[dx][dy];
							break;
						}
						else
						{
							g.x = dx;g.y = dy;
							q.push(g); 
						}
					}
				}
			}
		}
		
	}
	cout<<ans<<endl;
	return 0;
}

C++: #pragma once

#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
string S[1001];
long result=0;
int H,W,N;
long minmytime[1000][1000];
queue<int> qx,qy,mytime;
int sx,sy,gx,gy;
int step = 0;

int main(){
	scanf("%d%d%d",&H,&W,&N);

	for(int i=0;i<H;i++){
		cin>>S[i];
		for(int j=0;j<W;j++){
			minmytime[i][j]=1000000;
			if(S[i][j]=='S'){
				sx=j;
				sy=i;
				qx.push(j);
				qy.push(i);
				mytime.push(0);
			}

			if(S[i][j]-'0'==N){
				gx=j;
				gy=i;
			}

		}
	}



for(int acc=0;acc<N;acc++){
	step++;
	while(step<=N){
		
		if(qx.front()>0){
		if(mytime.front()<minmytime[qy.front()][qx.front()-1]-1  && S[qy.front()][qx.front()-1] !='X'){
			if(S[qy.front()][qx.front()-1]-'0' ==step){
			result += mytime.front()+1;
			sx=qx.front()-1;
			sy=qy.front();
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				mytime.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			mytime.push(0);
			break;
		}
				qx.push(qx.front()-1);
				qy.push(qy.front());
				mytime.push(mytime.front()+1);
				minmytime[qy.front()][qx.front()-1]=mytime.front()+1;
		}

	}
		//

	if( qx.front()<W-1 ){
		if(mytime.front()<minmytime[qy.front()][qx.front()+1]-1 && S[qy.front()][qx.front()+1] !='X'){

		if(S[qy.front()][qx.front()+1]-'0' ==step){
			result += mytime.front()+1;
			sx=qx.front()+1;
			sy=qy.front();
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				mytime.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			mytime.push(0);
			break;
		}

				qx.push(qx.front()+1);
				qy.push(qy.front());
				mytime.push(mytime.front()+1);
				minmytime[qy.front()][qx.front()+1]=mytime.front()+1;
		}
	}

		//

	if( qy.front()>0){
		if(mytime.front()<minmytime[qy.front()-1][qx.front()]-1  && S[qy.front()-1][qx.front()] !='X'){

			if(S[qy.front()-1][qx.front()]-'0' ==step){
			result += mytime.front()+1;
			sx=qx.front();
			sy=qy.front()-1;
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				mytime.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			mytime.push(0);
			break;
		}

				qx.push(qx.front());
				qy.push(qy.front()-1);
				mytime.push(mytime.front()+1);
				minmytime[qy.front()-1][qx.front()]=mytime.front()+1;
		}
	}

		//

	if(qy.front()<H-1){
		if(mytime.front()<minmytime[qy.front()+1][qx.front()]-1  && S[qy.front()+1][qx.front()] !='X'){

				if(S[qy.front()+1][qx.front()]-'0' ==step){
			result += mytime.front()+1;
			sx=qx.front();
			sy=qy.front()+1;
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				mytime.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			mytime.push(0);
			break;
		}

				qx.push(qx.front());
				qy.push(qy.front()+1);
				mytime.push(mytime.front()+1);
				minmytime[qy.front()+1][qx.front()]=mytime.front()+1;
		}
	}


		qx.pop();
		qy.pop();
		mytime.pop();
	



	}

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

}

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

}