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 "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

//#define int long long
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

struct P
{
	int x, y, t;
	P(int x, int y, int t) :x(x), y(y), t(t){}
	P() :P(-1, -1,-1) {}
};

string A[1000];
int cnt[1000][1000];
int H, W, N;

int solve(P sp)
{
	static const int dx[] = { 1,0,-1,0 };
	static const int dy[] = { 0,1,0,-1 };

	int ans = 0;
	rep(k, 1, N + 1)
	{
		queue<P> q;
		q.push(sp);
		while (true)
		{
			P tp = q.front(); q.pop();
			cnt[tp.y][tp.x] = k;
			if ((int)A[tp.y][tp.x] == ((int)'0' + k))
			{
				sp = P(tp.x, tp.y, 0);
				ans += tp.t;
				break;
			}

			rep(i, 0, 4)
			{
				P np(tp.x + dx[i], tp.y + dy[i], tp.t + 1);
				if (0 <= np.x&&np.x < W && 0 <= np.y&&np.y < H)
				{
					if (A[np.y][np.x] != 'X'&&cnt[np.y][np.x] < k)
					{
						q.push(np);
					}
				}
			}
		}
	}

	return ans;
}

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	P sp;
	cin >> H >> W >> N;
	rep(i, 0, H)
	{
		cin >> A[i];
		if (sp.x == -1)
		{
			rep(j, 0, SZ(A[i]))
			{
				if (A[i][j] == 'S')
				{
					sp = P(j, i, 0);
					break;
				}
			}
		}
	}
	cout << solve(sp) << endl;

	return 0;
}

C++: #include<map>
#include<queue>
#include<stdio.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define SIZE 1002
using namespace std;

typedef pair<int,int> P;

char mass[SIZE][SIZE];
int data[SIZE][SIZE];
int  dx[4]={1,0,-1,0};
int  dy[4]={0,1,0,-1};
int  sx,sy,gx,gy;
int  h,w,n;
int sum=0;

int bfs();

int main(){

  int i,j;

  cin>>h>>w>>n;

  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin>>mass[i][j];
    }
  }

  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(mass[i][j]=='S'){
	sx=j;
	sy=i;
	break;
      }
    }
  }
  for(int k=1;k<=n;k++){
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	if(mass[i][j]-'0'==k){
	  gx=j;
	  gy=i;
	}
      }
    }
    sum+=bfs();
    sx=gx;
    sy=gy;
  }

  /*
    for(i=0;i<h;i++){
    for(j=0;j<w;j++){
    printf("%2c",mass[i][j]);
    }
    printf("      ");
    for(j=0;j<w;j++){
    printf("%2d",data[i][j]);
    }
    cout<<endl;
    }                             */

  cout<<sum<<endl;
  
  return 0;
}
int bfs(){

  int i,j,now=0;
  queue<P> que;

  memset(data,-1,sizeof(data));

  que.push(P(sy,sx));
  data[sy][sx]=0;

  while(!que.empty()){

    P p=que.front();
    que.pop();

    if(p.first==gy && p.second==gx){
      return data[p.first][p.second];
    }

    for(i=0;i<4;i++){
      int nx=p.second+dx[i];
      int ny=p.first+dy[i];

      if(nx>=0 && nx<=w && ny>=0 && ny<=h && mass[ny][nx]!='X' && data[ny][nx]==-1){
	que.push(P(ny,nx));
	data[ny][nx]=data[p.first][p.second]+1;
      }
    }
   }
 return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> pii;

#define S 'S'
#define X 'X'

#define W_MAX 1000

char map[W_MAX][W_MAX];
bool visited[W_MAX][W_MAX];

int main(){
  int H, W, N;
  cin >> H >> W >> N;

  pii pos; //rat position

  for(int i=0; i<H; i++){
    getchar();
    for(int j=0; j<W; j++){
      scanf("%c", &map[i][j]);
      if(map[i][j]==S){
	pos = make_pair(i,j);
      }
    }
  }

  int dx[] = {0, -1, 0 ,1}; int dy[] = {-1, 0, 1, 0};
  int ans=0;
  int next = 1; //next target num

  while(next <= N){
    memset(visited, false, sizeof(visited));

    queue<pair<pii, int> > q; //<pos, depth>
    q.push(make_pair(pos, 0));

    while(true){
      pair<pii, int> p = q.front(); q.pop();
      bool found = false;
      visited[p.first.first][p.first.second] = true;
      for(int i=0; i<4; i++){
	int nx = p.first.first + dx[i], ny=p.first.second + dy[i];
	if(nx>=0 && nx<H && ny>=0 && ny<W && !visited[nx][ny]){
	  visited[nx][ny]= true;
	  if(map[nx][ny] == '0' + next){
	    found = true;
	    pos = make_pair(nx, ny);
	    break;
	  } else if(map[nx][ny] != X && map[nx][ny] != S){
	    q.push(make_pair(make_pair(nx, ny), p.second+1));
	  }
	}
      }
      if(found){
	ans += p.second+1;
	next++;
	break;
      }
    }
  }

  cout << ans << 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 D[1002][1002];
int 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(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;
			P.push(S);
		}
		}
	}
	while(1){
		l++;
		
		if(l==4) {
			l=0;
			P.pop();
		}
		S=P.front();
	//	A[S.y][S.x]=1;
		S.x+=x[l];
		S.y+=y[l];
		S.Z++;
		if(s[S.y][S.x]=='X'||S.y==h||S.x==w||S.x==-1||S.y==-1){
		continue;
		}
		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;
}