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

#define INF (1<<30)

typedef pair<int,int> P;

queue<P> que;
char map[1000][1000];
int vst[1000][1000];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int H,W,N,sx,sy,sum=0;

int main() {
	scanf("%d %d %d",&H,&W,&N);
	for(int i=0;i<H;i++) {
		scanf("%s",map[i]);
		char *ptr=strchr(map[i],'S');
		if(ptr!=NULL) sx=ptr-map[i],sy=i;
	}
	que.push(P(sx,sy));
	for(int i=1;i<=N;i++) {
		for(int j=0;j<H;j++) {
			for(int k=0;k<W;k++) {
				vst[j][k]=INF;
			}
		}
		vst[sy][sx]=0;
		while(!que.empty()) {
			P p=que.front();
			que.pop();
			if(map[p.second][p.first]==i+'0') {
				sum+=vst[p.second][p.first];
				while(!que.empty()) que.pop();
				que.push(P(p.first,p.second));
				sx=p.first,sy=p.second;
				break;
			}
			for(int j=0;j<4;j++) {
				int nx=p.first+dx[j],ny=p.second+dy[j];
				if(map[ny][nx]!='X'&&vst[ny][nx]==INF) {
					vst[ny][nx]=vst[p.second][p.first]+1;
					que.push(P(nx,ny));
				}
			}
		}
	}
	printf("%d\n",sum);
}

C++: #include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

struct Data{
	Data(int arg_row,int arg_col,int arg_cost){
		row = arg_row;
		col = arg_col;
		cost = arg_cost;
	}
	bool operator<(const struct Data &arg) const{
		return cost > arg.cost;
	}
	int row,col,cost;
};

int H,W,N;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int min_dist[1000][1000];
char base_map[1000][1001];
Info info[10];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

int calc(int goal){

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++)min_dist[row][col] = BIG_NUM;
	}

	min_dist[info[goal-1].row][info[goal-1].col] = 0;

	priority_queue<Data> Q;
	Q.push(Data(info[goal-1].row,info[goal-1].col,0));

	int adj_row,adj_col;

	while(!Q.empty()){

		if(Q.top().row == info[goal].row && Q.top().col == info[goal].col){
			return Q.top().cost;
		}else if(Q.top().cost > min_dist[Q.top().row][Q.top().col]){
			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){
				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || base_map[adj_row][adj_col] == 'X')continue;

				if(min_dist[adj_row][adj_col] > Q.top().cost+1){
					min_dist[adj_row][adj_col] = Q.top().cost+1;
					Q.push(Data(adj_row,adj_col,min_dist[adj_row][adj_col]));
				}
			}

			Q.pop();
		}
	}

}

int main(){

	scanf("%d %d %d",&H,&W,&N);

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){
			if(base_map[row][col] >= '1' && base_map[row][col] <= '9'){
				info[base_map[row][col]-'0'].set(row,col);
			}else if(base_map[row][col] == 'S'){
				info[0].set(row,col);
			}
		}
	}

	int ans = 0;

	for(int i = 1; i <= N; i++)ans += calc(i);

	printf("%d\n",ans);

	return 0;
}

C++: 


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>

using namespace std;
typedef long long ll;
int mod(ll a){
    int c=a%1000000007;
    if(c>=0)return c;
    else return c+1000000007;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000/*10^8*/

/////////////////////////////////


struct ball{
    int i,j,count;
};
int h,w,n;
char room[101][101];
i_i goal[11];
bool done[1001][1001];

int di[4]={1,0,-1,0};
int dj[4]={0,1,0,-1};

int  dfs(int k){
    for(int i=0;i<=h-1;i++)for(int j=0;j<=w-1;j++)done[i][j]=false;
    int si=goal[k].first,sj=goal[k].second;
    int gi=goal[k+1].first,gj=goal[k+1].second;
    queue<ball> q;
    ball ba;ba.i=si;ba.j=sj;ba.count=1;
    q.push(ba);
    bool whi=true;
    int ans=0;
    while(whi){
        ball pos=q.front();q.pop();
        done[pos.i][pos.j]=true;
        for(int i=0;i<=3;i++){
            int ii=pos.i+di[i],jj=pos.j+dj[i];
            if(0<=ii&&ii<=h-1&&0<=jj&&jj<=w-1&&room[ii][jj]!='X'&&done[ii][jj]==false){
                if(ii==gi&&jj==gj)ans=pos.count,whi=false;
                else{
                    ba.i=ii;ba.j=jj;ba.count=pos.count+1;
                    q.push(ba);
                }
            }
        }
    }
    return ans;
}

int main(){
    cin>>h>>w>>n;
    for(int i=0;i<=h-1;i++)cin>>room[i];
    for(int i=0;i<=h-1;i++)for(int j=0;j<=w-1;j++){
        if(room[i][j]=='.');
        else if(room[i][j]=='X');
        else if(room[i][j]=='S')goal[0]=make_pair(i,j);
        else goal[room[i][j]-'0']=make_pair(i,j);
    }
    int ans=0;
    for(int i=0;i<=n-1;i++){
        ans+=dfs(i);
    }
    
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

#define INF (1 << 26)

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

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

	cin >> H >> W >> N;

	vector<string> D(H);

	for (int i = 0; i < H; i++)
		cin >> D[i];

	int route = 0;

	for (int i = 1; i <= N; i++)
	{
		queue<pair<int, int> > que;

		vector<vector<int> > memo(H, vector<int>(W, INF));

		char start;

		if (i == 1)
		{
			start = 'S';
		}
		else
		{
			start = i + 48;
		}

		pair<int, int> start_;

		for (int j = 0; j < H; j++)
		{
			for (int k = 0; k < W; k++)
			{
				if (D[j][k] == start)
				{
					start_.first = k;
					start_.second = j;
				}
			}
		}

		que.push(start_);

		memo[start_.second][start_.first] = route;

		while (que.size())
		{
			pair<int, int> place = que.front(); que.pop();

			int x, y;

			x = place.first;
			y = place.second;

			for (int dir = 0; dir < 4; dir++)
			{
				if (0 <= x + dx[dir] && x + dx[dir] < W && 0 <= y + dy[dir] && y + dy[dir] < H)
				{
					if (D[y + dy[dir]][x + dx[dir]] != 'X' && memo[y + dy[dir]][x + dx[dir]] == INF)
					{
						place.first = x + dx[dir];
						place.second = y + dy[dir];

						que.push(place);

						memo[y + dy[dir]][x + dx[dir]] = memo[y][x] + 1;

						if (D[y + dy[dir]][x + dx[dir]] - 48 == i)
						{
							route += memo[y][x] + 1;

							goto Exit;
						}
					}
				}
			}
		}

	Exit:;
	}

	cout << route << endl;

	return 0;
}