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 fi first
#define se second

using namespace std;
typedef pair<int, int> pii;
const int inf=1e9;
const pii d[]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int H, W, dis[1000][1000];
char N, fld[1000][1000];
pii start;

int bfs(char num){
    queue<pii> qu;
    qu.push(start);

    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            dis[i][j]=inf;
        }
    }

    dis[start.fi][start.se]=0;
    while(!qu.empty()){
        pii now=qu.front(); qu.pop();
        int h=now.fi, w=now.se;
        if(fld[h][w]==num){
            start=make_pair(h, w);
            return dis[h][w];
        }

        for(int k=0; k<4; k++){
            pii nx=make_pair(h+d[k].fi, w+d[k].se);
            if(!(0<=nx.fi&&nx.fi<H&&0<=nx.se&&nx.se<W)) continue;//is_field?
            if(fld[nx.fi][nx.se]=='X') continue;
            if(dis[nx.fi][nx.se]!=inf) continue;
            dis[nx.fi][nx.se]=dis[h][w]+1;
            qu.push(nx);
        }
    }

}

void solve(){

    int ans=0;
    for(char c='1'; c<=N; c++){
        ans+=bfs(c);
    }

    cout<< ans<< endl;
    return;
}
int main(){

    cin>> H>> W>> N;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin>> fld[i][j];
            if(fld[i][j]=='S'){
                start=make_pair(i, j);
            }
        }
    }

    solve();

    return 0;
}

C++: #include<stdio.h>
#include<queue>
using namespace std;
int bfs[1000][1000];
bool field[1000][1000];
pair<int,int> point[10];
char str[1001];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	int ret=0;
	for(int i=0;i<a;i++){
		scanf("%s",str);
		for(int j=0;j<b;j++){
			if(str[j]=='X')field[i][j]=false;
			else field[i][j]=true;
			switch(str[j]){
				case 'S':
					point[0]=make_pair(i,j);
					break;
				case '1':
					point[1]=make_pair(i,j);
					break;
				case '2':
					point[2]=make_pair(i,j);
					break;
				case '3':
					point[3]=make_pair(i,j);
					break;
				case '4':
					point[4]=make_pair(i,j);
					break;
				case '5':
					point[5]=make_pair(i,j);
					break;
				case '6':
					point[6]=make_pair(i,j);
					break;
				case '7':
					point[7]=make_pair(i,j);
					break;
				case '8':
					point[8]=make_pair(i,j);
					break;
				case '9':
					point[9]=make_pair(i,j);
					break;
			}
		}
	}
	for(int i=0;i<c;i++){
		for(int k=0;k<a;k++)
			for(int j=0;j<b;j++)
				bfs[k][j]=-1;
		bfs[point[i].first][point[i].second]=0;
		queue<pair<int ,int> > Q;
		Q.push(point[i]);
		while(Q.size()){
			int row=Q.front().first;
			int col=Q.front().second;
			if(row>0&&field[row-1][col]&&bfs[row-1][col]==-1){
				bfs[row-1][col]=bfs[row][col]+1;
				Q.push(make_pair(row-1,col));
			}
			if(col>0&&field[row][col-1]&&bfs[row][col-1]==-1){
				bfs[row][col-1]=bfs[row][col]+1;
				Q.push(make_pair(row,col-1));
			}
			if(row<a-1&&field[row+1][col]&&bfs[row+1][col]==-1){
				bfs[row+1][col]=bfs[row][col]+1;
				Q.push(make_pair(row+1,col));
			}
			if(col<b-1&&field[row][col+1]&&bfs[row][col+1]==-1){
				bfs[row][col+1]=bfs[row][col]+1;
				Q.push(make_pair(row,col+1));
			}
			Q.pop();
		}
		ret+=bfs[point[i+1].first][point[i+1].second];
	}
	printf("%d\n",ret);
}

C++: #include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

/*
 貪欲
 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B
 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか
 ?
 */

/*
 DP
 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)
 */

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll h,w,n;
	cin>>h>>w>>n;
	vector<vector<char>> m(h,vector<char>(w));
	REP(i,h) REP(j,w) cin>>m[i][j];
	ll ret=0;
	REP(i,n) {
		vector<vector<ll>> dir(h,vector<ll>(w,INF));
		queue<P> q;
		REP(j,h) REP(k,w) {
			if(i==0) {
				if(m[j][k]=='S') {
					dir[j][k]=0;
					q.push(P(j,k));
				}
			} else {
				if(m[j][k]=='0'+i) {
					dir[j][k]=0;
					q.push(P(j,k));
				}
			}
		}
		while(!q.empty()) {
			P p=q.front();
			q.pop();
			ll dx[]={1,0,-1,0};
			ll dy[]={0,1,0,-1};
			REP(j,4) {
				ll nx=p.first+dx[j];
				ll ny=p.second+dy[j];
				if(nx>=0&&nx<h&&ny>=0&&ny<w&&m[nx][ny]!='X'&&dir[nx][ny]==INF) {
					q.push(P(nx,ny));
					dir[nx][ny]=dir[p.first][p.second]+1;
				}
			}
		}
		REP(j,h) REP(k,w) {
			if(m[j][k]=='1'+i) ret+=dir[j][k];
		}
	}
	cout<<ret<<endl;
}

C++: #include<iostream>
#include<queue>
#define fi first
#define se second
using namespace std;
int dy[4]={0,0,-1,1},dx[4]={1,-1,0,0};
int X,Y,N;
typedef pair<int,int> P;
char field[1000][1001];
P time[1000][1001];
typedef struct point{
    int y,x,t,n;
}point;
int bfs(int,int);
int main(){
    cin>>Y>>X>>N;
    int rep;
    for(int i=0;i<Y;i++)cin>>field[i];
    for(int i=0;i<Y;i++){
        for(int j=0;j<X;j++){
            time[i][j].fi=time[i][j].se=-1;
        }
    }
    for(int i=0;i<Y;i++){
        bool flag=false;
        for(int j=0;j<X;j++){
            if(field[i][j]=='S'){
                rep=bfs(i,j);
                flag=true;
                break;
            }
        }
        if(flag)break;
    }
    cout<<rep<<endl;
    return 0;

}

int bfs(int y,int x){
    point start={y,x,0,0};
    queue<point>Q;
    Q.push(start);
    while(Q.size()){

        point a;
        a=Q.front();
        Q.pop();
        if(a.y<0 || a.y>=Y ||a.x<0||a.x>=X)continue;

        if(field[a.y][a.x]=='X')continue;

        if(a.n+1==field[a.y][a.x]-'0')a.n++;

        if(a.n>time[a.y][a.x].se){
            time[a.y][a.x].fi=a.t;
            time[a.y][a.x].se=a.n;
        }else if(a.n==time[a.y][a.x].se&&a.t<time[a.y][a.x].fi){
            time[a.y][a.x].fi=a.t;
        }else continue;

        if(a.n==N){
            return a.t;
        }


        for(int i=0;i<4;i++){
            point next={a.y+dy[i],a.x+dx[i],a.t+1,a.n};
            Q.push(next);
        }


    }



}