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>

#define INF 1e9
#define MAX_H 1000
#define MAX_W 1000

using namespace std;

struct Cood {int x, y; };

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

char field[MAX_H][MAX_W + 1];
int d[MAX_H][MAX_W + 1];
queue<Cood> q;
int h, w, n;
int total_time = 0;

void init_bfs() {
    queue<Cood> new_q;
    swap(q, new_q);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            d[i][j] = INF;
        }
    }
}
/* current position (y, x) with current power 'current' & last cheeese target is 'last' */
int bfs(int sy, int sx, int target, int last) {
    init_bfs();
    int next_y, next_x;
    q.push(Cood{sx, sy});
    d[sy][sx] = 0;

    while (q.size()) {
        Cood current = q.front(); q.pop();
        if (field[current.y][current.x] == '0' + target) {
            total_time += d[current.y][current.x];
            if (target == last) {
                return total_time;
            } else {
                return bfs(current.y, current.x, target + 1, last);
            }
        }

        for (int i = 0; i < 4; ++i) {
            next_y = current.y + dy[i];
            next_x = current.x + dx[i];
            if (0 <= next_y && next_y < h && 0 <= next_x && next_x < w
                && field[next_y][next_x] != 'X' && d[next_y][next_x] == INF) {
                q.push(Cood{next_x, next_y});
                d[next_y][next_x] = d[current.y][current.x] + 1;
            }
        }
    }
}

int main() {
    //freopen("0558_1.in", "r", stdin);
    cin >> h >> w >> n;
    int sx, sy;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> field[i][j];
            if (field[i][j] == 'S') {
                sy = i, sx = j;
            }
        }
    }
    total_time = 0; // init
    cout << bfs(sy, sx, 1, n) << endl;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i ++)
#define COUNT(i, n) for(int i = 1; i <= n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define X first
#define Y second
#define P first
#define C second

using namespace std; 

typedef pair<int, int> pii;
typedef pair<pii, int> mouse;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

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

int main(void){
    int w, h, n, res = 0; cin >> h >> w >> n;
    vs m(h);
    rep(y, h) cin >> m[y];
    pii s;
    rep(y, h) rep(x, w) if(m[y][x] == 'S') s = mp(x, y);

    rep(i, n){
        queue<mouse> q;
        q.push(mp(s, 0));

        vector< vector<bool> > used(h);
        rep(y, h) used[y].resize(w);

        while(!q.empty()){
            mouse cur = q.front();
            q.pop();

            if(used[cur.P.Y][cur.P.X]) continue;
            used[cur.P.Y][cur.P.X] = true;

            if(m[cur.P.Y][cur.P.X] == i + 1 + '0'){
                res += cur.C;
                s = mp(cur.P.X, cur.P.Y);
                break;
            }

            rep(i, 4){
                mouse next = mp(mp(cur.P.X + dx[i], cur.P.Y + dy[i]), cur.C + 1);
                if(0 <= next.P.X && next.P.X < w &&
                   0 <= next.P.Y && next.P.Y < h &&
                   m[next.P.Y][next.P.X] != 'X') q.push(next);
            }
        }
    }

    cout << res << endl;

    return 0;
}

C++: #include<bits/stdc++.h>
#include<ctype.h>
#define int long long int
#define rep(a,b) for(int a=0;a<b;a++)
#define INF 1000006
using namespace std;

int tx[] = {1,0,-1,0};
int ty[] = {0,1,0,-1};
int w,h,che,sx,sy;
char bases;
int base[1003][1003],base2[1003][1003],memo[1003][1003];

int chee(int x,int y,int n){
    int ans=INF;
    if(memo[x][y]>0)return memo[x][y];
    else if(base[x][y]==n)return 0;
    else if(base[x][y]>=0){
        base[x][y]=-1;
        for(int i=0;i<4;i++){
            if(x+tx[i]>=0&&x+tx[i]<w&&y+ty[i]>=0&&y+ty[i]<h){
                ans = min(ans,chee(x+tx[i],y+ty[i],n)+1);
            }
        }base[x][y]=0;
    }
    if(ans!=INF)memo[x][y]=ans;
    return ans;
}
void sho(int b[1003][1003],int a[1003][1003]){
    rep(i,1003){
        rep(j,1003){
            b[i][j]=a[i][j];
        }
    }
}

signed main(){
    int zx[20],zy[20];
    cin >> h >> w >> che;
    rep(f,h){
        rep(s,w){
            cin >> bases;
            switch(bases){
                case 'S':sx=s;sy=f;
                case '.':base[s][f]=0;
                break;
                case 'X':base[s][f]=-1;
                break;
                default:{base[s][f]=bases - '0';
                        zx[base[s][f]]=s;
                        zy[base[s][f]]=f;
                        }

            }
        }
    }
    sho(base2,base);
    int ans=0;
    ans+=chee(sx,sy,1);
    for(int i=2;i<=che;i++){
        sho(base,base2);
        fill((int*)memo,(int*)(memo+1003),0);
        ans+=chee(zx[i-1],zy[i-1],i);
    }
    cout << ans << endl;
return 0;
}