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<map>
#include<queue>
#include<string>
using namespace std;
int main(){
  int h,w,n,px,py,ans;
  int field[100][100];
  int ch[100][100];
  while(cin >>h>>w>>n){
    ans = 0;
    string s;
    for(int i=0; i<h; i++){
      cin >>s;
      for(int j=0; j<w; j++){
	if(s[j] == 'S'){px = j;py = i;field[j][i] = 0;}
	else if(s[j]>='1' && s[j]<='9'){field[j][i] = s[j]-'0';}
	else if(s[j] == 'X'){field[j][i] = -1;}
	else{field[j][i] = 0;}
      }
    }
    for(int i=0; i<n; i++){
      queue<pair<int,int> > play;
      play.push(make_pair(px,py));
      for(int j=0; j<h; j++){
	for(int k=0; k<w; k++){
	  ch[k][j] = 0;
	}
      }
      ch[px][py] = 1;
      for(;;){
	int x = play.front().first;
	int y = play.front().second;
	if(field[x][y] == i+1){ans+=ch[x][y]-1; px = x; py = y;break;}
	if(x>0){if(field[x-1][y] != -1){if(ch[x-1][y] == 0){play.push(make_pair(x-1,y)); ch[x-1][y] = ch[x][y]+1;}}}
	if(y>0){if(field[x][y-1] != -1){if(ch[x][y-1] == 0){play.push(make_pair(x,y-1)); ch[x][y-1] = ch[x][y]+1;}}}
	if(x<w-1){if(field[x+1][y] != -1){if(ch[x+1][y] == 0){play.push(make_pair(x+1,y)); ch[x+1][y] = ch[x][y]+1;}}}
	if(y<h-1){if(field[x][y+1] != -1){if(ch[x][y+1] == 0){play.push(make_pair(x,y+1)); ch[x][y+1] = ch[x][y]+1;}}}
	play.pop();
      }
    }
    cout <<ans<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

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

struct OBJ{
public:
	OBJ(char a, bool b):kind(a), mark(b){}
	char kind;
	bool mark;
};

void dfs(char target, pair<int, int> &pos, vector<vector<OBJ> > &field, int count){
	if(field[pos.second][pos.first].kind == target){
		mincount = mincount > count ? count : mincount;
		return;
	}
	field[pos.second][pos.first].mark = true;
	for(int i = 0; i < 4; i++){
		if((pos.first+dx[i]<0||pos.first+dx[i]>=field[0].size())||(pos.second+dy[i]<0||pos.second+dy[i]>=field.size())) continue;
		if(field[pos.second+dy[i]][pos.first+dx[i]].kind != 'X' && !field[pos.second+dy[i]][pos.first+dx[i]].mark){
			dfs(target, pair<int, int>(pos.first+dx[i], pos.second+dy[i]), field, count + 1);
		}
	}
	field[pos.second][pos.first].mark = false;
}

pair<int, int> decideStart(char target, vector<vector<OBJ> > &field){
	for(int i = 0; i < field.size(); i++){
		for(int j = 0; j < field[i].size(); j++){
			if(field[i][j].kind == target) return pair<int, int>(j, i);
		}
	}
}

int main(){
	int h = 0, w = 0, n = 0;
	cin >> h >> w >> n;
	cin.ignore();
	pair<int, int> start;
	vector<vector<OBJ> > field(h, vector<OBJ>(w, OBJ(' ', false)));
	for(int i = 0; i < h; i++){
		string tmp;
		getline(cin, tmp);
		for(int j = 0; j < w; j++){
			field[i][j].kind = tmp[j];
			if(tmp[j] == 'S') start = pair<int, int>(j, i);
		}
	}
	int count = 0;
	for(int i = 1; i <= n; i++){
		mincount = h*w;
		dfs(i+'0', start, field, 0);
		count += mincount;
		start = decideStart(i+'0', field);
	}

	cout << count << endl;

	return 0;
}

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

using namespace std;

int h, w;
char n;
char N[1002][1002];
bool p_flag[1002][1002] = { 0 };
int depth[1002][1002] = { 0 };

int main(){
	char next;
	int x, y, time = 0;
	int sx, sy;
	const int dx[4] = { 1, 0, -1, 0 };
	const int dy[4] = { 0, 1, 0, -1 };

	cin >> h >> w >> n;

	for (int i = 0; i < 1002; i++){
		for (int j = 0; j < 1002; j++){
			N[j][i] = 'X';
		}
	}
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			cin >> N[j][i];
			if (N[j][i] == 'S'){
				sx = j;
				sy = i;
			}
		}
	}

	queue <pair<int, int>> q;
	q.push(pair<int, int>(sx, sy));
	next = '1';
	bool b_flag = 0;
	p_flag[sx][sy] = 1;
	while (true){
		if (b_flag) break;
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int d = 0; d < 4; d++){
			if (N[x + dx[d]][y + dy[d]] != 'X'){
				if (depth[x + dx[d]][y + dy[d]] == 0) depth[x + dx[d]][y + dy[d]] = depth[x][y] + 1;
				if (p_flag[x + dx[d]][y + dy[d]] == 0){
					if (N[x + dx[d]][y + dy[d]] == next){
						if (next == n){
							cout << depth[x + dx[d]][y + dy[d]] << endl;
							b_flag = 1;
							break;
						}
						else{
							next = next + 1;
							while (!q.empty()) q.pop();
							for (int i = 0; i < 1002; i++){
								for (int j = 0; j < 1002; j++){
									p_flag[j][i] = false;
								}
							}
							q.push(pair<int, int>(x + dx[d], y + dy[d]));
							p_flag[x + dx[d]][y + dy[d]] = 1;
							int dep = depth[x + dx[d]][y + dy[d]];
							for (int i = 0; i < 1002; i++){
								for (int j = 0; j < 1002; j++){
									depth[j][i] = 0;
								}
							}
							depth[x + dx[d]][y + dy[d]] = dep;
							break;
						}
					}
					else {
						q.push(pair<int, int>(x + dx[d], y + dy[d]));
						p_flag[x + dx[d]][y + dy[d]] = 1;
					}
				}
			}
		}
	}
}

