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 <cstring>
#include <queue>
using namespace std;

char ma[1005][1005];int vis[1005][1005];
int w,h,n;

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

struct node
{
    int x,y,time;

};
node start;

void bfs(node st,char ed)
{
    queue<node> que;
    que.push(st);
    vis[st.x][st.y]=1;
    while(!que.empty())
    {
        node no=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int x=no.x+dx[i];
            int y=no.y+dy[i];
            if(vis[x][y]||x>=w||x<0||y>=h||y<0||ma[x][y]=='X')
                continue;
            if(ma[x][y]==ed)
            {
                start.x=x;
                start.y=y;
                start.time=no.time+1;
                return ;
            }
            vis[x][y]=1;
            node no1;
            no1.x=x;no1.y=y;no1.time=no.time+1;
            que.push(no1);
        }
    }
}

int main()
{
    while(~scanf("%d %d %d", & w, & h, & n))
    {
        for(int i=0;i<w;i++)
        {
            cin>>ma[i];
            for(int j=0;j<h;j++)
                if(ma[i][j]=='S')
                {
                    start.x=i;
                    start.y=j;
                    start.time=0;
                    ma[i][j]='0';
                }

        }
            for(int i=0;i<n;i++)
            {
                memset(vis,0,sizeof(vis));
                bfs(start,i+'1');
            }

            printf("%d\n",start.time);


    }
}

C++: /* AOJ0558 Cheese */

#include <iostream>
#include <queue>
//#include <string.h>

using namespace std;

const int N = 1000;
char grid[N][N];
int w, h, n;

// 各点到当前工厂的距?
int d[N][N];

const int direct[4][2] = {
    { -1, 0 },
    { 1, 0 },
    { 0, -1 },
    { 0, 1 },
};

int factory[10][2];
typedef pair<int, int> P;

int bfs(const int& sx, const int& sy, const int& gx, const int& gy)
{
    //memset(d, -1, sizeof(d));
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            d[j][i] = -1;
        }
    }
    queue<P> que;
    que.push(P(sx, sy));
    d[sx][sy] = 0;
    while (que.size())
    {
        const 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 + direct[i][0];
            int ny = p.second + direct[i][1];
            // 是否可以移?，并且?点没有???
            if (0 <= nx && nx < w && 0 <= ny && ny < h && grid[nx][ny] != 'X' && d[nx][ny] == -1)
            {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }

    return d[gx][gy];
}

int main()
{

    while(cin >> h >> w >> n) {
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j) {
                cin >> grid[j][i];
                if (grid[j][i] == 'S') {
                    factory[0][0] = j;
                    factory[0][1] = i;
                    grid[j][i] = '.';
                }
                else if (isdigit(grid[j][i])) {
                    factory[grid[j][i] - '0'][0] = j;
                    factory[grid[j][i] - '0'][1] = i;
                }
            }


        int minstep = 0;
        for (int i = 0; i < n; ++i) {
            minstep += bfs(factory[i][0], factory[i][1], factory[i + 1][0], factory[i + 1][1]);
        }

        cout << minstep << endl;
    }

    return 0;
}

C++: #include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }

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

int n, m, N;
vector<string> fi;

pint pl[11];
int dist[1100][1100];

int solve(pint p, pint q) {
    memset(dist, -1, sizeof(dist));
    dist[p.first][p.second] = 0;
    queue<pint> que;
    que.push(p);
    
    while (!que.empty()) {
        pint now = que.front(); que.pop();
        if (now == q) break;
        for (int i = 0; i < 4; ++i) {
            int ni = now.first + dx[i], nj = now.second + dy[i];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if (fi[ni][nj] == 'X') continue;
            if (dist[ni][nj] == -1) {
                dist[ni][nj] = dist[now.first][now.second] + 1;
                que.push( pint(ni, nj) );
            }
        }
    }
    
    return dist[q.first][q.second];
}

int main() {
    while (cin >> n >> m >> N) {
        fi.resize(n);
        for (int i = 0; i < n; ++i) cin >> fi[i];
        
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
            if (fi[i][j] == 'S') pl[0] = pint(i, j);
            else if (fi[i][j] != '.' && fi[i][j] != 'X') pl[fi[i][j] - '0'] = pint(i, j);
        }
        
        int res = 0;
        for (int i = 0; i < N; ++i) res += solve(pl[i], pl[i+1]);
        
        cout << res << endl;
    }
    return 0;
}