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 <algorithm>
#include <cmath>
#include <sstream>
#include <queue>
#include <stack>

using namespace std;

struct pos {
    pos() {x = 0;y = 0;}
    pos(int x, int y) {
        this->x = x;
        this->y = y;
    }
    int x, y;
};

const int INF = 1000000000;
const int mvx[] = {-1, 0, 1, 0};
const int mvy[] = {0, 1, 0, -1};

int map[1002][1002];
int mem[1002][1002];
pos cpos[10];

signed main() {
    int h,w,n;
    cin >> h >> w >> n;

    {
        int ccount = 0;
        for (int y = 1; y <= h; ++y) {
            string s;
            cin >> s;
            for (int x = 1; x <= w; ++x) {
                switch (s[x - 1]) {
                    case 'X':
                        map[x][y] = -1;
                        break;
                    case 'S':
                        cpos[0] = pos(x, y);
                        break;
                    case '.':
                        break;
                    default :
                        int hard = s[x - 1] - '0';
                        map[x][y] = INF + hard;
                        cpos[hard] = pos(x, y);
                }
            }
        }
    }

    for (int x = 0; x <= w + 1; ++x) {
        map[x][0] = -1;
        map[x][h + 1] = -1;
    }
    for (int y = 1; y <= h; ++y) {
        map[0][y] = -1;
        map[w + 1][y] = -1;
    }

    int cstep[9] = {0};
    for (int i = 0; i < n; ++i) {
        queue<pos> q;
        q.push(cpos[i]);
        int target = map[cpos[i + 1].x][cpos[i + 1].y];
        while (q.size()) {
            pos head = q.front();
            q.pop();
            int nextstep = mem[head.x][head.y] + 1;

            for (int k = 0; k < 4; ++k) {
                int tx = head.x + mvx[k], ty = head.y + mvy[k];

                if (map[tx][ty] == target) {
                    cstep[i] = nextstep;
                    goto end;
                }

                if (((map[tx][ty] != 0) && (map[tx][ty] < INF)) || (mem[tx][ty] != 0)) continue;

                q.push(pos(tx, ty));
                mem[tx][ty] = nextstep;
            }
        }
        end:;
        for (int x = 1; x <= w; ++x) {
            for (int y = 1; y <= h; ++y) {
                mem[x][y] = 0;
            }
        }
    }

    int result = 0;
    for (int i = 0; i < n; ++i) {
        result += cstep[i];
    }
    cout << result << endl;

    return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

char b[1000][1002];
int  m[1000][1000];
int  px[10];
int  py[10];

int main(){
  int h,w,n;
  while(~scanf("%d%d%d", &h, &w, &n)){
    REP(i,h) scanf("%s", b[i]);
    REP(i,h)REP(j,w){
      if(isdigit(b[i][j]) || b[i][j] == 'S'){
        if(b[i][j] == 'S'){
          px[0] = j;
          py[0] = i;
        }else{
          px[b[i][j] - '0'] = j;
          py[b[i][j] - '0'] = i;
        }
        b[i][j] = '.';
      }
    }

    int ans = 0;

    REP(p,n){
      queue<pair<int,int> > q;

      REP(i,h) REP(j,w) m[i][j] = -1;
      m[py[p]][px[p]] = 0;
      q.push(mp(px[p], py[p]));

      while(!q.empty()){
        pair<int,int> pos = q.front();
        int x = pos.f;
        int y = pos.s;
        q.pop();

        if(x == px[p+1] && y == py[p+1]){
          //printf("%d: %d\n", p, m[y][x]);
          ans += m[y][x];
          break;
        }

        REP(d,4){
          int xx = x + _dx[d];
          int yy = y + _dy[d];

          if(ISIN(xx,yy,w,h) && b[yy][xx] == '.' && m[yy][xx] == -1){
            m[yy][xx] = m[y][x] + 1;
            q.push(mp(xx,yy));
          }
        }
      }
    }

    print(ans);
  }
  return 0;
}

C++: #include <cstdio>
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int W, H, N;
typedef pair<int, int> P;
queue<P> que;
char maze[1003][1003];
int timer[1003][1003];
int pos_x, pos_y;
int sh_x[4] = {0, 0, -1, 1};
int sh_y[4] = {1, -1, 0, 0};
int res = 0;
int strength = 1;

void solve() {
  que.push(P(pos_x, pos_y));

  while(que.size()) {
    P pos = que.front(); que.pop();
    if (maze[pos.second][pos.first] - '0' == strength) {
      //printf("[%d] [%d]\n", pos.second, pos.first);
      while(que.size()) que.pop();
      strength++;
      if (strength == N+1) {
        res = timer[pos.second][pos.first];
        break;
      }

      for (int i=0;i<H;i++) {
        for (int j=0;j<W;j++) {
          if (maze[i][j] == '#') maze[i][j] = '.';
        }
      }

      maze[pos.second][pos.first] = '#';
      que.push(pos);
      continue;
    }
    for (int i=0;i<4;i++) {
      int new_x = pos.first + sh_x[i];
      int new_y = pos.second + sh_y[i];
      if (new_x >= 0 && new_x < W && new_y >=0 && new_y < H && maze[new_y][new_x] != '#' && maze[new_y][new_x] != 'X') {
        //printf("Go to [%d] [%d]\n", new_y, new_x);
        que.push(P(new_x, new_y));
        if (maze[new_y][new_x] == '.') {
          maze[new_y][new_x] = '#';
        }
        timer[new_y][new_x] = timer[pos.second][pos.first] + 1;
      }
    }
  }
}

int main() {
    scanf("%d %d %d", &H, &W, &N);
    getchar();
    
    for (int i = 0; i < H; i++)
    {
      fgets(maze[i], 1002, stdin);
      maze[i][W] = '#';
    }

    for (int i=0;i<H;i++) {
      for (int j=0;j<W;j++) {
        if (maze[i][j] == 'S') {
          pos_x = j;
          pos_y = i;
        }
        if (i==H-1) {
          maze[H][j] = '#';
        }
      }
    }

    solve();
    printf("%d\n", res);
    return 0;
}