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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
 
 
 
int main()
{
 
    queue < pair<int, int> > q;
    pair<int, int> p;
 
 
 
    char **m;
    char c[10] = { "123456789" };
    int **f;
	bool flg = false;
    int n, k, i, i1, c1, i2, sum = 0;
    cin >> n;
    cin >> k;
    cin >> c1;
 
    m = new char *[n + 2];
    f = new int *[n + 2];
 
    for (i = 0; i < n + 2; i++){
        m[i] = new char[k + 2];
        f[i] = new int[k + 2];
    }
 
    for (i = 1; i <= n; i++){
        for (i1 = 1; i1 <= k; i1++){
            cin >> m[i][i1];
        }
    }
 
    for (i = 0; i < n + 2; i++){
        for (i1 = 0; i1 < k + 2; i1++){
            if (i == 0 || i == n + 1){
                m[i][i1] = 'X';
            }
            else if (i1 == 0 || i1 == k + 1){
                m[i][i1] = 'X';
            }
        }
    }
 
    for (i = 1; i <= n; i++){
        for (i1 = 1; m[i][i1] != '\0'; i1++){
            if (m[i][i1] == 'S'){
                q.push(make_pair(i, i1));
            }
        }
    }
 
 
 
    pair<int, int> temp;
 
    temp = q.front();
 
    for (i = 0; i < c1; i++){

		if(!flg){
		for (i1 = 0; i1 < n + 2; i1++){
				for (i2 = 0; i2 < k + 2; i2++){
					if (i1 == 0 || i1 == n + 1){
						f[i1][i2] = 1;
					}
					else if (i2 == 0 || i2 == k + 1){
						f[i1][i2] = 1;
					}
					else
						f[i1][i2] = -1;
				}
		}
		flg = true;
		}

        f[temp.first][temp.second] = 0;
 
		while (!q.empty()){
            p = q.front();
            q.pop();
 
            int x[4] = { -1, 1, 0, 0 }, y[4] = { 0, 0, -1, 1 };
 
            for (int j = 0; j < 4; j++){
 
                //???????????´??????????´¢
                if (m[p.first + x[j]][p.second + y[j]] != 'X' && f[p.first + x[j]][p.second + y[j]] < 0){
                    q.push(make_pair(p.first + x[j], p.second + y[j]));
                    f[p.first + x[j]][p.second + y[j]] = f[p.first][p.second] + 1;
                }
            }
            //??´?????????????????????
            if (m[p.first][p.second] == c[i]){
                sum += f[p.first][p.second];
                temp = p;
                while (!q.empty()){
                    q.pop();
                }
                q.push(p);
                break;
			}
		}
	}
 
    cout << sum << endl;
 
    return 0;
}

C++: #include <iostream>
#include <string>
#include <queue>
#define INF 1e+9
using namespace std;

typedef pair<int,int> P;

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

int dist[1000][1000];
string field[1000];

int main(){
	int h,w,n,x,y,res = 0;
	cin >> h >> w >> n;
	for(int i = 0;i < h;i++){
		cin >> field[i];
		for(int j = 0;j < w;j++){
			if(field[i][j] == 'S'){
				x = i;
				y = j;
			}
		}
	}
	queue<P> que;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < h;j++){
			for(int k = 0;k < w;k++) dist[j][k] = INF;
		}
		que.push(P(x,y));
		for(int d = 0;;d++){
			int siz = que.size();
			if(!siz) break;
			for(int j = 0;j < siz;j++){
				P p = que.front();que.pop();
				int nx = p.first,ny = p.second;
				if(dist[nx][ny] < d) continue;
				if(field[nx][ny] == i + 1 + '0'){
					x = nx;
					y = ny;
					res += dist[nx][ny];
				}
				for(int k = 0;k < 4;k++){
					int nnx = nx + dx[k],nny = ny + dy[k];
					if(nnx >= 0 && nnx < h && nny >= 0 && nny < w && field[nnx][nny] != 'X' && dist[nnx][nny] > d + 1){
						dist[nnx][nny] = d + 1;
						que.push(P(nnx,nny));
					}
				}
			}
		}
	}
	cout << res << endl;
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> _P;
typedef pair<_P,int> P;
int W,H,N;
_P fact[11];
char map[1000][1001];
bool vst[1000][1000];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int bfs(int n) {
	memset(vst,0,sizeof(vst));
	char chr=(n<N?n+1+'0':'G');
	queue<P> que;
	que.push(P(fact[n],0));
	while(!que.empty()) {
		P p=que.front();que.pop();
		if(map[p.first.second][p.first.first]==chr) {
			return p.second;
		}
		for(int i=0;i<4;i++) {
			int nx=p.first.first+dx[i];
			int ny=p.first.second+dy[i];
			if(0>nx||nx>=W||0>ny||ny>=H)continue;
			if(map[ny][nx]=='X'||
				vst[nx][ny]==true)continue;
			vst[nx][ny]=true;
			que.push(P(_P(nx,ny),p.second+1));
		}
	}
}
int main() {
	scanf("%d %d %d",&W,&H,&N);
	for(int i=0;i<H;i++) {
		scanf("%s",map[i]);
	}
	for(int i=0;i<=N+1;i++) {
		for(int j=0;j<H;j++) {
			char *cp=strchr(map[i],i==0?'S':i==N+1?'G':i+'0');
			if(cp!=NULL) {
				fact[i].first=j;
				fact[i].second=(cp-map[i]);
				break;
			}
		}
	}
	int res=0;
	for(int i=0;i<=N;i++) {
		res+=bfs(i);
	}
	return res;
}

C++: #include <stdio.h>
#include <queue>

using namespace std;

typedef pair<int,int> P;

int h, w, n;
char field[100][101];
queue<P> qu;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int d[100][100];


void init(){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      d[i][j] = -1;
    }
  }
  queue<P> empty;
  swap(qu,empty);
}

int solve(){
  int hp = 1;
  int cnt;
  init();
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(field[i][j] == 'S'){
        qu.push(P(i,j));
        d[i][j] = 0;
      }
    }
  }
  while(qu.size()){
    P p = qu.front();
    qu.pop();
    int y = p.first;
    int x = p.second;
    if(hp == n + 1)
      return d[y][x];
    if(hp == field[y][x] - '0'){
      hp++;
      cnt = d[y][x];
      init();
      d[y][x] = cnt;
    }
    for(int i = 0; i < 4; i++){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(ny >= 0 && ny < h && nx >= 0 && nx < w && field[ny][nx] != 'X' && d[nx][ny] < 0){
        d[ny][nx] = d[y][x] + 1;
        qu.push(P(ny,nx));
        printf("%d \n", d[ny][nx]);
        printf("%d %d\n", ny, nx);
      }
    }
  }
  return 0;
}

int main(){
  scanf("%d %d %d", &h, &w, &n);
  for(int i = 0; i < h; i++){
    scanf("%s", field[i]);
  }
  printf("%d\n", solve() - 1);
  return 0;
}