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<cstring>
using namespace std;
int m,n;
int che=1;
int k;
struct node{
  int x,y;
};
char mape[1111][1111];
int d[1111][1111];
int r[10];
queue<node> q;
int da[]={0,1,0,-1};
int db[]={1,0,-1,0};
void bfs(){
  while(!q.empty()&&che<=k){
    node nn;
    int x=q.front().x;
    int y=q.front().y;
    q.pop();
    if(mape[x][y]==che+'0'){
      mape[x][y]='.';
      r[che++]=d[x][y];
      memset(d,-1,sizeof(d));
      d[x][y]=r[che-1];
      while(!q.empty())q.pop();
      nn.x=x;
      nn.y=y;
      q.push(nn);
      return;
    }
    for(int i=0;i<4;i++)
      if(x+da[i]>=0&&x+da[i]<m&&y+db[i]>=0&&y+db[i]<n&&mape[x+da[i]][y+db[i]]!='X'&&d[x+da[i]][y+db[i]]==-1){
	int w=x+da[i];
	int e=y+db[i];
	d[w][e]=d[x][y]+1;
	nn.x=w;
	nn.y=e;
	q.push(nn);
      }
  }
}
int main(){
  cin>>m>>n>>k;
  while(!q.empty())q.pop();
  node nn;
  memset(d,-1,sizeof(d));
  for(int i=0;i<m;i++)
    for(int j=0;j<n;j++){
      cin>>mape[i][j];
      if(mape[i][j]=='S'){
	nn.x=i;
	nn.y=j;
	d[i][j]=0;
	q.push(nn);
	mape[i][j]='.';
      }
    }
  while(che<=k)bfs();
  cout<<r[k]<<"\n";
}

C++: #include <iostream>
#include <string>
#include <queue>
int a[1005][1005];
bool tf[1005][1005];
int p[10][2];
int dirc[4][2] = {{-1 , 0} , {1 , 0} , {0 , -1} , {0 , 1}};
int w , h , n;

int bfs(int st_y , int st_x , int en_y , int en_x){
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            tf[i][j] = false;
        }
    }
    tf[st_y][st_x] = true;    
    int x , y , step;
    std::queue < std::tuple<int , int , int> > que;
    que.push(std::make_tuple(st_y , st_x , 0));
    while(!que.empty()){
        std::tie(y , x , step) = que.front();
        que.pop();
        if(x == en_x && y == en_y){
            return step;
        }
        for(int i = 0;i < 4;i++){
            int ny = y + dirc[i][0] , nx = x + dirc[i][1];
            if(nx >= 0 && nx < w && ny >= 0 && ny < h && a[ny][nx] >= 0 && tf[ny][nx] == false){
                tf[ny][nx] = true;
                que.push(std::make_tuple(ny , nx , step + 1));
            }
        }
    }
    return 0;
}
int main(){
    std::cin >> h >> w >> n;
    for(int i = 0;i < h;i++){
        std::string s;
        std::cin >> s;
        for(int j = 0;j < w;j++){
            switch(s[j]){
                case 'S':
                    a[i][j] = 0 , p[0][0] = i , p[0][1] = j;
                    break;
                case '.':
                    a[i][j] = 0;
                    break;
                case '1':
                    a[i][j] = 1; p[1][0] = i , p[1][1] = j;
                    break;
                case '2':
                    a[i][j] = 2; p[2][0] = i , p[2][1] = j;
                    break;
                case '3':
                    a[i][j] = 3; p[3][0] = i , p[3][1] = j;
                    break;
                case '4':
                    a[i][j] = 4; p[4][0] = i , p[4][1] = j;
                    break;
                case '5':
                    a[i][j] = 5; p[5][0] = i , p[5][1] = j;
                    break;
                case '6':
                    a[i][j] = 6; p[6][0] = i , p[6][1] = j;
                    break;
                case '7':
                    a[i][j] = 7; p[7][0] = i , p[7][1] = j;
                    break;
                case '8':
                    a[i][j] = 8; p[8][0] = i , p[8][1] = j;
                    break;
                case '9':
                    a[i][j] = 9; p[9][0] = i , p[9][1] = j;
                    break;
                default:
                    a[i][j] = -1;
                    break;
            }
        }
    }

    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += bfs(p[i - 1][0] , p[i - 1][1] , p[i][0] , p[i][1]);
    }
    std::cout << ans << "\n";
    return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

const double inf = (int)1e8;

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

    vector<string> field(h);
    int d[h][w];
    int mx, my;
    for(int i=0; i< h; i++){
        cin >> field[i];
        for(int j=0; j < field[i].size(); j++) if(field[i][j] == 'S'){mx = i; my = j; field[i][j] = '.';}
    }
    int count = 0;
    for(int i = 1; i <= n; i++){
        for(int j=0; j< h; j++)for(int k=0; k < w; k++) d[j][k] = inf;
        queue<pair<int, int>> q;
        q.push(make_pair(mx, my));
        d[mx][my] = 0;
        while(q.size()){
            pair<int, int> p = q.front(); q.pop();
            if(field[p.first].substr(p.second, 1) == to_string(i)){count += d[p.first][p.second]; mx = p.first; my = p.second; break;}
            int dx[4] = {1, 0, -1, 0};
            int dy[4] = {0, 1, 0, -1};
            for(int j=0; j < 4; j++){
                int nx = p.first+dx[j], ny = p.second+dy[j];
                if(0 <= nx && nx < h && 0 <= ny && ny < w && field[nx][ny] != 'X' && d[nx][ny] == inf){
                    q.push(make_pair(nx, ny));
                    d[nx][ny] = d[p.first][p.second] + 1;
                }
            }
        }
    }
    cout << count << endl;
}