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 <cstdio>
#include <queue>
using namespace std;


#define INF 1 << 30
#define min(a,b) ((a) > (b) ? (b) : (a))
typedef struct P {
	int x, y;
	P(){}
	P(int i, int j) {
		x = i;
		y = j;
	}
	P operator+(const P r) {
		return{ x + r.x,y + r.y };
	}
	bool operator==(const P r) {
		return x == r.x && y == r.y;
	}
}P;

int H, W, N;
char map[1001][1001];
bool dp[1001][1001];
P mv[4] = { {-1,0},{0,-1},{0,1},{1,0} };
P fac[10];
queue<P> q;

void ini() {
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			dp[i][j] = false;
		}
	}
}

inline bool ok(P p) {
	return p.x >= 0 && p.x < H && p.y >= 0 && p.y < W && !dp[p.x][p.y] && map[p.x][p.y] != 'X';
}

int road(P s, P e) {
	ini();
	q = queue<P>();
	q.push(s);
	int l = 0;
	while (true) {
		l++;
		int ql = q.size();
		if (ql == 0) break;
		for (int i = 0; i < ql; i++) {
			P f = q.front();
			q.pop();
			for (int j = 0; j < 4; j++) {
				P p = f + mv[j];
				if (ok(p)) {
					if (p == e) {
						return l;
					}
					q.push(p);
					dp[p.x][p.y] = true;
				}
			}
		}
	}
	return -1;
}

int main(){
	scanf("%d%d%d", &H, &W, &N);
	for (int i = 0; i < H; i++) {
		scanf("%s", map[i], 1001);
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (map[i][j] == 'S') {
				fac[0] = P(i, j);
			}
			else if (map[i][j] > '0' && map[i][j] <= '9') {
				fac[(unsigned)(map[i][j] - '0')] = P(i, j);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans += road(fac[i], fac[i + 1]);
	}
	printf("%d\n", ans);

	return 0;
}

C++: #include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAX 1000
int y[MAX][MAX];
int x[MAX][MAX];
int px[10];
int py[10];
int main(){
	memset(y,127,sizeof(y));
	char T[12]={'.','1','2','3','4','5','6','7','8','9','S','X'};
	int n,m,c,d,sum;
	string S;
	sum=0;
	cin>>n>>m>>c;
	for(int i=0;i<n;i++){
		cin>>S;
		for(int j=0;j<m;j++){
			for(int k=0;k<12;k++){
				if(S[j]==T[k]){
					x[i][j]=k;
					if(k==10){
						px[0]=i;
						py[0]=j;
					}
					if(k>=1 && k<=9){
						px[k]=i;
						py[k]=j;
					}
				}
			}
		}
	}
	for(int i=1;i<=c;i++){
		memset(y,127,sizeof(y));
		y[px[i-1]][py[i-1]]=0;
		for(int j=0;j<n*m/4+2;j++){
			for(int k=0;k<n;k++){
				for(int l=0;l<m;l++){
					if(k>=1){
						if(x[k-1][l]!=11){
							y[k-1][l]=min(y[k-1][l],y[k][l]+1);
						}
					}
					if(l>=1){
						if(x[k][l-1]!=11){
							y[k][l-1]=min(y[k][l-1],y[k][l]+1);
						}
					}
					if(x[k+1][l]!=11){
						y[k+1][l]=min(y[k+1][l],y[k][l]+1);
					}
					if(x[k][l+1]!=11){
						y[k][l+1]=min(y[k][l+1],y[k][l]+1);
					}
				}
			}
			if(y[px[i]][py[i]]<1000000){
				goto Exit;
			}
		}
		Exit:;
		sum += y[px[i]][py[i]];
	}
	cout<<sum<<endl;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

struct Point {
  int x,y;
  Point(double x, double y) : x(x), y(y){}
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H, W, N;
  cin >> H >> W >> N;
  char c[H][W];
  deque<Point> q;
  for (int i = 0; i < H; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < W; j++) {
      c[i][j] = s[j];
      if (c[i][j] == 'S') q.push_back(Point(j, i));
    }
  }
  int sum = 0;
  int dx[] = {1, -1, 0, 0};
  int dy[] = {0, 0, 1, -1};
  for (int i = 1; i <= N; i++) {
    int vis[H][W]{};
    int d[H][W]{};
    Point p = q.front();
    vis[p.y][p.x] = 1;
    while (true) {
      Point t = q.front();
      q.pop_front();
      if (c[t.y][t.x] == (char)(i + '0')) {
        q.clear();
        q.push_back(t);
        sum += d[t.y][t.x];
        break;
      }
      for (int j = 0; j < 4; j++) {
          int nx = t.x + dx[j];
					int ny = t.y + dy[j];
          if (nx >= 0 && nx < W && ny >= 0 && ny < H) {
            if (vis[ny][nx] == 0 && c[ny][nx] != 'X') {
              vis[ny][nx] = 1;
              d[ny][nx] = d[t.y][t.x] + 1;
              q.push_back(Point(nx, ny));
            }
          }
      }
    }
  }
  cout << sum << "\n";
  return 0;
}

C++: #include<stdio.h>
#include<iostream>
using namespace std;
#include<queue>
#include<string.h>
struct PP{
	int x;
	int y;
	int Z;
	int c;
};
char s[1000][1000],C[11]={"0123456789"};
int D[1000][1000];
int A[1000][1000],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;
			P.push(S);
		}
		}
	}
	while(1){
		l++;
		//printf("a");
		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++;
		//printf("%d\n",A[S.y][S.x]);
		if(A[S.y][S.x]==1) continue;
		//printf("b");
		if(s[S.y][S.x]=='X'||S.y==h||S.x==w||S.x==-1||S.y==-1){
			S.x-=x[l];
			S.y-=y[l];
		}
		else if(s[S.y][S.x]=='.'){}
		else{
			if(C[S.c]==s[S.y][S.x]){
				S.c++;
				if(S.c==d+1){
				printf("%d\n",S.Z);
				break;
				}
				while(!P.empty()){
				P.pop();
				
				}
			memset(A,0,sizeof(A));
			l=-1;
			}

		} 
		P.push(S);
	}
	return 0;
}

