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

using namespace std;

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

const int INF = 100000000;

char map[1005][1005];
int flag[1005][1005];
int H,W,N;
int cheese;
int sx,sy;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main()
{
	queue<RAT> que;
	int tx,ty;
	scanf("%d %d %d",&H,&W,&N);
	for(int i=0;i<H;i++)
	{
		scanf("%s",map[i]);
		for(int j=0;j<W;j++)
			if(map[i][j] == 'S')
			{
				sx = i;
				sy = j;
			}
	}
	
	que.push(RAT(P(sx,sy),P(1,0)));
	cheese = 1;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			flag[i][j] = INF;
	for(;;)
	{
		RAT rat = que.front();
		que.pop();
		if(rat.second.first == N+1)
		{
			printf("%d\n",rat.second.second);
			break;
		}
		if(cheese > rat.second.first)
			continue;
		if(cheese < rat.second.first)
		{
			cheese = rat.second.first;
			for(int i=0;i<H;i++)
				for(int j=0;j<W;j++)
					flag[i][j] = INF;
		}
		for(int i=0;i<4;i++)
		{
			tx = rat.first.first + dx[i];
			ty = rat.first.second + dy[i];
			if(tx >= 0 && tx < H && ty >= 0 && ty < W && map[tx][ty] != 'X' && flag[tx][ty] != 0)
			{
				if(rat.second.first == map[tx][ty]-48)
				{
					que.push(RAT(P(tx,ty),P(rat.second.first+1,rat.second.second+1)));
					flag[tx][ty] = 0;
				}
				else
				{
					que.push(RAT(P(tx,ty),P(rat.second.first,rat.second.second+1)));
					flag[tx][ty] = 0;
				}
			}
		}
	}
	return 0;	
}

C++: #if 0
#cflags(-std=c++14 -Wall)
#endif
#include<iostream>
template<typename T>
T input(std::istream& os = std::cin){T t;os >> t;return t;}

#include<vector>
#include<string>
#include<queue>
#include<numeric>

struct pos{
  int x, y;
  template<typename T>
  auto operator[](T&& t)const{return std::forward<T>(t)[y][x];}
};
template<typename F>
struct itr{
  int r;
  std::pair<pos, int> t;
  F shortest;
  itr& operator++(){++r;return *this;}
  int& operator*(){t = shortest(r, t.first.x, t.first.y);return t.second;}
  bool operator==(const itr& other)const{return r == other.r;}
  bool operator!=(const itr& other)const{return !(*this == other);}
};
template<typename F>
itr<F> make_itr(const pos& p, F&& f){return ++itr<F>{0, {p, 0}, f};}
template<typename F>
itr<F> make_itr(int r, F&& f){return itr<F>{r, {}, f};}

int main(){
  const auto H = input<int>();
  const auto W = input<int>();
  const auto N = input<int>();
  const std::vector<std::string> data = [H]{
    std::vector<std::string> data;
    data.reserve(H);
    for(int i = 0; i < H; ++i)
      data.emplace_back(input<std::string>());
    return data;
  }();
  const std::vector<pos> poss = [&]{
    std::vector<pos> poss(10);
    for(int j = 0; j < H; ++j)
      for(int i = 0; i < W; ++i)
        if(data[j][i] == 'S')
          poss[0] = {i, j};
        else if('1' <= data[j][i] && data[j][i] <= '9')
          poss[data[j][i] - '0'] = {j, i};
    return poss;
  }();
  auto shortest = [&](int rank, int i, int j){
    std::vector<std::vector<bool>> flags(H, std::vector<bool>(W));
    std::queue<std::pair<pos, int>> q;
    q.push({{i, j}, 0});
    while(true){
      const auto& d = q.front();
      const auto& p = d.first;
      if(p[data] == rank+'0')
        return q.front();
      p[flags] = true;
      auto add = [&](const pos& po){
        if(!po[flags])
          if(po[data] != 'X')
            q.push({po, d.second+1});
          else
            p[flags] = true;
      };
      for(int a = -1; a <= 1; a += 2)
        if(0 <= p.x + a && p.x + a < W)
          add(pos{p.x+a, p.y});
      for(int b = -1; b <= 1; b += 2)
        if(0 <= p.y + b && p.y + b < H)
          add(pos{p.x, p.y+b});
      p[flags] = true;
      q.pop();
    }
    return q.front();
  };
  std::cout << std::accumulate(make_itr(poss[0], shortest), make_itr(N+1, shortest), 0) << std::endl;
}

