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<string.h>
#include<queue>
using namespace std;

bool flag[1005][1005];
int temp[1005][1005];
char map[1005][1005],ch[1005];
int n,m,xy[10][2],sum;
char tt[10]={'1','2','3','4','5','6','7','8','9','10',},t;
void initflag(){
	for(int i=0;i<1005;i++){
		memset(flag[i],true,sizeof(flag[i]));
	}
}
void initmap(){
	for(int i=0;i<1005;i++){
		memset(map[i],'X',sizeof(map[i]));
	}	
}
int main(){
	int i,j,k,x,y;
	while(~scanf("%d%d%d",&n,&m,&k)){
		initmap();
		for(i=1;i<=n;i++){
			scanf("%s",ch);
			for(j=1;j<=m;j++){
				map[i][j]=ch[j-1];
				if(map[i][j]=='S'){
					xy[0][0]=i;
					xy[0][1]=j;
				}
				if(map[i][j]>='1'&&map[i][j]<='9'){
					xy[map[i][j]-'0'][0]=i;
					xy[map[i][j]-'0'][1]=j;
				}
			}
			
		}
		/*
		for(i=0;i<=n+1;i++){
			for(j=0;j<=m+1;j++)
			printf("%c",map[i][j]);
			printf("\n");
		}
		for(i=0;i<=n+1;i++){
			for(j=0;j<=m+1;j++)
			printf("%d",flag[i][j]);
			printf("\n");
		}
		for(i=0;i<10;i++){
			printf("%c %d %d\n",tt[i],xy[i][0],xy[i][1]);
		}
		*/
		
		sum=0;
		for(i=0;i<k;i++){
			initflag();                 //初始 flag	 
			x=xy[i][0];y=xy[i][1];		//起点坐?	 
			queue<int> q;				// ?? 
			q.push(x*10000+y);
			flag[x][y]=false;				//?? 
			temp[x][y]=0;				//?数 
			t=tt[i];					//目? 
				
			//printf("i=%d x=%d y=%d q=%d t=%c\n" ,i,x,y,q.front(),t);
			while(!q.empty()){
				x=q.front()/10000;y=q.front()%10000;
				if(flag[x+1][y]&&map[x+1][y]!='X'){
					q.push((x+1)*10000+y);
					flag[x+1][y]=false;
					temp[x+1][y]=temp[x][y]+1;
				}
				if(map[x+1][y]==t){sum+=temp[x+1][y];break;}
				
				if(flag[x-1][y]&&map[x-1][y]!='X'){
					q.push((x-1)*10000+y);
					flag[x-1][y]=false;
					temp[x-1][y]=temp[x][y]+1;
				}
				if(map[x-1][y]==t){sum+=temp[x-1][y];break;}
				if(flag[x][y+1]&&map[x][y+1]!='X'){
					q.push(x*10000+y+1);
					flag[x][y+1]=false;
					temp[x][y+1]=temp[x][y]+1;
					
				}
				if(map[x][y+1]==t){sum+=temp[x][y+1];break;}
				if(flag[x][y-1]&&map[x][y-1]!='X'){
					q.push(x*10000+y-1);
					flag[x][y-1]=false;
					temp[x][y-1]=temp[x][y]+1;
				}
				if(map[x][y-1]==t){sum+=temp[x][y-1];break;}
				q.pop();
			}
		}
		printf("%d\n",sum);
		
	}
	return 0;
}

C++: /************************************************
* Author        :somniloquy
* Created Time  :2015/10/30 16:15:09
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int hw_max = 1000 + 5;
char graph[hw_max][hw_max];
int sign[hw_max][hw_max];
int h, w, n, ans;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct node
{
	int x;
	int y;
	int time;
} start;

void BFS(node op, char ed)
{
	queue <node> process;
	process.push(op);
	sign[op.x][op.y] = 1;
	while(!process.empty())
	{
		node now = process.front();
		process.pop();
		for(int i = 0; i < 4; i ++)
		{
			node next = now;
			next.x += dx[i];
			next.y += dy[i];
			next.time ++;
			if(next.x >= 0 && next.x < h && next.y >= 0 && next.y < w && graph[next.x][next.y] != 'X' && !sign[next.x][next.y])
			{
				if(graph[next.x][next.y] == ed)
				{
					ans += next.time;
					next.time = 0;
					start = next;
				       	return;
				}
				else
				{
					process.push(next);
					sign[next.x][next.y] = 1;
				}
			}
		}
	}
}

int main()
{
	while(~scanf("%d %d %d", & h, & w, & n))
	{
		getchar();
		for(int i = 0; i < h; i ++)
		{
			for(int j = 0; j < w; j ++)
			{
			       scanf("%c", & graph[i][j]);
			       if(graph[i][j] == 'S')
			       {
					start.x = i;
					start.y = j;
					start.time = 0;
			       }
			}
			getchar();
		}
		ans = 0;
		for(int i = 1; i <= n; i ++)
		{
			memset(sign, 0, sizeof(sign));
			BFS(start, '0' + i);
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;
int w ,h ,cheese;
char Map[1010][1010];
int dis[1010][1010];
typedef pair<int,int> p ;
p pos[11];
int sx , sy;
int INF= 1<<30;
int move[4][2] = {1,0,-1,0,0,-1,0,1};
int BFS(int x, int y ,int ax ,int ay)
{
	dis[x][y]= 0;
	if (x==ax && y ==ay) return 0 ;
	queue<p> que;
	que.push(make_pair(x ,y));
	
	while (!que.empty())
	{
		p f = que.front();que.pop();
		int X =f.first;
		int Y =f.second;
		
		for (int dir=0;dir<4;dir++)
		{
			int X1 = X+move[dir][0];
			int Y1 = Y+move[dir][1];
			if (X1 <1 || X1>h || Y1<1 || Y1 >w || Map[X1][Y1]=='X' || dis[X1][Y1]!=INF ) continue;
			if(X1==ax && Y1==ay ) return dis[X][Y]+1;
			dis[X1][Y1]= dis[X][Y]+1;
			que.push(make_pair(X1,Y1));
		}
	}
}

int main ()
{
	cin >> h >>w >>cheese ;
	for (int i=1;i<=h ;i++)
		for (int j=1;j<=w;j++)
		{
			cin >>Map[i][j];
			if (Map[i][j]=='S')
				{
					sx = i ;
					sy = j;
				}
			else if (Map[i][j] >='1' && Map[i][j]<='9')
				{
					pos[Map[i][j]-'0'] = make_pair(i,j);
				}
		}
	int stept= 0 ;
	for (int i=1;i<=cheese ;i++)
		{
			fill (dis[0],dis[0]+1020100,INF);
			stept += BFS(sx ,sy, pos[i].first,pos[i].second);
			sx = pos[i].first;
			sy = pos[i].second;
		}
	cout <<stept<<endl;
	return 0;
}