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<queue>
#include<algorithm>
#include<string.h>
using namespace std;
struct nagase {
		int x;
		int y;
		int c;
		int r;
};
int kani[4]={0,1,-1,0};
int ebi[4]={1,0,0,-1};
long long map[1001][1001]={0};
int s[1001][1001];
int main(){
	queue<nagase>Q;
	nagase kotani;
	nagase yanagi;
	int h,w,n;
	cin>>h>>w>>n;
	char a;
	memset(s,0,sizeof(s));
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>a;
			if(a=='S'){
				kotani.x=i;
				kotani.y=j;
				kotani.c=1;
				kotani.r=0;
				s[i][j]=1;
				Q.push(kotani);
			}
			else if(a=='X'){
				map[i][j]=-1;
			}
			else if(a=='.'){
				map[i][j]=0;
			}
			else{
				map[i][j]=(int)(a-48);
			}
		}
	}
	while(!Q.empty()){
		yanagi=Q.front();
		Q.pop();
		if(yanagi.c==map[yanagi.x][yanagi.y]){
			if(yanagi.c==n){
				cout<<yanagi.r<<endl;
				break;
			}
			while(!Q.empty()){
				Q.pop();
			}
			yanagi.c++;
			memset(s,0,sizeof(s));
			s[yanagi.x][yanagi.y]=1;
			Q.push(yanagi);
		}
		else{
			for(int i=0;i<4;i++){
				if(yanagi.x+kani[i]>=0&&yanagi.x+kani[i]<h&&yanagi.y+ebi[i]>=0&&yanagi.y+ebi[i]<w&&map[yanagi.x+kani[i]][yanagi.y+ebi[i]]!=-1&&s[yanagi.x+kani[i]][yanagi.y+ebi[i]]!=1){
					kotani=yanagi;
					kotani.x=yanagi.x+kani[i];
					kotani.y=yanagi.y+ebi[i];
					kotani.c;
					kotani.r++;
					s[yanagi.x+kani[i]][yanagi.y+ebi[i]]=1;
					Q.push(kotani);
				}
			}
		}
	}
}

C++: #include<iostream>
#include<queue>
const int MAX_H = 1000;
const int MAX_W = 1000;
const int vx[4] = { 0, 1, 0, -1 };
const int vy[4] = { 1, 0, -1, 0 };
const int INF = 10000000;
const char num[9] = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
char c[MAX_H][MAX_W], b;
int y[MAX_H][MAX_W];
int h, w, n;
typedef std::pair<int, int> P;
P p[9];
P nest;
int bfs(P start, P end){
	std::queue<P> Q;
	P b;
	for (int i = 0; i<h; i++){
		for (int j = 0; j<w; j++){
			y[i][j] = INF;
		}
	}
	Q.push(start);
	y[start.first][start.second] = 0;
	while (Q.size()){
		b = Q.front();
		Q.pop();
		if (b == end){
			break;
		}
		for (int i = 0; i<4; i++){
			if (y[b.first][b.second] + 1<y[b.first + vx[i]][b.second + vy[i]] && y[b.first + vx[i]][b.second + vy[i]] == INF && c[b.first + vx[i]][b.second + vy[i]] != 'X'){
				y[b.first + vx[i]][b.second + vy[i]] = y[b.first][b.second] + 1;
				Q.push(P(b.first + vx[i], b.second + vy[i]));
			}
		}
	}
	return y[end.first][end.second];
}
int main(){
	int ok = 0;
	int ans = 0;
	std::cin >> h >> w >> n;
	for (int i = 0; i<h; i++){
		for (int j = 0; j<w; j++){
			std::cin >> b;
			if (b != 'S' && b != '.' && b != 'X'){
				for (int k = 0; k < 9; k++){
					if (b == num[k])ok = k;
				}
				p[ok].first = i;
				p[ok].second = j;
			}
			else if (b == 'S'){
				nest.first = i;
				nest.second = j;
			}
			c[i][j] = b;
		}
	}
	ans += bfs(nest, p[0]);
	for (int i = 1; i <= n - 1; i++){
		ans += bfs(p[i - 1], p[i]);
	}
	std::cout << ans << "\n";
}

