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 <algorithm>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); ++i)
 
typedef pair<int, int> P;

int H, W, N;
char m[1001][1001];
int d[1001][1001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void dfs(int i, int j) {
    char c = m[i][j];
    m[i][j] = '.';
    if(j+1<W && m[i][j+1]==c) dfs(i, j+1);
    if(j>0 && m[i][j-1]==c) dfs(i, j-1);
    if(i+1<H && m[i+1][j]==c) dfs(i+1, j);
    if(i>0 && m[i-1][j]==c) dfs(i-1, j);
}
int main() {
    cin >> H >> W >> N;
    int x, y;
    rep(i, H) {
        rep(j, W) {
            cin >> m[i][j];
            if(m[i][j]=='S') {
                x = j;
                y = i;
            }
        }
    }

    int HP = 1;
    int time = 0;
    int dist = 0;
    while(HP <= N) {
        rep(i, H) {
            rep(j, W) {
                d[i][j] = -1;
            }
        }
        d[y][x] = dist;
        queue<P> q;
        q.push(P(x, y));
        while(q.size()>0) {
            P p = q.front(); q.pop();
            int cx = p.first;
            int cy = p.second;
            if(m[cy][cx]=='0'+HP) {
                x = cx;
                y = cy;
                dist = d[y][x];
                HP++;
                break;
            } 
            rep(i, 4) {
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(0<=nx && nx<W && 0<=ny && ny<H &&
                        d[ny][nx] == -1 && m[ny][nx]!='X') {
                    q.push(P(nx, ny));
                    d[ny][nx] = d[cy][cx] + 1;
                }
            }
        }
    }
    cout << dist << endl;
    return 0;
}

C++: #include <cstdio>
#include <queue>
#include <utility>
using namespace std;
#define mp make_pair
typedef pair<int, int> pint;
const int INF = 100000000;

int h, w, n;
char maze[1000][1000];
int i, j;

struct {
	int x, y;
} dir[4] = {
	{1, 0}, // right
	{0, 1}, // down
	{-1, 0}, // left
	{0, -1} // up
};

int dist[1000][1000];

int bfs(int hp) {
	for(int x = 0; x < w; x++) {
		for(int y = 0; y < h; y++) {
			dist[y][x] = INF;
		}
	}
	dist[i][j] = 0;
	queue<pint> q;
	q.push(mp(i, j));
	while(!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if(maze[y][x] == (char)('0' + hp)) {
			i = y;
			j = x;
			maze[i][j] = '.';
			break;
		}
		for(int k = 0; k < 4; k++) {
			int nx = x + dir[k].x;
			int ny = y + dir[k].y;
			if(0 <= nx && nx < w && 0 <= ny && ny < h && maze[ny][nx] != 'X') {
				if(dist[ny][nx] == INF) { // never searched
					dist[ny][nx] = dist[y][x] + 1;
					q.push(mp(ny, nx));
				}
			}
		}
	}
	int ret = dist[i][j];
	return ret;
}

int main() {
	scanf(" %d %d %d", &h, &w, &n);
	for(int y = 0; y < h; y++) {
		scanf(" %s", maze[y]);
	}
	int ans = 0;
	{
		bool loop = true;
		for(int x = 0; x < w; x++) {
			for(int y = 0; y < h; y++) {
				if(maze[y][x] == 'S') {
					i = y;
					j = x;
					maze[y][x] = '.';
					loop = false;
					break;
				}
			}
			if(!loop) break;
		}
	}
	for(int x = 1; x <= n; x++) {
		ans += bfs(x);
	}
	printf("%d\n", ans);
	return 0;
}

C++: //2013-5

#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <time.h>
#define INF 1e8
#define fs first
#define sc second
#define rep(x,n) for(int x = 0;x < n;x ++)
#define Rep(x,n) for(int x = 1;x <= n;x ++)
using namespace std;


char mp[1005][1005];
int d[1005][1005];
int chx[10];
int chy[10];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

//下向きにx,右向きにy
int main(){
    int H,W;
    int N;
    cin >> H >> W;
    cin >> N;
    int ans = 0;
    
    rep(i,H){
        scanf("%s",mp[i]);
        rep(j,W){
            if('1'<=mp[i][j]&&mp[i][j]<'9'){
                chx[mp[i][j]-'0']=i;
                chy[mp[i][j]-'0']=j;
            }else if(mp[i][j]=='S'){
                chx[0]=i;
                chy[0]=j;
            }
        }
    }    rep(i,N){
        queue<pair<int,int> > que;
        rep(j,H){
            rep(k,W){
                d[j][k]=-1;
            }
        }
        d[chx[i]][chy[i]]=0;
        que.push(make_pair(chx[i],chy[i]));
        while(!que.empty()){
            int flag = 0;
            int nowx = que.front().first;
            int nowy = que.front().second;
            que.pop();
            rep(j,4){
                int nextx = nowx+dx[j];
                int nexty = nowy+dy[j];
                if(!(0<=nextx&&nextx<H&&0<=nexty&&nexty<W))
                    continue;
                if( mp[nextx][nexty]!='X' && d[nextx][nexty]==-1){
                    d[nextx][nexty]=d[nowx][nowy]+1;
                    que.push(make_pair(nextx,nexty));
                }
                if(mp[nextx][nexty]=='1'+i){
                    ans += d[nextx][nexty];
                    flag = 1;
                    break;
                }
            }
            if(flag == 1)
                break;
        }
    }
    cout << ans << endl;
}