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 <cstring>
#include <queue>
#include <utility>
#include <algorithm>
#define MAXHW 1000 + 1

using namespace std;
typedef pair<int, int> P;

int n, m, H, W, N, d[MAXHW][MAXHW];
char fac[MAXHW][MAXHW];

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

int bfs(int a, int b, int s){
	memset(d, -1, sizeof(d));
	queue<P> q;
	d[a][b] = 0;
	q.push(P(a, b));
	
	while(!q.empty()){
		P p = q.front();
		q.pop();
		
		if(fac[p.first][p.second] == char(s + '0')){
			n = p.first, m = p.second;
			cout << d[p.first][p.second] << endl;
			return d[p.first][p.second];
		}
		
		for(int i = 0; i < 4; i++){
			int h = p.first + dy[i];
			int k = p.second + dx[i];
			if(h >= 0 && h < H && k >= 0 && k < W && fac[h][k] != 'X' && d[h][k] == -1){
				d[h][k] = d[p.first][p.second] + 1;
				q.push(P(h, k));
			}
		}
	}
}

int main(){
	int sum = 0;
	scanf("%d %d %d", &H, &W, &N);
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cin >> fac[i][j];
			if(fac[i][j] == 'S')
				n = i, m = j;
		}
	}
	for(int i = 1; i <= N; i++)
		sum += bfs(n, m, i);
	
	cout << sum << endl;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
#define mod 1000000007

ll gcd(ll x,ll y) {return y ? gcd(y,x%y) : x;} 
ll lcm(ll x,ll y) {return x/gcd(x,y)*y;}

typedef pair<int,int> P;
const int hmax=1001,wmax=1001;
const int INF=1000100100;
char mp[hmax][wmax];
int d[hmax][wmax];
int h,w,n,ans=0;
int sy,sx;
int dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
int gy[10],gx[10];


int bfs(){
    cin >> h >> w >> n;
    rep(i,h)rep(j,w) d[i][j]=INF;
    rep(i,h)rep(j,w){
        cin >> mp[i][j];
        if(mp[i][j]=='S'){
            sy=i,sx=j;
        }
        if(mp[i][j]!='S'&&mp[i][j]!='X'&&mp[i][j]!='.'){
            gy[mp[i][j]-'1']=i,gx[mp[i][j]-'1']=j;
        }
    }
    rep(k,n){
        rep(i,h)rep(j,w) d[i][j]=INF;
        d[sy][sx]=0;
        queue<P> q;
        q.push(P(sy,sx));
        while(q.size()){
            P p=q.front();
            q.pop();
            if(p.first==gy[k]&&p.second==gx[k]) break;
            rep(i,4){
                int y=p.first+dy[i],x=p.second+dx[i];
                if(0<=y&&y<h&&0<=x&&x<w&&d[y][x]==INF&&mp[y][x]!='X'){
                    q.push(P(y,x));
                    d[y][x]=d[p.first][p.second]+1;
                }
            }
        }
        ans+=d[gy[k]][gx[k]];
        sy=gy[k],sx=gx[k];
    }
    return ans;
}

int main(){
    cout << bfs() << endl;
    return 0;
}

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

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

struct Info {
    int r;
    int c;
    int cost;
    Info(int r, int c, int cost) : r(r), c(c), cost(cost){}
};

int bfs(vector<string> map, pair<int, int> start, char target) {
    int res = 0;
    queue<Info> que;
    que.push(Info(start.first, start.second, 0));
    map[start.first][start.second] = 'o';
    while (!que.empty()) {
        Info info = que.front(); que.pop();
        for (int i = 0; i < 4; i++) {
            int nr = info.r + dr[i];
            int nc = info.c + dc[i];
            if (nr >= 0 && nr < map.size() && nc >= 0 && nc < map[nr].size()
                    && map[nr][nc] != 'X' && map[nr][nc] != 'o') {
                if  (map[nr][nc] == target) {
                    res = info.cost + 1;
                    break;
                }
                map[nr][nc] = 'o';
                Info nextInfo = Info(nr, nc, info.cost + 1);
                que.push(nextInfo);
            }
        }

        /*
        cerr << "=======[" << info.r << "," << info.c << "]===========" << endl;
        for (int i = 0; i < map.size(); i++) {
            for (int j = 0; j < map[i].size(); j++) {
                cerr << map[i][j];
            }
            cerr << endl;
        }
        */
    }



    return res;
}

int getCost(vector<string>& map, int next, int N) {
    char from = 'S';
    if (next > 1) from = char(next - 1 + '0');
    char to = char(next + '0');
    pair<int, int> start;
    for (int i = 0; i < map.size(); i++) {
        for(int j = 0; j < map[i].size(); j++) {
            if (map[i][j] == from) {
                start = pair<int, int>(i, j);
                int c = bfs(map, start, to);

                return c;
            }
        }
    }
    return 0;
}

int solve(vector<string>& map, int N) {
    int cost = 0;
    for (int k = 1; k <= N; k++) {
        cost += getCost(map, k, N);
    }
    return cost;
}

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    vector<string> map;
    for (int i = 0; i < H; i++) {
        string s; cin >> s;
        map.push_back(s);
    }
    int answer = solve(map, N);
    cout << answer << endl;
}

C++: #include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxh = 1005, INF = 1e8, maxn = 14;
int H, W, N;
char field[maxh][maxh];
int dp[maxh][maxh], res = 0;
int sx, sy, gx, gy;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
typedef pair<int, int> P;
P cheese[maxn];
int bfs()
{
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            dp[i][j] = INF;
        }
    }
    queue<P> que;
    que.push(P(sx, sy));
    dp[sx][sy] = 0;
    while(que.size()){
        P p = que.front();
        que.pop();
        int x = p.first, y = p.second;
//        printf("%d %d\n", x, y);
        if(x == gx && y == gy)
            break;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < H && ny >= 0 && ny < W && field[nx][ny] != 'X' && dp[nx][ny] == INF){
                que.push(P(nx, ny));
                dp[nx][ny] = dp[x][y] + 1;
            }
        }

    }
    return dp[gx][gy];
}
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] >= '1' && field[i][j] <= '9'){
                cheese[field[i][j] - '0'].first = i;
                cheese[field[i][j] - '0'].second =j;
            }
            else if(field[i][j] == 'S'){
                sx = i; sy = j;
            }
        }
    }
    for(int i = 1; i <= N; i++){
        gx = cheese[i].first, gy = cheese[i].second;
        res += bfs();
        sx = gx; sy = gy;
    }
    printf("%d\n", res);
    return 0;
}