C++: #include <iostream>
#include <queue>
using namespace std;

int h,w,n;
char map[1000][1000];
struct P{
  int t, i,j;
  P(){t=0;i=0;j=0;};
  P(int time,int x, int y){t=time;i=x;j=y;};
};
int cal(int a, int b){
  char start = a==0?'S':'0'+a;
  bool flags[1000][1000];
  int si,sj;
  for( int i=0;i<h;i++ )
    for( int j=0;j<w;j++ ){
      flags[i][j] = false;
      if( map[i][j] == start ){
	si=i; sj=j;
      }
    }

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

  queue<P> q;
  q.push(P(0, si, sj));
  while( !q.empty() ){
    P p = q.front(); q.pop();
    if( p.i < 0 || p.j < 0 ) continue;
    if( p.i >=h || p.j>=w )  continue;

    if( flags[p.i][p.j] ) continue;
    flags[p.i][p.j] = true;

    if( map[p.i][p.j] == '0' + b )
      return p.t;
    if( map[p.i][p.j] == 'X' )
      continue;

    p.t++;
    for( int d=0;d<4;d++ ){
      int ni = p.i+dx[d], nj=p.j+dy[d];
      //      if( flags[ni][nj] ) continue;
      q.push(P(p.t, ni, nj) );
    }
  }

  return -1;
}


int main(){
  cin >> h >> w >> n;
  for(int i=0;i<h;i++ )
    for( int j=0;j<w;j++ )
      cin >> map[i][j];

  int time=0, r;
  for( int i=0;i<n;i++ ){
    r = cal( i, i+1);
    time += r;
    //    cout << i << " => " << (i+1) << "\t | " << r << endl;
  }
  cout << time << endl;

  return 0;
}