C++: #include<iostream>
#include<queue>
#include<string>
using namespace std;
	int a[1005][1005];
	int b[1005][1005];
	string moji[1005];
int main(){
	queue<int> q1;
	int x[15];
	int y[15];
	int e=0;
	int c=0;
	int d=0;
	string g;
	int i=0;
	int j=0;
	int k=0;
	int l=0;
	int s=0;
	int n=0;
	
	for(i=0;i<1000;i++){
		for(j=0;j<1000;j++){
			a[i][j]=10;
			b[i][j]=0;
		}
	}
	g=".123456789XS";
	cin>>e;
	cin>>c;
	cin>>d;
	for(i=0;i<e;i++){
		cin>>moji[i];
	}
	for(i=0;i<e;i++){
		for(j=0;j<c;j++){
			if(moji[i][j]==g[0]){
				a[i][j]=0;
			}else if(moji[i][j]==g[10]){
				a[i][j]=10;
			}else if(moji[i][j]==g[11]){
				a[i][j]=0;
				x[0]=i;
				y[0]=j;
			}else if(moji[i][j]==g[1]){
				a[i][j]=0;
				x[1]=i;
				y[1]=j;
			}else if(moji[i][j]==g[2]){
				a[i][j]=0;
				x[2]=i;
				y[2]=j;
			}else if(moji[i][j]==g[3]){
				a[i][j]=0;
				x[3]=i;
				y[3]=j;
			}else if(moji[i][j]==g[4]){
				a[i][j]=0;
				x[4]=i;
				y[4]=j;
			}else if(moji[i][j]==g[5]){
				a[i][j]=0;
				x[5]=i;
				y[5]=j;
			}else if(moji[i][j]==g[6]){
				a[i][j]=0;
				x[6]=i;
				y[6]=j;
			}else if(moji[i][j]==g[7]){
				a[i][j]=0;
				x[7]=i;
				y[7]=j;
			}else if(moji[i][j]==g[8]){
				a[i][j]=0;
				x[8]=i;
				y[8]=j;
			}else if(moji[i][j]==g[9]){
				a[i][j]=0;
				x[9]=i;
				y[9]=j;
			}
		}
	}
	for(i=0;i<d;i++){
		k=x[i];
		l=y[i];
		for(j=0;j<e*c;j++){
			if(k==x[i+1] && l==y[i+1]){
				break;
			}
			if(a[k+1][l]!=10 && b[k+1][l]==0){
				b[k+1][l]=b[k][l]+1;
				q1.push (k+1);
				q1.push (l);
			}
			if(a[k][l+1]!=10 && b[k][l+1]==0){
				b[k][l+1]=b[k][l]+1;
				q1.push (k);
				q1.push (l+1);
			}
			if(a[k][l-1]!=10 && b[k][l-1]==0){
				b[k][l-1]=b[k][l]+1;
				q1.push (k);
				q1.push (l-1);
			}
			if(a[k-1][l]!=10 && b[k-1][l]==0){
				b[k-1][l]=b[k][l]+1;
				q1.push (k-1);
				q1.push (l);
			}
			k=q1.front();
			q1.pop();
			l=q1.front();
			q1.pop();
		}
		s=s+b[k][l];
		n=q1.size();
		for(j=0;j<n;j++){
			q1.pop();
		}
		for(j=0;j<1000;j++){
			for(k=0;k<1000;k++){
				b[j][k]=0;
			}
		}
	}
	cout<<s<<endl;
}