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 <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++){
            cin>>map[i][j]
        }
    }
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char ch=map[i][j];
            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();
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> P;
int N,M,L,sx,sy,gx,gy,num;
char maze[110][110];
int d[110][110];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
P s[10];
int bfs()
{
	queue<P> que;
		que.push(P(sx,sy));
	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(nx>=0 && nx<N && ny>=0 && ny<M && maze[nx][ny]!='X' )
				{
					que.push(P(nx,ny));
					d[nx][ny]=d[p.first ][p.second ]+1; 
				}   
			}
	}
}
void solve()
{
	for(int i=0;i<L;i++)
	{
		sx=s[i].first ,sy=s[i].second;
		gx=s[i+1].first ,gy=s[i+1].second;
		bfs();
	}
	printf("%d\n",d[s[L].first ][s[L].second ]);
}
int main()
{
	while(~scanf("%d %d %d",&N,&M,&L))
	{
		num=0;
		memset(d,0,sizeof(d));
		for(int i=0;i<N;i++)
			for(int j=0;j<M;j++)
			{
				scanf("\n%c",&maze[i][j]);
				if(maze[i][j]=='S')
				s[0].first ,s[0].second ; 
				else if(maze[i][j]<='9' && maze[i][j] >='1')
				s[maze[i][j]-'0'].first =i,s[maze[i][j]-'0'].second =j;
			}
		solve();
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<P, int> PI; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };
bool visited[1000][1000];
char stage[1000][1000];
int h, w, n;

int main(void)
{
	ios::sync_with_stdio(false);
	while(cin >> h >> w >> n && n)
	{
		PArray goals(n + 1);
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> stage[i][j];
				if(stage[i][j] == 'S') goals[0] = P(i, j);
				int num = stage[i][j] - '0';
				if(inRange(n + 1, num)) goals[num] = P(i, j);
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			P start = goals[i], goal = goals[i + 1];
			memset(visited, false, sizeof(visited));
			queue<PI> que;
			que.push(PI(start, 0));
			while (!que.empty())
			{
				PI pi = que.front(); que.pop();
				if(goal == pi.first)
				{
					ans += pi.second;
					break;
				}
				int r = pi.first.first, c = pi.first.second;

				for (int i = 0; i < 4; i++)
				{
					int nr = r + dr[i], nc = c + dc[i];
					if(!inRange(h, nr) || !inRange(w, nc) || stage[nr][nc] == 'X' || visited[nr][nc]) continue;
					que.push(PI(P(nr, nc), pi.second + 1));
					visited[nr][nc] = true;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}