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++: #define _CRT_SECURE_NO_WARNINGS

#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

int h, w, n;
vector<pair<int, int>> map;
vector<pair<int, int>> List;

queue<int> q;

int loop(int start, int end) {
	for (int i = 0; i < h * w; i++) {
		map[i].second = 0;
	}
	while (!q.empty()) {
		q.pop();
	}
	queue<int> tmp;
	q.push(start);
	for (int i = 1; true; i++) {
		while (!q.empty()) {
			int front = q.front();
			q.pop();
			map[front].second = -1;

			if (front / w != 0) {
				if (map[front - w].first != 'X' && map[front - w].second != -1) {
					if (front - w == end) {
						return i;
					}
					map[front - w].second = -1;
					tmp.push(front - w);
				}
			}

			if (front / w != h - 1) {
				if (map[front + w].first != 'X' && map[front + w].second != -1) {
					if (front + w == end) {
						return i;
					}
					map[front + w].second = -1;
					tmp.push(front + w);
				}
			}

			if (front % w != 0) {
				if (map[front - 1].first != 'X' && map[front - 1].second != -1) {
					if (front - 1 == end) {
						return i;
					}
					map[front - 1].second = -1;
					tmp.push(front - 1);
				}
			}

			if (front % w != w - 1) {
				if (map[front + 1].first != 'X' && map[front + 1].second != -1) {
					if (front + 1 == end) {
						return i;
					}
					map[front + 1].second = -1;
					tmp.push(front + 1);
				}
			}
		}
		swap(q, tmp);
	}
}

void set_map() {
	pair<int, int> map_p;
	pair<int, int> list_p;
	for (int i = 0; i < h; i++) {
		string tmp;
		cin >> tmp; // map状況
		for (int j = 0; j < w; j++) {
			map_p.first = tmp[j]; // map状況
			map_p.second = 0; //queのための値
			map.push_back(map_p);
			if (map_p.first != 'X' && map_p.first != '.') {
				list_p.first = i * w + j; // map上の何番目なのか
				if (map_p.first == 'S') { // 何番目のゴールなのか
					list_p.second = 0;
				} else {
					list_p.second = map_p.first - '0';
				}
				vector<pair<int, int>>::iterator ite = List.begin();
				int k = 0;
				for (; k < List.size(); ite = std::next(ite, 1), k++) {
					if (list_p.second < List[k].second) {
						List.insert(ite, list_p);
						break;
					}
				}
				if (k == List.size()) {
					List.push_back(list_p);
				}
			}
		}
	}
}

int main(int argc, string *argv){

	cin >> h >> w >> n;
	set_map();
	int count = 0;
	for (int i = 1; i < List.size(); i++) {
		count += loop(List[i - 1].first, List[i].first);
	}
	cout << count << endl;
	return 0;
}

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

void zero();

struct p{
	int x, y, cnt;
};
int H, W, N;
int tizu[1001][1001];
bool flag[1001][1001] = { false };
int main(){
	queue<p> que;
	char a;
	char h[10] = "123456789";
	cin >> H >> W >> N;
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			cin >> a;
			if (a == 'S'){
				tizu[i][j] = 0;
				p temp;
				temp.x = j;
				temp.y = i;
				temp.cnt = 0;
				que.push(temp);
			}
			else if (a == 'X'){
				tizu[i][j] = -1;
			}
			else if (a == '.'){
				tizu[i][j] = 0;
			}
			else {
				for (int k = 0; k < 9; k++){
					if (h[k] == a){
						tizu[i][j] = k + 1;
					}
				}

			}
			//cout << tizu[i][j];
		}
		//cout << endl;
	}
	int max = 1;
	int step = 0;
	while (!que.empty()){
		p temp = que.front();
		que.pop();
		if (tizu[temp.y][temp.x] == max){
			max++;
			while (!que.empty()) que.pop();
			if (max - 1 == N) {
				max = temp.cnt;
				break;
			}
			zero();
		}
		flag[temp.y][temp.x] = true;
		for (int i = 0; i < 4; i++){
			int dx[4] = { 1, -1, 0, 0 };
			int dy[4] = { 0, 0, 1, -1 };
			int yy = temp.y + dy[i];
			int xx = temp.x + dx[i];
			if (flag[yy][xx] != true){
				if (yy > -1 && xx > -1 && yy < H && xx < W && tizu[yy][xx] != -1){
					p tt;
					tt.y = yy;
					tt.x = xx;
					tt.cnt = temp.cnt + 1;
					que.push(tt);
				}
			}
		}
	}
	cout << max << endl;
	return 0;
}
void zero(){
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			flag[i][j] = false;
		}
	}
}

C++: #include <iostream>
#include <queue>
#define INF		10000000
using namespace std;
typedef pair<int, int> P;

int h, w, n;
int count = 0;
char masu[1000][1000];
int d[1000][1000];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int sgx[10], sgy[10];

void bfs(int a){
	queue<P> que;
	que.push(P(sgx[a], sgy[a]));
	d[sgy[a]][sgx[a]] = 0;
	while(que.size()){
		P p = que.front();
		que.pop();
		if(p.first == sgx[a+1] && p.second == sgy[a+1]) break;
		for(int i = 0; i < 4; i++){
			int nx = p.first+dx[i], ny = p.second+dy[i];
			if(0 <= nx && 0 <= ny && nx < w && ny < h && masu[ny][nx] != 'X' && d[ny][nx] == INF){
				que.push(P(nx,ny));
				d[ny][nx] = d[p.second][p.first]+1;
			}
		}
	}
	count += d[sgy[a+1]][sgx[a+1]];
}

void solve(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 1000; j++){
			for(int k = 0; k < 1000; k++){
				d[j][k] = INF;
			}
		}
		bfs(i);
	}
	cout << count << endl;
}

int main(){
	for(int i = 0; i < 1000; i++)
		for(int j = 0; j < 1000; j++) masu[i][j] = 'X';
		
	cin >> h >> w >> n;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> masu[i][j];
			if(masu[i][j] == 'S'){
				sgx[0] = j;
				sgy[0] = i;
			}
			for(int k = 1; k < n+1; k++){
				if(masu[i][j] == '0'+k){
					sgx[k] = j;
					sgy[k] = i;
				}
			}
		}
	}
	solve();
}