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 <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
typedef struct cheese {
    P p;
    int hd;
    cheese(P p, int hd) : p(p), hd(hd) {}
} cheese;

const int INF = 1e8;
const int MAX_N = 1010;
int m, n, total;
char map[MAX_N][MAX_N];
int tm[MAX_N][MAX_N];
vector<cheese> che;

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

int bfs(int sx, int sy, int ex, int ey) {
    queue<P> que;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            tm[i][j] = INF;
    que.push(P(sx, sy));
    tm[sx][sy] = 0;
    
    while (que.size() > 0) {
        P p = que.front();
        que.pop();
        if (p.first == ex && p.second == ey) return tm[ex][ey];
        
        for (int i = 0; i < 4; i++) {
            int nx = p.first+dx[i], ny = p.second+dy[i];
            if (nx >= 0 && nx < m && ny >=0 && ny < n && map[nx][ny] != 'X' && tm[nx][ny] == INF) {
                que.push(P(nx, ny));
                tm[nx][ny] = tm[p.first][p.second]+1;
            }
        }
    }
    return -1;
}

bool cmp(cheese a, cheese b) {
    return a.hd < b.hd;
}

int main() {
    cin >> m >> n >> total;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'S') {
                sx = i;
                sy = j;
            }
            if (map[i][j] > '0' && map[i][j] <= '9')
                che.push_back(cheese(P(i, j), map[i][j]-'0'));
        }
    sort(che.begin(), che.end(), cmp);
    int sum = bfs(sx, sy, che[0].p.first, che[0].p.second);
    for (vector<cheese>::iterator it = che.begin(); it < che.end()-1; it++) {
        int sx = it->p.first, sy = it->p.second;
        int ex = (it+1)->p.first, ey = (it+1)->p.second;
        sum += bfs(sx, sy, ex, ey);
    }
    cout << sum << endl;
    return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX = 1001;
const int INF = (1<<20);
typedef pair<int,int> P;
typedef pair<int,P> PP;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
char grid[MAX][MAX];
int cost[MAX][MAX];
int H,W,N;
vector<PP> V;
P f,t;

void init(){
  for(int i = 1; i <= H; i++)
    for(int j = 1; j <= W; j++)
      cost[i][j] = INF;

}

void input(){
  for(int i = 1; i <= H; i++)
    for(int j = 1; j <= W; j++){
      cin >> grid[i][j];
      PP pp;

      if(grid[i][j] == 'S' || '0' <= grid[i][j] && grid[i][j] <= '9'){
	if(grid[i][j] == 'S') pp.first = 0;
	else pp.first = grid[i][j] - '0';
	
	pp.second = P(i,j);
	V.push_back(pp);
      }
    }
}


bool isIn(P p){
  return 0 < p.first && p.first<= H && 0 < p.second && p.second <= W;
}
void solve(P p){

  int n = cost[p.first][p.second];

  for(int i = 0; i < 4; i++){
    P next = p;
    next.first += dy[i];
    next.second += dx[i];
    if(grid[next.first][next.second] != 'X' && cost[next.first][next.second] > n+1 && isIn(next)){
	cost[next.first][next.second] = n+1;
	if(next != t) solve(next);
    }
  }
}

P find(int n){
  for(int i = 0; i < V.size(); i++)
    if(V[i].first == n) return V[i].second;

}

int main(){

  cin >> H >> W >> N;

  input();
  sort(V.begin(),V.end());
  
  int ans = 0;
 
  for(int i = 1; i <= N; i++){
    init();
    f = find(i-1), t = find(i);
    cost[f.first][f.second] = 0;
    solve(f);
    ans += cost[t.first][t.second]; 
  }

  cout << ans << endl;
  return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
struct k{
	int x,y,c;
};
queue<k> q;
int p[1000][1000],m[1000][1000];
int main(void) {
	k z,z1;
	char d;
	int v=1,h,w,n,i,j,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	cin >> h >> w>>n;
	for (i = 0; i != w + 2; i++) {
		for (j = 0; j != h + 2; j++){
			p[j][i] = 99;
			m[j][i]=0;
		}
	}for (i = 1; i != w + 1; i++) {
		for (j = 1; j != h + 1; j++){
			m[j][i]=99;
		}
	}
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++){
			cin >> d;
			switch(d){
				case 'S':
					z.x=j;
					z.y=i;
					z.c=0;
					p[i][j]=-1;
					break;
				case '.':
					p[i][j]=-1;
					break;
				case 'X':
					p[i][j]=99;
					break;
				case '1':
					p[i][j]=1;
					break;
				case '2':
					p[i][j]=2;
					break;
				case '3':
					p[i][j]=3;
					break;
				case '4':
					p[i][j]=4;
					break;
				case '5':
					p[i][j]=5;
					break;
				case '6':
					p[i][j]=6;
					break;
				case '7':
					p[i][j]=7;
					break;
				case '8':
					p[i][j]=8;
					break;
				case '9':
					p[i][j]=9;
					break;
			}
		}
	}
	q.push(z);
	while(!q.empty()){
			z=q.front();
			q.pop();
			if(m[z.y][z.x]==v)
				continue;
			if(p[z.y][z.x]==v){
				if(p[z.y][z.x]==n)
					break;
				while(!q.empty())
					q.pop();
				q.push(z);
				v++;
				//printf("%d %d %d\n",z.x,z.y,z.c);
			}
		//	cout<<p[z.y][z.x]<<" "<<z.y<<" "<<z.x<<endl;
			m[z.y][z.x]=v;
			for(i=0;i!=4;i++){
				if(p[z.y+dy[i]][z.x+dx[i]]!=99/*&&z.x+dx[i]!=v&&z.y+dy[i]!=v*/){
					z1.x=z.x+dx[i];
					z1.y=z.y+dy[i];
					z1.c=z.c+1;
					q.push(z1);
				}
			}
	}
	cout <<z.c<< endl;
}

C++: #include <iostream>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <queue>
#include <cstdio>

using namespace std;

int H,W;
int N;
char a[1005][1005];
bool b[1005][1005];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

struct Node
{
    int x;
    int y;
    int deep;
};

struct Node Temp;

void bfs(int n)
{
    queue<struct Node> t;
    t.push(Temp);
    while (t.size())
    {
        Temp=t.front();t.pop();
        int x=Temp.x;
        int y=Temp.y;
        int d=Temp.deep;
        if(a[x][y]==n+48)
        {
			break;
        }
        if(b[x][y])
            b[x][y]=false;

        for(int i=0;i<4;i++)
        {
            int x1=x+dx[i];
            int y1=y+dy[i];
            if (x1>=0 && x1<W && y1>=0 && y1<H && a[x1][y1]!='X' && b[x1][y1])
            {
                Temp.x=x1;
                Temp.y=y1;
                Temp.deep=d+1;
                t.push(Temp);
            }
        }
    }
}

int main()
{
	while(cin>>H>>W>>N)
	{
    int i,j;
    int sx=0,sy=0;
    for(j=0;j<H;j++)
        for(i=0;i<W;i++)
        {
            cin>>a[i][j];
            if (a[i][j]=='S')
            {
                sx=i;
                sy=j;
            }
        }
    Temp.x=sx;
    Temp.y=sy;
    Temp.deep=0;

    for(int k=1;k<=N;k++)
    {
        memset(b,true, sizeof(b));
        bfs(k);
    }
    cout<<Temp.deep<<endl;
	}
    return 0;
}