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;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

#define MAX_H 1000
#define MAX_W 1000

int h, w;
char board[MAX_H][MAX_W];

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

inline bool is_in_range(const int y, const int x) {
    return 0 <= y && y < h && 0 <= x && x < w;
}

int bfs(const pii &start, const pii &end) {
    bool visited[MAX_H][MAX_W] = { false };
    visited[start.first][start.second] = true;
    queue<pair<int, pii> > que;
    que.push(make_pair(0, start));
    while(!que.empty()) {
        int stp = que.front().first;
        pii now = que.front().second;
        que.pop();
        REP(i, 4) {
            int ny = now.first + dy[i], nx = now.second + dx[i];
            if(is_in_range(ny, nx) && board[ny][nx] != 'X' && !visited[ny][nx]) {
                visited[ny][nx] = true;
                if(ny == end.first && nx == end.second) return stp + 1;
                else {
                    que.push(make_pair(stp + 1, make_pair(ny, nx)));
                }
            }
        }
    }
    return -1;
}

int main() {
    int n;
    cin >> h >> w >> n;
    vpii loc(n + 1);
    REP(j, h) {
        REP(i, w) {
            char c;
            cin >> c;
            if(c == 'S') {
                loc[0].first = j;
                loc[0].second = i;
            }
            else if('1' <= c && c <= '9') {
                int idx = c - '0';
                loc[idx].first = j;
                loc[idx].second = i;
            }
            board[j][i] = c;
        }
    }
    int ans = 0;
    REP(i, n) {
        ans += bfs(loc[i], loc[i + 1]);
    }
    cout << ans << "\n";

    return 0;
}

C++: #include<iostream>
#include<queue>

const int MAXW = 1

C++: #include "bits/stdc++.h"

using namespace std;

//#define int long long

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

#define pb push_back
#define VDEL(v, n) v.erase(v.begin() + (n))
#define ALL(v) v.begin(), v.end()

#define INTMAX 2147483647
#define INF 200000000
#define TINT(str) atoi(str.c_str())
#define TSTR(num) to_string(num)

using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VII = vector<vector<int>>;

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

PII goal[10];
char k[1000][1000];
int fx, fy;
int H,W;

int BFS(int x, int y)
{
    int cost[1000][1000];

    REP(i, H)
    {
        REP(h, W)
        {
            cost[i][h] = INF;
        }
    }

    cost[fx][fy] = 0;

    queue<PII> q;

    q.push(make_pair(fx, fy));

    while(!q.empty())
    {
        PII now = q.front();
        q.pop();
        int nx = now.first;
        int ny = now.second; 

        REP(i, 4)
        {
            if(nx + dx[i] >= H ||
            nx + dx[i] < 0) continue;
            if(ny + dy[i] >= W || 
            ny + dy[i] < 0) continue;

            if(nx + dx[i] == x &&
            ny + dy[i] == y)
            {
                return cost[nx][ny] + 1;
            }

            if(k[nx + dx[i]][ny + dy[i]] != 'X')
            {
                if(cost[nx + dx[i]][ny + dy[i]] > 
                cost[nx][ny])
                {
                    cost[nx + dx[i]][ny + dy[i]] =
                        cost[nx][ny] + 1;
                    q.push(make_pair(nx + dx[i], ny + dy[i]));
                }
            }
            else continue;
        }
    }

    return -1;
}

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

    char str[1001];
    REP(h, H)
    {
        scanf("%s", str);
        REP(w, W)
        {
            k[h][w] = str[w];
            if(k[h][w] == 'S')
            {
                fx = h;
                fy = w;
            }
            if(k[h][w] != '.' &&
                k[h][w] != 'X')
            {
                goal[k[h][w] - '1'] = make_pair(h, w);
            }
        }
    }
    int ans = 0;

    REP(i, N)
    {
        ans += BFS(goal[i].first, goal[i].second);
        fx = goal[i].first;
        fy = goal[i].second;
    }

    cout << ans << endl;

    return 0;
}

C++: #include<iostream>
#include<queue>
using namespace std;
int W,H,N,A[10][2];
static char s[1000+2][1000+2];
const int INF=1000000000;
int muki[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int f(int x){
	queue<int> que;
	static int cost[1000+2][1000+2];
	for(int i=0;i<1002;i++)for(int j=0;j<1002;j++)cost[i][j]=INF;
	cost[A[x][0]][A[x][1]]=0;
	que.push(A[x][0]*1002+A[x][1]);
	while(cost[A[x+1][0]][A[x+1][1]]==INF){
		int c=que.front();
		int nY=c%1002,nX=(c-nY)/1002;
		for(int i=0;i<4;i++){
			if(s[nX+muki[i][0]][nY+muki[i][1]]!='X'&&cost[nX+muki[i][0]][nY+muki[i][1]]==INF){
				cost[nX+muki[i][0]][nY+muki[i][1]]=cost[nX][nY]+1;
				que.push((nX+muki[i][0])*1002+nY+muki[i][1]);
			}
		}
		que.pop();
	}
	return cost[A[x+1][0]][A[x+1][1]];
}

int main(){
	for(int i=0;i<1002;i++)for(int j=0;j<1002;j++)s[i][j]='X';
	scanf("%d%d%d",&W,&H,&N);
	for(int i=1;i<W+1;i++){
		scanf("%s",&s[i]);
		for(int j=H;j>0;j--)s[i][j]=s[i][j-1];
		for(int j=1;j<H+1;j++){
			if(s[i][j]=='S'){A[0][0]=i; A[0][1]=j;}
			for(int k=1;k<N+1;k++){
				if(s[i][j]==k+48){A[k][0]=i; A[k][1]=j;}
			}
		}
	}
	int ans=0;
	for(int i=0;i<N;i++){
		ans+=f(i);
	}
	printf("%d\n",ans);
}