C++: #include<bits/stdc++.h>
using namespace std;

struct data{
  int x;
  int y;
  int depth;
};

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

char A;
queue<data> q;
bool use[1000][1000] = {};
bool wall[1000][1000] = {};
int NS[1000][1000] = {};
data start;
data finish;
int ans;

for(int i = 0; i < H; i++){
  for(int j = 0; j < W; j++){
	cin>>A;
	if(A == 'X'){
		wall[j][i] = true;
	}
	if(A == 'S'){
		start.x = j;
		start.y = i;
		start.depth = 0;
	}
	if(A == '1'){
		NS[i][j] = 1;
	}
	if(A == '2'){
		NS[i][j] = 2;
	}
	if(A == '3'){
		NS[i][j] = 3;
	}
	if(A == '4'){
		NS[i][j] = 4;
	}
	if(A == '5'){
		NS[i][j] = 5;
	}
	if(A == '6'){
		NS[i][j] = 6;
	}
	if(A == '7'){
		NS[i][j] = 7;
	}
	if(A == '8'){
		NS[i][j] = 8;
	}
	if(A == '9'){
		NS[i][j] = 9;
	}
  }
}
q.push(start);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

for(int i = 1; i < N+1; i++){
  for(int j = 0; j < H; j++){
    for(int k = 0; k < W; k++){
	if(NS[j][k] == i){
	  finish.x = k;
	  finish.y = j;
	  finish.depth = 0;
	}
    }
  }

while(q.size()){
  data now = q.front();
  q.pop();
  if(now.x == finish.x && now.y == finish.y){
    ans = now.depth;
    break;
  }
  for(int i = 0; i < 4; i++){
    data next = now;
    next.x += dx[i];
    next.y += dy[i];
    next.depth += 1;
    if(next.x < 0 || next.y < 0 || next.x >= W || next.y >= H) continue;
    if(use[next.x][next.y] == true) continue;
    if(wall[next.x][next.y] == true) continue;
    
    use[next.x][next.y] = true;
    q.push(next);
  }
}
for(int l = 0; l < H; l++){
    for(int m =0; m < W; m++){
        use[m][l] = false;
    }
}
while(q.size()){
    q.pop();
}
start.x = finish.x;
start.y = finish.y;
start.depth = ans;
q.push(start);
}
cout << ans << endl;
return 0;
}

C++: #include<iostream>
#include<queue>
#define MAX 1000

typedef std::pair<int,int> P;

int h,w,N,PX[4]={1,-1,0,0},PY[4]={0,0,1,-1},sum=0;
char ch[MAX][MAX];

void bfs(P p,P q){
	std::queue<P> Q;
	Q.push(p);
	while(!Q.empty()){
		P u=Q.front();Q.pop();
		for(int i=0;i<4;++i){
			if(u.first+PX[i]>=0&&u.first+PX[i]<h&&u.second+PY[i]<w&&u.second+PY[i]>=0&&ch[u.first+PX[i]][u.second+PY[i]]!='X'){
				if(P(u.first+PX[i],u.second+PY[i])==q)
					return;
				else{
					++sum;
					Q.push(P(u.first+PX[i],u.second+PY[i]));
				}
			}
		}
	}
}

void solve(){
	int n=1;
	P s,p[10];
	for(int i=0;i<h;++i){
		for(int j=0;j<w;++j){
			if(ch[i][j]=='S')
				s.first=i;s.second=j;
			if(ch[i][j]==char(n)){
				p[n]=P(i,j);
				++n;
			}
		}
	}
	bfs(s,p[1]);
	for(int i=1;i<9;++i){
		bfs(p[i],p[i+1]);
	}
}

int main(){
	std::cin>>h>>w>>N;
	for(int i=0;i<h;++i){
		for(int j=0;j<w;++j){
			std::cin>>ch[i][j];
		}
	}
	solve();
	std::cout<<sum<<std::endl;
	return 0;
}