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<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>  
#include<queue> 
#include<algorithm>
using namespace std;  
#define INF 1000  
int H, W, N;  
char map[1001][1001];  
int dx[4] = { 0, 0, 1, -1 };  
int dy[4] = { 1, -1, 0, 0 };  
int d[1001][1001];  
int sx, sy;  
int gx, gy;  
typedef pair<int, int> P;  
int sum = 0;  
void bfs()  
{  
    queue<P> que;  
    for (int i = 0; i < H; i++)  
        for (int j = 0; j < W; j++)  
            d[i][j] = INF;  
    que.push(P(sx, sy));  
    d[sx][sy] = 0;  
    while (que.size())  
    {  
        P p = que.front();  
        que.pop();  
        if (p.first == gx&&p.second == gy)break;  
        for (int i = 0; i < 4; i++)  
        {  
            int nx = p.first + dx[i], ny = p.second + dy[i];  
            if (0 <= nx&&nx < H && 0 <= ny&&ny < W&&map[nx][ny] != 'X'&&d[nx][ny] == INF)  
            {  
                que.push(P(nx, ny));  
                d[nx][ny] = d[p.first][p.second] + 1;  
            }  
        }  
    }  
    sum+=d[gx][gy];  
  
}  
int main()  
{  
    scanf("%d%d%d", &H, &W, &N);  
    while (getchar() != '\n')continue;  
    for (int i = 0; i < H; i++){  
        gets(map[i]);  
    }  
    for (int i = 0; i < H; i++)  
        for (int j = 0; j < W; j++)  
        {  
        if (map[i][j] == 'S')  
        {  
            sx = i;  
            sy = j; 
        }  
        }  
  
  
  
  
    for (int i = 0; i < N; i++)  
    {  
        for (int j = 0; j < H; j++)  
        {  
            for (int k = 0; k < W; k++)  
            {  
                if (map[j][k] == '1' + i)  
                {  
                      
                    gx = j; gy = k;  
                    bfs();
                    sx = j; sy = k;  
                }  
                      
            }  
        }  
    }  
    printf("%d\n", sum);  
  
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int ctoi(char c){
    switch(c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    int d[MAX][MAX];
    int ans=0;
    int sx[9];
    int sy[9];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                sx[0]=i;
                sy[0]=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                sx[ctoi(in)]=i;
                sy[ctoi(in)]=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                d[i][j]=INF;
            }
        }
        que.push(P(sx[k],sy[k]));
        d[sx[k]][sy[k]]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==P(sx[k+1],sy[k+1]))   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.second+dy[l];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]==INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[sx[k+1]][sy[k+1]];
    }
    
    cout<<ans<<endl;
    
    return 0;
}

C++: #include<iostream>
#include<queue>
using namespace std;
const int MAX_H = 1000;
const int MAX_W = 1000;
const int MAX_N = 10;
char map[MAX_H][MAX_W];
bool visit[MAX_N][MAX_H][MAX_W];
int h, w, n;
struct node
{
	int x;
	int y;
	int l;
	int step;
};
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int main()
{
	int i, j, k;
	cin >> h >> w >> n;
	node s;
	for (i = 0; i < h; i++)
	{
		for (j = 0; j < w; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'S')
			{
				s.x = i;
				s.y = j;
				s.l = 0;
				s.step = 0;
			}
			for (k = 0; k < n; k++)
			{
				visit[k][i][j] = false;
			}
		}
	}
	queue<node> que;
	que.push(s);
	int curlevel = 0;
	bool flag = false;
	while (que.size())
	{
		node t = que.front(); que.pop();
		if (t.l < curlevel)continue;
		for (i = 0; i < 4; i++)
		{
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if (xx < 0 || xx >= h || yy < 0 || yy >= w)
			{
				continue;
			}
			if (visit[t.l][xx][yy])continue;
			if (map[xx][yy] == 'X')continue;
			if (map[xx][yy] == '.')
			{
				visit[t.l][xx][yy] = true;
				node n;
				n.x = xx;
				n.y = yy;
				n.l = t.l;
				n.step = t.step + 1;
				que.push(n);
			}
			else
			{
				if (map[xx][yy] > t.l + 1 + '0' || map[xx][yy] < t.l + 1 + '0')
				{
					node n;
					n.x = xx;
					n.y = yy;
					n.l = t.l;
					n.step = t.step + 1;
					que.push(n);
					continue;
				}
				else
				{
					if (map[xx][yy] == n + '0')
					{
						flag = true;
						cout << t.step + 1 << endl;
						break;
					}
					node n;
					n.x = xx;
					n.y = yy;
					n.l = t.l + 1;
					n.step = t.step + 1;
					visit[n.l][xx][yy] = true;
					curlevel++;
					que.push(n);
				}
			}
		}
		if (flag)break;
	}
	return 0;
}