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 <queue>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int H, W, N;
int main() {
	cin >> H >> W >> N;
	vector<string> s(H);
	vector<int> x(N + 1), y(N + 1);
	for (int i = 0; i < H; i++) {
		cin >> s[i];
		for (int j = 0; j < W; j++) {
			if (s[i][j] == 'S') x[0] = j, y[0] = i;
			else if (isdigit(s[i][j])) x[s[i][j] - 48] = j, y[s[i][j] - 48] = i;
		}
	}
	vector<vector<int> > G(H * W);
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i][j] != 'X' && s[i + 1][j] != 'X') {
				int v1 = i * W + j, v2 = v1 + W;
				G[v1].push_back(v2);
				G[v2].push_back(v1);
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) {
			if (s[i][j] != 'X' && s[i][j + 1] != 'X') {
				int v1 = i * W + j, v2 = v1 + 1;
				G[v1].push_back(v2);
				G[v2].push_back(v1);
			}
		}
	}
	int ret = 0;
	for (int i = 0; i < N; i++) {
		vector<int> dist(H * W, -1); dist[y[i] * W + x[i]] = 0;
		queue<int> que; que.push(y[i] * W + x[i]);
		while (!que.empty()) {
			int u = que.front(); que.pop();
			for (int i : G[u]) {
				if (dist[i] == -1) {
					dist[i] = dist[u] + 1;
					que.push(i);
				}
			}
		}
		ret += dist[y[i + 1] * W + x[i + 1]];
	}
	cout << ret << endl;
	return 0;
}

C++: #include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

const int MAX_W = 1002;
const int MAX_H = 1002;

int w, h, n;
char field[MAX_H][MAX_W];
bool G[MAX_H][MAX_W];

int bfs(pii s, pii g){
	fill_n((bool *)G, MAX_H*MAX_W, false);

	int step = 0;
	queue<pii> que;
	que.push(s);
	que.push({-1, -1});

	while(1){
		pii p = que.front(); que.pop();
		if(p.first == -1){
			if(que.empty()){
				break;
			}
			que.push(p);
			step++;
			continue;
		}
//		LOG("%d %d %c\n",p.first, p.second, field[p.second][p.first]);
		if(p == g){
			return step;
		}

		REP(i, 4){
			int sx = p.first + dx[i];
			int sy = p.second + dy[i];
			if(field[sy][sx] != 'X'){
				if (G[sy][sx] == false){
					G[sy][sx] = true;
					que.push({sx, sy});
				}
			}
		}
	}

	return -1;
}

int main() {
	(cin >> h >> w >> n);
	fill_n((char *)field, MAX_H*MAX_W, 'X');
	vector<pii> cheese(n + 1);

	REP(y, h){
		REP(x, w){
			char c;
			cin >> c;
			if(isdigit(c)){
				cheese[c-'0'] = {x + 1, y + 1};
			}else if(c == 'S'){
				cheese[0] = {x + 1, y + 1};
			}
			field[y + 1][x + 1] = c;
		}
	}

	//		REP(y, h + 2){
	//			REP(x, w + 2){
	//				cout << field[y][x];
	//			}
	//			cout << endl;
	//		}

	int res = 0;
	REP(i, n){
		int m = bfs(cheese[i], cheese[i+1]);
//		LOG("%d \n", m);
		res += m;
	}

	cout << res << endl;
}

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

int main(){
  int h,w,n;
  int x[10],y[10];
  string map[1000];
  int dmap[1000][1000];
  queue<int> qx,qy;
  int dis;

  cin >> h >> w >> n;

  for(int i=0;i<h;i++)cin >> map[i];
 
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(map[i][j] == 'S'){
	x[0] = j;
	y[0] = i;
      }
      if(map[i][j] != 'X' && map[i][j] != '.'){
	x[map[i][j] - '0'] = j;
	y[map[i][j] - '0'] = i;
      }
    }
  }

  dis = 0;
  for(int i=0;i<n;i++){
    while(!qx.empty())qx.pop();
    while(!qy.empty())qy.pop();
    for(int k=0;k<h;k++){
      for(int j=0;j<w;j++){
	dmap[k][j] = 10000000;
      }
    }
    dmap[y[i]][x[i]] = 0;
    qx.push(x[i]);
    qy.push(y[i]);

    while(!qx.empty()){
      if(qx.front()>0 && map[qy.front()][qx.front()-1] != 'X' && dmap[qy.front()][qx.front()-1] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()][qx.front()-1] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front()-1);
	qy.push(qy.front());
      }
      if(qy.front()>0 && map[qy.front()-1][qx.front()] != 'X' && dmap[qy.front()-1][qx.front()] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()-1][qx.front()] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front());
	qy.push(qy.front()-1);
      }
      if(qx.front()<w-1 && map[qy.front()][qx.front()+1] != 'X' && dmap[qy.front()][qx.front()+1] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()][qx.front()+1] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front()+1);
	qy.push(qy.front());
      }
      if(qy.front()<h-1 && map[qy.front()+1][qx.front()] != 'X' && dmap[qy.front()+1][qx.front()] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()+1][qx.front()] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front());
	qy.push(qy.front()+1);
      }
      qx.pop();
      qy.pop();
    }
    
    dis += dmap[y[i+1]][x[i+1]];
  }

  cout << dis << endl;
}

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

int h,w;
int sx,sy,gx,gy;
char rec[1000][1000];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int used[1000][1000];

bool check(int x, int y){
  return x >= 0 && y >= 0 && x <= w && y <= h && rec[y][x] != 'X' 
    && used[y][x] == 0;
}

int bfs(int p){
  queue<pair<int,int> > que;
  que.push(make_pair(sy,sx));
  for(int i=0; i<1000; i++)
    for(int j=0; j<1000; j++)
      used[i][j] = 0;
  
  while(!que.empty()){
    pair<int,int> pos = que.front();
    for(int i=0; i<4; i++){
      int yy = pos.first + dy[i];
      int xx = pos.second + dx[i];

         if(check(xx,yy)){
	que.push(make_pair(yy,xx));
	used[yy][xx] = used[pos.first][pos.second] + 1;
      }
         
      if(rec[yy][xx] == p + '0'){
	sx = xx;
	sy = yy;
	return used[sy][sx];
      }
    }
    que.pop();
  }
}

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

  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cin>>rec[i][j];
      if(rec[i][j] == 'S'){
	sy = i;
	sx = j;
      }
    }
  }

  int res = 0;

  for(int i=1; i<=n; i++) {
    res += bfs(i);
  }
  cout<<res<<endl;

  return 0;
  
}