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 <stdio.h>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <math.h>
#include <utility>
using namespace std;
typedef pair<int,int> P;
const int INF = (int)((unsigned int)-1>>1);
const int MAX_N = 100;

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

int H, W, N;
P s;
P c[9];
bool map_mat[1000][1000];

struct state{
    int d,to,y,x;
};

int main(){
    scanf("%d %d %d", &H, &W, &N);
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            char ch;
            cin >> ch;
            if (ch == 'S'){
                s = P(i,j);
            }else if ('1' <= ch && ch <= '9'){
                c[(int)(ch-'1')] = P(i,j);
            }
            if (ch == 'X'){
                map_mat[i][j] = false;
            }else{
                map_mat[i][j] = true;
            }
        }
    }

    queue<state> que;
    que.push((state){0, 0, s.first, s.second});
    bool itta[1000][1000];
    for(int i=0;i<H;i++)for(int j=0;j<W;j++) itta[i][j] = false;

    while(que.size()){
        state q = que.front(); que.pop();
        //printf("%d %d %d %d\n",q.d,q.to,q.y,q.x);
        if (c[q.to].second == q.x && c[q.to].first == q.y){
            q.to += 1;
            while(que.size()) que.pop();
            if (q.to == N){
                printf("%d\n", q.d);
                break;
            }else{
                for(int i=0;i<H;i++)for(int j=0;j<W;j++) itta[i][j] = false;
                itta[q.y][q.x] = true;
            }
        }
        for(int i=0;i<4;i++){
            int nextx = q.x+dx[i], nexty = q.y+dy[i];
            if(0<=nextx && nextx<W && 0<=nexty && nexty<H && map_mat[nexty][nextx] && !itta[nexty][nextx]){
                itta[nexty][nextx] = true;
                que.push((state){q.d+1, q.to, nexty, nextx});
            }
        }
    }

    return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1002
#define maxc 10
using namespace std;
struct point{
    int r,c;
};
char graph[maxn][maxn];
int len[maxn][maxn];
bool mark[maxn][maxn];
point node[maxc];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int main(void){
    int h,w,cheese,tr,tc,answer=0;
    scanf("%d%d%d",&h,&w,&cheese);
    memset(graph,0,sizeof(graph));
    memset(node,0,sizeof(node));
    for(int i=1;i<=h;i++) for(int j=1;j<=w;j++){
        do scanf("%c",&graph[i][j]);
        while(graph[i][j]==' ' || graph[i][j]=='\n');
        if(graph[i][j]>='0' && graph[i][j]<='9'){
            node[graph[i][j]-'0'].r=i;
            node[graph[i][j]-'0'].c=j;
        }
        else if(graph[i][j]=='S'){
            node[0].r=i;
            node[0].c=j;
        }
    }
    for(int cnt=0;cnt<cheese;cnt++){
        memset(len,0,sizeof(len));
        memset(mark,false,sizeof(mark));
        for(int i=0;i<=h+1;i++){mark[i][0]=true;mark[i][w+1]=true;}
        for(int j=0;j<=w+1;j++){mark[0][j]=true;mark[h+1][j]=true;}
        queue<point> q;
        q.push(node[cnt]);
        len[node[cnt].r][node[cnt].c]=0;
        point ongo,togo;
        while(!q.empty()){
            ongo=q.front();
            q.pop();
            if(mark[ongo.r][ongo.c]) continue;
            mark[ongo.r][ongo.c]=true;
            if(ongo.r==node[cnt+1].r && ongo.c==node[cnt+1].c){
                answer+=len[ongo.r][ongo.c];
                break;
            }
            for(int i=0;i<4;i++){
                togo.r=ongo.r+dir[i][0];togo.c=ongo.c+dir[i][1];
                if(mark[togo.r][togo.c]==false && graph[togo.r][togo.c]!='X'){
                    len[togo.r][togo.c]=len[ongo.r][ongo.c]+1;
                    q.push(togo);
                }
            }
        }
    }
    printf("%d\n",answer);
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define fi first
#define se second
static const int INF = 1e9;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
string board[1001];
int d[1001][1001];
int h, w, n;
pair<int, int> point[10];//fi=y se=x
int ans = 0;
bool flag;
//???????????¢?´¢
void bfs(void){
	rep(i, n){//??????????????¨??´?????????
		int starty = point[i].fi, startx = point[i].se;//start
		int endy = point[i + 1].fi, endx = point[i + 1].se;//end
		queue<pair<int, int> > q;
		q.push(make_pair(starty, startx));
		rep(i, h) rep(j, w) d[i][j] = INF;
		d[starty][startx] = 0;
		flag = false;
		while(!q.empty()){
			pair<int, int> now;
			now = q.front(); q.pop();
			rep(j, 4){
				int y = now.fi + dy[j];
				int x = now.se + dx[j];
				if(y < 0 || h <= y || x < 0 || w <= x) continue;
				if(d[y][x] == INF && board[y][x] != 'X'){
					d[y][x] = d[now.fi][now.se] + 1;
					q.push(make_pair(y, x));
				}
				if(y == endy && x == endx){
					flag = true;
					ans += d[y][x];
					break;
				}
			}
			if(flag == true) break;
		}
	}
	return;
}

int main(void){
	cin >> h >> w >> n;
	rep(i, h){
		cin >> board[i];
	}

	rep(i, h) rep(j, w){
		if(board[i][j] == 'S'){
			point[0].fi = i; point[0].se = j;
		}else if ('1' <= board[i][j] && board[i][j] <= '9'){
			int tmp = board[i][j] - '0';
			point[tmp].fi = i; point[tmp].se = j;
		}
	}
	bfs();
	cout << ans << endl;
	return 0;
}