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 <cstdio>
#include <vector>
#include <ctype.h>

const int MAX_SIZE = 1000;
char field[MAX_SIZE + 1][MAX_SIZE + 1];

const int STEP_NUM = 4;
const int STEP[STEP_NUM][STEP_NUM] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

using Position = std::pair<int,int>;

const int MAXN = 10;
Position locations[MAXN];
 
int H, W, N;

int get_shortest_distance(Position &start, Position &goal)
{
	bool is_visit[MAX_SIZE + 1][MAX_SIZE + 1]={};
	is_visit[start.first][start.second]=true;

	std::vector<Position> frontier(1,start);
	for(int step=0;step<W*H;step++)
	{
		std::vector<Position> next_frontier;
		for(auto p:frontier)
			for(int i=0;i<STEP_NUM;i++)
			{
				int nx = p.first+STEP[i][0];
				int ny = p.second+STEP[i][1];
				if(nx==goal.first && ny==goal.second)	return step+1;
				if(nx<0 || H<=nx) 		continue;
				if(ny<0 || W<=ny) 		continue;
				if(field[nx][ny]=='X') 	continue;
				if(is_visit[nx][ny]) 	continue;
				next_frontier.push_back(std::make_pair(nx,ny));
				is_visit[nx][ny] = true;
			}
		frontier = next_frontier;
	}
	return -1;
}

int solve()
{
	int total_step = 0;
	for(int i=1;i<N+1;i++)
		total_step += get_shortest_distance(locations[i-1],locations[i]);
	return total_step;
}

int main()
{
	scanf("%d %d %d", &H, &W, &N);
	for(int i=0; i<H; i++)
		scanf("%s", field[i]);
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
		{
			if(field[i][j]=='S')
				locations[0] = std::make_pair(i,j);
			if(isdigit(field[i][j]))
				locations[field[i][j]-'0'] = std::make_pair(i,j);
		}
	printf("%d\n", solve());
	return 0;
}

C++: #include <cstdio>
#include <map>
#include <queue>

using namespace std;

int h, w, n;

char field[1010][1010];

using pos = pair<int, int>;

pos pass[10];

int distance(pos start, pos goal) {
    bool visited[1010][1010];
    for (int i = 0; i < 1010; i++) {
        for (int j = 0; j < 1010; j++) {
            visited[i][j] = false;
        }
    }
    queue<pair<int, pos>> q;
    q.push(make_pair(0, start));

    while (!q.empty()) {
        auto s = q.front();
        q.pop();
        if (s.second.first < 0 || s.second.second < 0) { continue; }
        if (field[s.second.first][s.second.second] == 'X') { continue; }
        if (visited[s.second.first][s.second.second]) { continue; }
        if (s.second == goal) {
            return s.first;
        }
        visited[s.second.first][s.second.second] = true;
        q.push(make_pair(s.first + 1, make_pair(s.second.first, s.second.second + 1)));
        q.push(make_pair(s.first + 1, make_pair(s.second.first, s.second.second - 1)));
        q.push(make_pair(s.first + 1, make_pair(s.second.first + 1, s.second.second)));
        q.push(make_pair(s.first + 1, make_pair(s.second.first - 1, s.second.second)));
    }
}

int main() {
    scanf("%d", &h);
    scanf("%d", &w);
    scanf("%d", &n);
    for (int i = 0; i < h; i++) {
        scanf("%s", field[i]);
        for (int j = 0; j < w; j++) {
            if (field[i][j] == 'S') {
                pass[0] = make_pair(i, j);
            } else if (field[i][j] >= '1' && field[i][j] <= '9') {
                pass[field[i][j] - '0'] = make_pair(i, j);
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += distance(pass[i], pass[i + 1]);
    }
    printf("%d\n", sum);
}

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct data{
    int x,y;
};
queue <data> q;
data start,scop;
char field[1001][1001];
int ans[1001][1001],cop[1001][1001],H,W,N,cou,acou,s;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
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'){
                //data start;
                start.x=i,start.y=j;
                q.push(start);
            }
            if(field[i][j]=='1')cop[i][j]=1;
            if(field[i][j]=='2')cop[i][j]=2;
            if(field[i][j]=='3')cop[i][j]=3;
            if(field[i][j]=='4')cop[i][j]=4;
            if(field[i][j]=='5')cop[i][j]=5;
            if(field[i][j]=='6')cop[i][j]=6;
            if(field[i][j]=='7')cop[i][j]=7;
            if(field[i][j]=='8')cop[i][j]=8;
            if(field[i][j]=='9')cop[i][j]=9;
            if(field[i][j]=='X')cop[i][j]=-1;
        }
    }
    fill(ans[0],ans[0]+1001*1001,10000);
    //ans[start.x][start.y]=0;
    data now,a;
    for(int i=0;i<N;i++){
        while(!q.empty()){
        /*for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cout<<ans[i][j];
                }
            cout<<endl;
        }*/
            //cout<<ans[start.x][start.y]<<endl;
            now=q.front();
            q.pop();
            if(ans[now.x][now.y]!=10000||field[now.x][now.y]=='X')continue;
            /*if(cop[now.x][now.y]==i+1){
                q.empty();
                q.push(now);
                break;
            }*/
            for(int j=0;j<4;j++){
            if(ans[now.x+dx[j]][now.y+dy[j]]>=0&&now.x+dx[j]<1000&&now.x+dx[j]>=0&&now.y+dy[j]<1001&&now.y+dy[j]>=0)
                s=min(ans[now.x][now.y],ans[now.x+dx[j]][now.y+dy[j]])+1;
                //cout<<ans[now.x][now.y]<<" "<<now.x+dx[j]<<" "<<now.y+dy[j]<<endl;
                ans[now.x][now.y]=min(ans[now.x][now.y],s);
                //cout<<ans[now.x][now.y]<<endl;
            }
            if(cop[now.x][now.y]==i+1){
                while (!q.empty()) q.pop();
                q.push(now);
                break;
            }
            for(int j=0;j<4;j++){
                if(now.x+dx[j]>W-1&&now.x+dx[j]<0&&now.y+dy[j]>H-1&&now.y+dy[j]<0)continue;
                a.x=now.x+dx[j],a.y=now.y+dy[j];
                q.push(a);
            }
            ans[start.x][start.y]=0;
        }
        /*for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cout<<ans[i][j];
            }
            cout<<endl;
        }*/
        cou+=ans[now.x][now.y];
        fill(ans[0],ans[0]+1001*1001,10000);
        start.x=now.x,start.y=now.y;
        //ans[now.x][now.y]=0;
    }
    /*for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cout<<ans[i][j];
        }
        cout<<endl;
    }*/
    cout<<cou<<endl;
return 0;
}