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<utility>
typedef std::pair<int,int> PP;
int H, W, N;
int sh, sw;
char tar[9] = { '1','2','3','4','5','6','7','8','9' };
char HW[1000][1000];
int cnt = 0;
const int INF = 1 << 30;
int ans;
int tx, ty;
int D[1000][1000];
void solve(int h, int w) {
	std::queue<std::pair<int,int>> q;
	q.push(std::make_pair(h, w));
	for (int a = 0; a < H; a++) {
		for (int b = 0; b < W; b++) {
			D[a][b] = INF;
		}
	}
	D[h][w] = 0;
	while (q.size()) {
		std::pair<int, int> p = q.front();
		q.pop();
		if (HW[p.first][p.second] == tar[cnt]) {
			ans += D[p.first][p.second];
			tx = p.first;
			ty = p.second;
			return;
		}
		int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
		for (int i = 0; i < 4; i++) {
			int ux = p.first + dx[i];
			int uy = p.second + dy[i];
			if (0 <= ux&&ux < H && 0 <= uy&&uy < W&&D[ux][uy] == INF&&HW[ux][uy] != 'X') {
				q.push(std::make_pair(ux, uy));
				D[ux][uy] = D[p.first][p.second] + 1;
			}
		}
	}
	return;
}
int main() {
	std::cin >> H >> W >> N;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			std::cin >> HW[i][j];
			if (HW[i][j] == 'S') {
				sh = i;
				sw = j;
			}
		}
	}
	solve(sh, sw);
	for (int i = 0; i < N; i++) {
		cnt = i;
		solve(tx, ty);
	}
	std::cout << ans << "\n";
	return 0;
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int ctoi(char c){
    switch(c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    int d[MAX][MAX];
    int ans=0;
    int sx[9];
    int sy[9];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                sx[0]=i;
                sy[0]=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                sx[ctoi(in)]=i;
                sy[ctoi(in)]=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                isVisited[i][j]=false;
                d[i][j]=INF;
            }
        }
        que.push(P(sx[k],sy[k]));
        d[sx[k]][sy[k]]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==P(sx[k+1],sy[k+1]))   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.second+dy[l];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]==INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[sx[k+1]][sy[k+1]];
    }
    
    cout<<ans<<endl;
    
    return 0;
}

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 D[1002][1002];
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));
   memset(D,0,sizeof(D));
		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;
}

C++: #include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int H,W,N;
char map[1001][1001];
int visit[1001][1001];
struct node{
	int x,y,ph,time;
}s;
void bfs(){
	queue<node>q;
	while(!q.empty())q.pop();
	q.push(s);
	int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
	while(!q.empty()){
		node ne=q.front();q.pop();
		for(int i=0;i<4;i++){
			node no;
			no.x=ne.x+dx[i];
			no.y=ne.y+dy[i];
			no.time=ne.time;
			no.ph=ne.ph;
			if(no.x>=0&&no.x<H&&no.y>=0&&no.y<W&&map[no.x][no.y]!='X'){
				no.time++;
				//printf("map[%d][%d],time=%d\n",no.x,no.y,no.time);				
				if((int)map[no.x][no.y]==s.ph+48){
					s.x=no.x;
					s.y=no.y;
					s.ph++;
					s.time=no.time;
					return ;					
				}
				if(map[no.x][no.y]=='.'){
					map[no.x][no.y]='X';
					visit[no.x][no.y]=1;
				}
				q.push(no);
			}
		}
	}
}
int main(void){
	while(scanf("%d",&H)!=EOF&&scanf("%d%d",&W,&N)){
		for(int i=0;i<H;i++)
		for(int j=0;j<W;j++){
			cin>>map[i][j];
			if(map[i][j]=='S'){
				s.x=i,s.y=j,s.ph=1,s.time=0;
			}
		}
		for(int i=0;i<N;i++){
			memset(visit,0,sizeof(visit));
			bfs();
				for(int i=0;i<H;i++)
				for(int j=0;j<W;j++)
				if(visit[i][j])map[i][j]='.';	
		}
		printf("%d\n",s.time);
	}
}