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

const int M=1005;
char ti[M][M];
int isu[M][M];
int n,m,nn;

int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};

queue<int> qu;
void init_bfs()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ti[i][j]=='S')
            {
                qu.push(i*M+j);
                isu[i][j]=0;
                return;
            }
}
int bfs()
{
    int ans=0;
    int edx,edy;
    for(int ii=1;ii<=nn;ii++)
    {
        while(!qu.empty())
            qu.pop();
        memset(isu,-1,sizeof(isu));
        if(ii==1)
            init_bfs();
        else
        {
            qu.push(edx*M+edy);
            isu[edx][edy]=0;
        }
        int f=0;
        while(!qu.empty())
        {
            int t=qu.front();
            qu.pop();
            int tx=t/M,ty=t%M;
            for(int i=0;i<4;i++)
            {
                int x=tx+dx[i],y=ty+dy[i];
                if(x<1||x>n||y<1||y>m||ti[x][y]=='X'||isu[x][y]!=-1)
                    continue;
                if(ti[x][y]=='0'+ii)
                {
                    ans+=isu[tx][ty]+1;
//                    cout<<ans<<endl;
//                    for(int i=0;i<=n+1;i++)
//                    {
//                        for(int j=0;j<=m+1;j++)
//                            cout<<'\t'<<isu[i][j];
//                        cout<<endl;
//                    }
                    edx=x;edy=y;
                    f=1;
                    break;
                }
                qu.push(x*M+y);
                isu[x][y]=isu[tx][ty]+1;
            }
            if(f==1)
                break;
        }
        if(!f)
            return -1;
    }
    return ans;
}

int main()
{
    //freopen("1.out","w",stdout);
    scanf("%d%d%d",&n,&m,&nn);
    for(int i=1;i<=n;i++)
        scanf("%s",ti[i]+1);
    printf("%d\n",bfs());
    return 0;
}

C++: 22:42 
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# include <iostream>
# include <queue>
# include <cctype>
typedef std::pair<int, int> P;
テつ?
const int INF = 100000;
const int MAX_H = 1000;
const int MAX_W = 1000;
const int MAX_N = 9;
テつ?
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int h, w, n;
int d[MAX_H][MAX_W];
char ch[MAX_H][MAX_W];
P p[MAX_N + 1];
テつ?
int bfs(P s, P g) {
テつ?つ?つ?つ?or (int i = 0; i<h; ++i) {
テつ?つ?つ?つ?つ?つ?つ?つ?or (int j = 0; j<w; ++j)
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[i][j] = INF;
テつ?つ?つ?つ?
テつ?つ?つ?つ?td::queue<P> que;
テつ?つ?つ?つ?ue.push(s);
テつ?つ?つ?つ?[s.second][s.first] = 0;
テつ?つ?つ?つ?hile (!que.empty()) {
テつ?つ?つ?つ?つ?つ?つ?つ? x = que.front(); que.pop();
テつ?つ?つ?つ?つ?つ?つ?つ?f (x == g)
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?reak;
テつ?つ?つ?つ?つ?つ?つ?つ?or (int i = 0; i < 4; ++i) {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?nt nx = x.first + dx[i];
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?nt ny = x.second + dy[i];
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?f (nx >= 0 && ny >= 0 && nx < w && ny < h && d[ny][nx] == INF && ch[ny][nx] != 'X') {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?ue.push(P(nx, ny));
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[ny][nx] = d[x.second][x.first] + 1;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?
テつ?つ?つ?つ?eturn d[g.second][g.first];
}
テつ?
int solve() {
テつ?つ?つ?つ?nt res = 0;
テつ?つ?つ?つ?or (int i = 1; i <= n; ++i) {
テつ?つ?つ?つ?つ?つ?つ?つ?es += bfs(p[i - 1], p[i]);
テつ?つ?つ?つ?
テつ?つ?つ?つ?eturn res;
}
テつ?
int main() {
テつ?つ?つ?つ?td::cin >> h >> w >> n;
テつ?つ?つ?つ?or (int i = 0; i < h; ++i) {
テつ?つ?つ?つ?つ?つ?つ?つ?or (int j = 0; j < w; ++j) {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?td::cin >> ch[i][j];
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?f (std::isdigit(ch[i][j])) {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[atoi(&ch[i][j])].first = j;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[atoi(&ch[i][j])].second = i;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?lse if (ch[i][j] == 'S') {
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[0].first = j;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?[0].second = i;
テつ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?つ?つ?つ?つ?
テつ?つ?つ?つ?
テつ?つ?つ?つ?td::cout << solve() << std::endl;
テつ?つ?つ?つ?eturn 0;

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

int h,w,n;
const int MAX_N=1005;
char map[MAX_N][MAX_N];
struct point{
    int x,y;
    int step;
    point(){
        x=0; y=0; step=0;
    }
    point(int xx, int yy, int ss){
        x=xx;
        y=yy;
        step=ss;
    }
};
struct point p[16];

int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};

int ok(int x, int y){
    if(x>=0 && x<h && y>=0 && y<w) return 1;
    return 0;
}

int bfs(int next){
    int nextcheese = next +1; 
    
    queue<point> q;
    point cur(p[next].x, p[next].y,0);
    q.push(cur);
    while(q.size()){
        cur = q.front(); q.pop(); 
        int x=cur.x, y=cur.y;
        int nx, ny;
        for(int i=0; i<4; i++){
            nx = x+dx[i]; ny=y+dy[i];
            if(ok(nx, ny)){
                if((map[nx][ny]-'0')==nextcheese) return ++cur.step;
                if(map[nx][ny]=='.'){
                    point temp(nx, ny, cur.step+1);
                    q.push(temp);
                }
            }
        }
    }
}

void solve(){
    cin>>h>>w>>n;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char ch;
            cin>>ch; map[i][j]=ch;
            switch(ch){
                case '.': break;
                case 'X': break;
                case 'S': p[0].x = i; p[0].y = j; map[i][j]='.';break;
                default:
                int t=ch-'0';
                p[t].x = i; p[t].y = j;
            }
        }
    }
    int step=0;
    for(int i=0; i<n; i++){
        step+=bfs(i);
    }
    printf("%d\n", step);
}


int main(){
    solve();
}