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

const int N = 1000;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int cost[N][N];
char m[N][N];
class st{
public:
  int y,x;
};

int bfs(int sy,int sx,int r,int c,char tar){
  queue<st> Q;
  rep(i,r){
    rep(j,c)cost[i][j]=-1;
  }
  cost[sy][sx]=0;
  Q.push((st){sy,sx});
  while(!Q.empty()){
    st now = Q.front();Q.pop();
    int nc=cost[now.y][now.x];
    if (m[now.y][now.x] == tar){
      return nc;
    }
    rep(i,4){
      int nex=now.x+dx[i],ney=now.y+dy[i];
      if (nex == -1 || ney == -1 || nex == c || ney == r ||
	  m[ney][nex] == 'X' || cost[ney][nex] != -1)continue;
      cost[ney][nex]=nc+1;
      Q.push((st){ney,nex});
    }
  }
  return -1;
}

main(){
  int r,c,n;
  while(cin>>r>>c>>n ){
    rep(i,r){
      cin>>m[i];
    }
    int sx[n],sy[n];
    const string tar="123456789";
    rep(i,r){
      rep(j,c){
	if (m[i][j] == 'S'){
	  sx[0]=j;
	  sy[0]=i;
	}else if (isdigit(m[i][j]) && m[i][j]-'0' != n){
	  sx[m[i][j]-'0']=j;
	  sy[m[i][j]-'0']=i;
	}
      }
    }

    int ans=0;
    rep(i,n){
      int tmp=bfs(sy[i],sx[i],r,c,tar[i]);
      //cout <<i <<" " << tmp << " " << sy[i] <<" " <<
      //sx[i] <<" " << tar[i] << endl;
      ans+=tmp;
    }
    cout << ans << endl;
  }
  return false;
}

C++: #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> P;

int H, W, N;
int map[1000][1000];
bool visited[1000][1000];
P Points[10];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

struct point {
    int x;
    int y;
    int step;
    point(int xx, int yy, int ss) : x(xx), y(yy), step(ss) {} 
};

int main() {
    cin >> H;
    cin >> W;
    cin >> N;
    char tmp[1000];
    for (int i = 0; i < H; i++) {
        cin >> tmp;
        for (int j = 0; j < W; j++) {
            if (tmp[j] == 'X') map[i][j] = 1;
            else {
                map[i][j] = 0;
                if (tmp[j] == 'S') {
                    Points[0] = make_pair(i,j);
                }
                else if (tmp[j] != '.') {
                    Points[tmp[j]-'0'] = make_pair(i,j);
                }
            }
        }
    }

    int res = 0;

    for (int i = 0; i < N; i++) {
        P start = Points[i];
        P goal = Points[i+1];
        int sx = start.first, sy = start.second, gx = goal.first, gy = goal.second;
        
        memset(visited,false,sizeof(visited));
        visited[sx][sy] = true;
        queue<point> que;
        que.push(point(sx,sy,0));

        while (!que.empty()) {
            point p = que.front(); que.pop();
            int x = p.x, y = p.y, s = p.step;
            if (x == gx && y == gy) {
                res += s;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x1 = x + dx[i], y1 = y + dy[i];
                if (x1 >= 0 && x1 < H && y1 >= 0 && y1 < W && !visited[x1][y1] && map[x1][y1] == 0) {
                    visited[x1][y1] = true;
                    que.push(point(x1,y1,s+1));
                }
            }
        }
    }
    cout << res << "\n";

}

C++: // AOJ 0558
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<map>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define X first
#define Y second
using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> S;

int H, W, N;
const int HMAX = 1008, WMAX = 1008;
char field[HMAX][WMAX];

bool legal(P p) {
  return 0 <= p.X and p.X < W and 0 <= p.Y and p.Y < H;
}

int dist(P start, P goal) {
  priority_queue<S, vector<S>, greater<S> > que;
  que.push(S(0, start));
  while (!que.empty()) {
    S s = que.top();
    que.pop();
    P cur = s.second;

    if (cur.X == goal.X and cur.Y == goal.Y) {
      return s.first;
    }

    const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
    REP(i, 4) {
      P p = P(cur.X + dx[i], cur.Y + dy[i]);
      if (legal(p) and field[p.X][p.Y] != 'X') {
        que.push(S(s.first + 1, p));
      }
    }
  }
}

P search(char c) {
  REP(y, H) REP(x, W) {
    if (field[x][y] == c)
      return P(x, y);
  }
}

int solve() {
  int ans = 0;
  P start = search('S');
  for (int i = 1; i <= N; i++) {
    P goal = search('0' + i);
    ans += dist(start, goal);
    start = goal;
  }
  return ans;
}

int main() {
  cin >> H >> W >> N;
  REP(y, H) {
    string row;
    cin >> row;
    REP(x, W) {
      field[x][y] = row[x];
    }
  }

  cout << solve() << endl;
}