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 <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <sstream>
using namespace std;
typedef pair<int,int> P;

const int max_n=1000+10;
int h,w,n,sx,sy,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;
char c[max_n][max_n];

void bfs(int x,int y,int m){
	if(m>n)return;
	queue<P> q;
	memset(d,0,sizeof(d));
	q.push(P(x,y));
	d[x][y]=1;
	while(!q.empty()){
		P p=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int tx=p.first+dx[i],ty=p.second+dy[i];
			if(c[tx][ty]=='0'+m){
				ans+=d[p.first][p.second];
				bfs(tx,ty,m+1);
				return;
			}
			if(tx>=0 && tx<h && ty>=0 && ty<w && c[tx][ty]!='X' && !d[tx][ty]){
				q.push(P(tx,ty));
				d[tx][ty]=d[p.first][p.second]+1;
			}
		}
	}
}

int main(){
    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++){
            cin>>c[i][j];
            if(c[i][j]=='S'){sx=i;sy=j;}
        }
    bfs(sx,sy,1);
    cout<<ans<<endl;
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;

char field[1000][1001];
int d[1000][1000];
int h, w, n;
int sx, sy;
int dx[4] = { 0,0,-1,1 }, dy[4] = { -1,1,0,0 };
int ret;
queue<P> que;

void solve() {
	char c = '1';
	while (c < '1' + n) {
		Loop(i, h) {
			Loop(j, w) {
				d[i][j] = -1;
			}
		}
		que.push(P(sx, sy));
		d[sx][sy] = ret;
		while (que.size()) {
			P p = que.front(); que.pop();
			Loop(k, 4) {
				int a = p.first + dx[k], b = p.second + dy[k];
				if (a >= 0 && a <= h - 1 && b >= 0 && b <= w - 1
					&& field[a][b] != 'X' && d[a][b] == -1) {
					d[a][b] = d[p.first][p.second] + 1;
					if (field[a][b] == c) {
						ret = d[a][b];
						sx = a; sy = b;
						while (que.size()) que.pop();
						c++;
						break;
					}
					else que.push(P(a, b));
				}
			}
		}
	}

}

int main() {
	cin >> h >> w >> n;
	Loop(i, h) {
		Loop(j, w) {
			cin >> field[i][j];
			if (field[i][j] == 'S') { sx = i;sy = j; }
		}
	}
	ret = 0;
	solve();
	cout << ret << endl;
	return 0;
}

C++: #include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <string>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <cstdlib>
#include <stack>
#include <time.h>
using namespace std;
typedef long long LL;
const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1.0); //M_PI;
const int maxn = 1001;
char g[maxn][maxn];
int vis[maxn][maxn];
int row , col , n;
int d[4][2] = {0 , 1 , 1 , 0 , 0 , -1 , -1 , 0};

struct factory{
    int x , y , index;
}fac[11];

bool cmp(struct factory tp1 , struct factory tp2)
{
    return tp1.index <= tp2.index;
}
struct node{
    int x , y;
    int sum;
};

int bfs(int si , int sj , int ei , int ej)
{
    queue<struct node> q;
    while(!q.empty()) q.pop();
    memset(vis , 0 , sizeof(vis));
    struct node tp1 , tp2 , tp3;
    tp1.x = si;
    tp1.y = sj;
    tp1.sum = 0;
    q.push(tp1);
    vis[si][sj] = 1;
    //cout << si << " " << sj << endl;
    while(!q.empty())
    {
        tp2 = q.front();
        q.pop();
        int curx = tp2.x;
        int cury = tp2.y;
        if(curx == ei && cury == ej){
            return tp2.sum;
        }
        for(int i = 0 ; i < 4 ; i ++){
            int xx = curx + d[i][0];
            int yy = cury + d[i][1];
//cout << xx << " " << yy << endl;
            if(xx < 0 || xx >= row || yy < 0 || yy >= col || g[xx][yy] == 'X' || vis[xx][yy]) continue;
            tp3.x = xx;
            tp3.y = yy;
            tp3.sum = tp2.sum + 1;
            vis[xx][yy] = 1;
            q.push(tp3);
        }
        //cout << endl;
    }
    return -1;
}

int main()
{

    #ifdef DoubleQ
    freopen("in.txt" , "r" , stdin);
    #endif
    while(cin >> row >> col >> n){
        string s;
        int len = 0;
        for(int i = 0 ; i < row ; i ++){
            cin >> s;
            for(int j = 0 ; j < col ; j ++){
                g[i][j] = s[j];
                if(s[j] == 'S'){
                    fac[len].x = i;
                    fac[len].y = j;
                    fac[len++].index = 0;
                }
                else if(s[j] >= '0' && s[j] <= '9'){
                    fac[len].x = i;
                    fac[len].y = j;
                    fac[len++].index = (int)(s[j] - '0');
                }
            }
        }
        sort(fac , fac + len , cmp);
        int res = 0;
        for(int i = 1 ; i < len ; i ++){
            g[fac[i-1].x][fac[i-1].y] = '.';
            char tp = g[fac[i].x][fac[i].y];
            g[fac[i].x][fac[i].y] = '.';

            int mid = bfs(fac[i-1].x , fac[i-1].y , fac[i].x , fac[i].y);
            res += mid;
            g[fac[i].x][fac[i].y] = tp;
        }
        cout << res  << endl;
    }
}

C++: #include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct PP{
	int x;
	int y;
	int Z;
	int c;
};
char s[1002][1002],C[11]={"0123456789"};
int A[1002][1002],d;
int main(){
	PP S;
	queue<PP> P;
	int  w,h;
	int d=0,i=0,j=0,l=-1;
	int x[4]={ 1, 0,-1,0};
	int y[4]={ 0 ,1,0,-1};
	scanf("%d %d %d",&h,&w,&d);
	memset(A,0,sizeof(A));
		for(i=0;i<h;i++){
		scanf("%s",s[i]);
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
		if(s[i][j]=='S'){
			S.x=j;
			S.y=i;
			S.Z=0;
			S.c=1;
			A[S.y][S.x]=1;
			P.push(S);
		}
		}
	}
	while(1){
		l++;
		
		if(l==4) {
			l=0;
			P.pop();
		}
		S=P.front();

		S.x+=x[l];
		S.y+=y[l];
		S.Z++;
		if(A[S.y][S.x]==1||s[S.y][S.x]=='X'||S.y==h||S.x==w||S.x==-1||S.y==-1){
		continue;
		}
				A[S.y][S.x]=1;
		if(C[S.c]==s[S.y][S.x]){
				S.c++;
				if(S.c==d+1){
				break;
				}
				while(!P.empty()){
				P.pop();
				
				}
			memset(A,0,sizeof(A));
			l=-1;
		

		} 
		P.push(S);
	}
	printf("%d\n",S.Z);
	return 0;
}