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 <cstdio>
#include <stack>
#include <queue>

using namespace std;
const int maxn = 1005;
const int inf = 1e6;

typedef pair<int, int> P;
char data[maxn][maxn];
int dist[maxn][maxn];
int sx, sy, w, h, n, energy, sum;

void bfs(int& sx, int& sy, int energy)
{
    int a[4] = {-1, 0, 1, 0}, b[4] = {0, -1, 0, 1};
    queue<P> que;
    que.push(P(sx, sy));
    char temp[h][w];
    for(int i=0; i<h; ++i)
    {
        for(int j=0; j<w; ++j)
        {
            dist[i][j] = inf;
            temp[i][j] = data[i][j];
        }
    }

    dist[sx][sy] = 0;

    while(!que.empty())
    {
        P cur = que.front();
        que.pop();
        int x = cur.first, y = cur.second;
        if(temp[x][y]==(energy + '0'))
        {
            sx = x;
            sy = y;
            return;
        }

        temp[x][y]='X';
        for(int i=0; i<4; ++i)
        {
            int nx = x + a[i], ny = y + b[i];
            if(nx>=0 && nx<h && ny>=0 && ny<w && temp[nx][ny]!='X')
            {
                que.push(P(nx, ny));
                dist[nx][ny] = min(dist[nx][ny], dist[x][y]+1);
            }
        }
    }
}

int main()
{
    //while(scanf("%d%d", &w, &h)!= EOF && w && h){
    scanf("%d%d%d", &h, &w, &n);
    for(int i=0; i<h; ++i)
        scanf("%s", &data[i]);

    for(int i=0; i<h; ++i)
    {
        for(int j=0; j<w; ++j)
        {
            if(data[i][j]=='S')
            {
                sx = i;
                sy = j;
            }
        }
    }
    sum = 0, energy=1;
    while(energy<=n)
    {
        int bx = sx, by = sy;
        bfs(sx, sy, energy);
        data[bx][by] = '.';
        sum += dist[sx][sy];
        ++energy;
    }
    printf("%d\n", sum);

    //}
    return 0;
}

C++: #include<stdio.h>
#include<utility>
#include<queue>
using namespace std;

char maze[1000][1001];
void solve()
{
	bool flag[1000][1000]={0};
	int h,w,n,pow=1,ans=0;
	int h_route[4]={1,0,-1,0};
	int w_route[4]={0,1,0,-1};
	typedef pair <int,int> P;
	typedef pair<int ,P> P2;
	P data[10];


	scanf("%d %d %d\n",&h,&w,&n);
	
	for(int i=0;i<h;i++)//迷路読み込み
		for(int j=0;j<w+1;j++)
		{
			scanf("%c",&maze[i][j]);
			if(maze[i][j]=='S')
				data[0]=P(i,j);
			else if(maze[i][j] >='1' && maze[i][j] <='9')
				data[maze[i][j]-'0']=P(i,j);
		}

	for(int i=0;i<n;i++)
	{
		queue<P2> que;
		que.push(P2(ans,P(data[i].first,data[i].second)));
		while(!que.empty())
		{

			P2 temp = que.front();
			que.pop();
			if(temp.second.first==data[i+1].first && temp.second.second==data[i+1].second)
			{
				memset(flag,0,sizeof(flag));
				ans=temp.first;
				break;
			}
			for(int j=0;j<4;j++)
			{
				int Th=temp.second.first+h_route[j];
				int Tw=temp.second.second+w_route[j];
				if(Th>=0 && Th<h && Tw>=0 && Tw<w && maze[Th][Tw]!='X' && flag[Th][Tw]!=1)
				{
					que.push(P2(temp.first+1,P(Th,Tw)));
					flag[Th][Tw]=1;
				}
			}
		}
		
	}
	printf("%d\n",ans);
}

int main()
{
	solve();
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PA;
int main(){

  int h,w,n,a[11][2];
  char c[101][101];
  cin >> h >> w >> n;

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
      if(c[i][j]>='1'&&c[i][j]<='9'){
	a[ c[i][j]-'0'][0] = j;
	a[ c[i][j]-'0'][1] = i;
      }
      if(c[i][j]=='S'){
	a[0][0] = j;
	a[0][1] = i;
      }
    }
  }

  int sum = 0,suji[101][101],flag=0;
  queue<PA> que;
  int dx[12] = {1,-1,0,0};
  int dy[12] = {0,0,1,-1};

  for(int i=0;i<n;i++){

    memset(suji,-1,sizeof(suji));
    que.push( PA(a[i][0],a[i][1]) );
    suji[ a[i][1] ][ a[i][0] ] = 0;
    while(!que.empty()){
      PA p = que.front();
      que.pop();
      
      for(int j=0;j<4;j++){
	int x = p.first + dx[j];
	int y = p.second + dy[j];

	if(x<0||y<0||x>=w||y>=h||suji[y][x]!=-1||c[y][x]=='X') continue;
	suji[y][x] = suji[p.second][p.first]+1;
	que.push( PA(x,y) );
      }
    }
    
    sum += suji[a[i+1][1]][a[i+1][0]];

  }

  cout << sum << 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();
		cout << x << " " << y << endl;
		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;
					}
				}
			}
		}
	}

	for (int i = 1; i <= h; i++){
	for (int j = 1; j <= w; j++){
			cout << depth[j][i] << " ";
		}
		cout << endl;
	};
}