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 <string>
#include <utility>
#include <queue>

constexpr int INF = 1000000000;
using Pair = std::pair<int, int>;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int h, w, n;
std::string map[1010];
int cost[1010][1010];
Pair pts[10];

int bfs(Pair st, Pair en) {
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            cost[i][j] = INF;
        }
    }
    cost[st.first][st.second] = 0;

    std::queue<Pair> que;
    que.push(st);

    while(!que.empty()) {
        auto p = que.front(); que.pop();

        for(int i = 0; i < 4; ++i) {
            int py = p.first + dy[i], px = p.second + dx[i];

            if(py < 0 || px < 0 || py >= h || px >= w)
                continue;

            if(map[py][px] == '.' && cost[py][px] == INF) {
                que.push({py, px});
                cost[py][px] = cost[p.first][p.second] + 1;
            }
        }
    }

    return cost[en.first][en.second];
}

int main() {
    std::cin >> h >> w >> n;

    for(int i = 0; i < h; ++i) {
        std::cin >> map[i];

        for(int j = 0; j < w; ++j) {
            if(map[i][j] != '.' && map[i][j] != 'X') {
                int idx = (map[i][j] == 'S' ? 0 : map[i][j] - '0');

                pts[idx] = {i, j};
                map[i][j] = '.';
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += bfs(pts[i - 1], pts[i]);
    }

    std::cout << ans << std::endl;
}

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

#define MAXN 1000
struct node{
    int x,y,st;
    bool operator == (node B) const{
        return x==B.x&&y==B.y;
    }
};
int H,W,N;
char Map[MAXN+5][MAXN+5];
bool vis[MAXN+5][MAXN+5];

const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int bfs(node S,node T){
    queue<node> Q;
    Q.push(S);
    memset(vis,0,sizeof vis);
    while(!Q.empty()){
        node u=Q.front();Q.pop();
        for(int i=0;i<4;i++){
            node tmp=u;
            tmp.x+=dir[i][0],tmp.y+=dir[i][1],tmp.st++;
            if(tmp.x<1||tmp.x>H||tmp.y<1||tmp.y>W||vis[tmp.x][tmp.y]||Map[tmp.x][tmp.y]=='X')
                continue;
            if(tmp==T)
                return tmp.st;
            vis[tmp.x][tmp.y]=1;
            Q.push(tmp);
        }
    }
    return -1;
}

pair<int,int> pos[10];

int main(){
    scanf("%d%d%d",&H,&W,&N);
    for(int i=1;i<=H;i++)
        scanf("%s",Map[i]+1);
    node S;
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++){
            if(Map[i][j]!='.'&&Map[i][j]!='X'&&Map[i][j]!='S')
                pos[Map[i][j]-'1'+1]=make_pair(i,j);
            if(Map[i][j]=='S')
                S.x=i,S.y=j,S.st=0;
        }
    int Ans=0;
    for(int i=1;i<=N;i++){
        Ans+=bfs(S,(node){pos[i].first,pos[i].second,0});
        S=(node){pos[i].first,pos[i].second,0};
    }
    printf("%d",Ans);
}

C++: #include <iostream>
#include <vector>
#include <queue>

using ll = long long;
using namespace std;
using P = pair<int, int>;
static const int INF = 10000000;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int dis[1002][1002];
bool ma[1002][1002] = {};

int main() {
    int h, w, n, t = 0;
    cin >> h >> w >> n;
    P cp[10];
    queue<P> Q;
    fill_n(&dis[0][0], 1002*1002, INF);
    for (int i = 1; i < h+1; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j < w+1; ++j) {
            ma[i][j] = s[j-1] != 'X';
            if(s[j-1] == 'S') cp[0] = make_pair(i, j);
            if('1' <= s[j-1] && s[j-1] <= '9') cp[s[j-1]-'0']= make_pair(i, j);
        }
    }

    for (int i = 0; i < n; ++i) {
        fill_n(&dis[0][0], 1002*1002, INF);
        P st = cp[i], gl = cp[i+1];
        Q.push(st);
        dis[st.first][st.second] = 0;
        while(!Q.empty()){
            int y = Q.front().first, x = Q.front().second; Q.pop();
            for (int j = 0; j < 4; ++j) {
                int ny = y + dy[j], nx = x + dx[j];
                if(dis[ny][nx] == INF && ma[ny][nx]){
                    dis[ny][nx] = dis[y][x] + 1;
                    Q.push(make_pair(ny, nx));
                }
            }
        }
        t += dis[gl.first][gl.second];
    }
    cout << t << "\n";
    return 0;
}

C++: //Cheese
#include <iostream>
#include <queue>

using namespace std;
static const int MAX = 1000;
static const int dx[4] = {1, 0, -1, 0};
static const int dy[4] = {0, 1, 0, -1};

int H, W, N, gx, gy;
int A[MAX][MAX];
bool visited[MAX][MAX];

struct State {
    int x, y, d;
    State() {}
    State(int x, int y, int d): x(x), y(y), d(d) {}
};

int bfs(int t, int x, int y) {
    queue<State> Q;
    Q.push(State(x, y, 0));
    for(int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            visited[i][j] = false;
        }
    }
    visited[y][x] = true;
    while(!Q.empty()) {
        State s = Q.front();
        Q.pop();
        if(A[s.y][s.x] == t) {gx = s.x; gy = s.y; return s.d;}
        for(int i = 0; i < 4; i++) {
            int sx, sy;
            sx = s.x + dx[i];
            sy = s.y + dy[i];
            if(sx >= 0 && sy >= 0 && sx < W && sy < H) {
                if(A[sy][sx] == -1) continue;
                if(visited[sy][sx]) continue;
                Q.push(State(sx, sy, s.d + 1));
                visited[sy][sx] = true;
            }
        }
    }
    return 0;
}

int main() {
    cin >> H >> W >> N;
    char c;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> c;
            if(c == '.') A[i][j] = 0;
            else if(c == 'X') A[i][j] = -1;
            else if(c == 'S') {A[i][j] = 0; gx = j; gy = i;}
            else A[i][j] = c - '0';
        }
    }

    int d = 0;
    for(int i = 1; i < N + 1; i++) d += bfs(i, gx, gy);

    cout << d << endl;

    return 0;
}