C++: #include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
struct node
{
	int x = -1,y = -1;
	node(int x = -1,int y = -1) : x(x),y(y) {};
}start[11];
const int N = 1005;
char g[N][N];
int s[N][N];
int H,W,n,sx,sy,gx,gy;
const int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int bfs()
{
	memset(s,0xff,sizeof(s));
	queue<node> q;
	q.push(node(sx,sy));
	s[sx][sy] = 0;
	while(!q.empty())
	{
		node& prev = q.front();q.pop();
		for(int i = 0;i < 4;++i)
		{
			int nx = prev.x + dx[i],ny = prev.y + dy[i];
			if(nx >= 0 && nx < H && ny >= 0 && ny < W && g[nx][ny] != 'X' && s[nx][ny] == -1)
			{
				s[nx][ny] = s[prev.x][prev.y] + 1;
				q.push(node(nx,ny));
				if(nx == gx && ny == gy)
					return s[nx][ny];
			}
		}
	}
}
int main()
{
	cin >> H >> W >> n;
	for(int i = 0;i < H;++i)	cin >> g[i];
	for(int i = 0;i < H;++i)
		for(int j = 0;j < W;++j)
			if(g[i][j] == 'S')
				start[0].x = i,start[0].y = j;
			else if(g[i][j] != '.' && g[i][j] != 'X')
				start[g[i][j]-'0'].x = i,start[g[i][j]-'0'].y = j;
	int res = 0;
	for(int i = 0;i < n;++i)
	{
		sx = start[i].x,sy = start[i].y;
		gx = start[i+1].x,gy = start[i+1].y;
		res += bfs();
	}
	cout << res << endl;
	return 0;
}