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 <queue>

using namespace std;

const int INF = 99999999;
typedef pair<int, int> Pair;

char cheese[1000][1000];
int d[1000][1000], count = 0, N;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void bfs(int row, int col, int sx, int sy, int cur){
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) 
            d[i][j] = INF;
    }
    d[sx][sy] = 0; //been visited

    queue<Pair> que;
    que.push(Pair(sx, sy));
    Pair p = que.front();

    while((cheese[p.first][p.second]-'0') != cur) {
        que.pop();
        for(int i = 0; i < 4; i++) {
            int x = p.first + dx[i], y = p.second + dy[i];
            if(x >= 0 && x < row && y >= 0 && y < col && cheese[x][y] != 'X' && d[x][y] == INF) {// can move this way
                d[x][y] = d[p.first][p.second]+1;
                que.push(Pair(x, y));
            }
        }
        p = que.front();
    }

    //cheese[p.first][p.second] != cur
    count += d[p.first][p.second];
    if(cur == N)
        return;
    bfs(row, col, p.first, p.second, cur+1);
}

int main() {
    int row, col, sx, sy;
    cin >> row >> col >> N;
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            cin >> cheese[i][j];
            if(cheese[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    bfs(row, col, sx, sy, 1);
    cout << count << endl;
    return 0;
}

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

typedef pair<int,int> P;
int H,W,N;
int inf = 10e8;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
char G[1010][1010];
int hp = 1,sum = 0;
int sx,sy;
int times[1010][1010];

bool valid(int x,int y){
	return 0<=x && x<H && 0<=y && y<W && G[x][y]!='X';
}

int bfs(){
	queue<P> q;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			times[i][j] = inf;
		}
	}
	while(hp<=N){
		q.push(P(sx,sy));
		times[sx][sy] = 0;
		while(q.size()){
			P p = q.front();q.pop();
			if(isdigit(G[p.first][p.second]) && hp == atoi(&G[p.first][p.second])){
				hp++;
				sum += times[p.first][p.second];
				sx = p.first;sy = p.second;
				for(int i=0;i<H;i++){
					for(int j=0;j<W;j++){
						times[i][j] = inf;
					}
				}
				while(q.size()){
					q.pop();
				}
				break;
			}
			for(int i=0;i<4;i++){
				int x = p.first + dx[i] , y  = p.second + dy[i];
				if(valid(x,y) && times[x][y]==inf){
					q.push(P(x,y));
					times[x][y] = times[p.first][p.second] + 1;
				}
			}
		}
	}
	return sum;
}

int main(){
	cin >> H >> W >> N;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin >> G[i][j];
			if(G[i][j] == 'S'){
				sx = i;
				sy = j;
			}
		}
	}
	cout << bfs() << endl;
}

C++: #include <stdio.h>
#include <queue>
using namespace std;
int d[1000][1000], sx, sy;
char s[1000][1000];
int h,w,n;
int k, l;

int bfs(int,int,int,int);

int main(){
  int result = 0;
  int x[10], y[10], v;
  scanf("%d %d %d", &h, &w, &n);
  for(k = 0 ; k < h ; k++){
      scanf("%s",s[k]);
    }
  for( k = 0 ; k < h ; k++ ){
    for( l = 0 ; l < w ; l++){
      if(s[k][l] == 'S'){
	x[0] = l; y[0] = k;
      }
      if('1' <= s[k][l] && s[k][l] <= '9'){
	v = s[k][l]-'1'+1;
	x[v] = l; y[v] = k;
      }
    }
  }
  for (k = 1 ; k <= n ; k++){
   
    result += bfs(x[k-1],y[k-1],x[k],y[k]);
  }
  printf("%d\n", result);
  return 0;
}

int bfs(int sx, int sy, int gx, int gy){
  queue<int> Q;
  int i, j;
  int dx[4]={0, 1, 0, -1};
  int dy[4]={1, 0, -1, 0};
  

  for( i =  0 ; i < h ; i++ ){
    for( j = 0 ; j < w ; j++ ){
      d[i][j] = 1000000;
    }
  }

  Q.push(sy*w+sx);
  d[sy][sx]=0; /*スタート地点の初期化*/

  while( !Q.empty() ){
    int u = Q.front(); Q.pop();
    int pi = u/w;
    int pj = u%w;
    if( pi == gy && pj == gx )return d[gy][gx];
    for ( int r = 0; r < 4; r++ ){
      int ni = pi + dy[r];
      int nj = pj + dx[r];
      if ( ni < 0 || nj < 0 || ni >= h || nj >= w ) continue;
      if ( s[ni][nj] == 'X' ) continue;
      if( d[ni][nj] > d[pi][pj]+1 ){
      d[ni][nj] = d[pi][pj] + 1;
      Q.push( ni * w + nj );
      }

    }


  }
  //  printf("%d\n",u);
  return -1;
}

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

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define Y first
#define X second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<pi, pi> pipi;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int H, W, N;
char field[1000][1000];
int dy[] = {0,1,0,-1}, dx[] = {1,0,-1,0};

int main(){
  scanf("%d%d%d", &H, &W, &N);
  rep(i, H) scanf("%s", field[i]);

  int x, y;
  rep(i, H) rep(j, W) if(field[i][j] == 'S'){ y = i; x = j; break;}

  map<pi, int>m;
  m[MP(y, x)] = 1;
  queue<pipi>q;
  q.push(MP(MP(1, 0), MP(y, x)));
  while(!q.empty()){
    pipi p = q.front(); q.pop();
    if(field[p.S.Y][p.S.X] == p.F.F + '0'){
      if(p.F.F == N){
	printf("%d\n", p.F.S);
	break;
      }
      m.clear();
      while(!q.empty()) q.pop();
      m[MP(p.S.Y, p.S.X)] = 1;
      p.F.F++;
    }
    rep(d, 4){
      int ny = p.S.Y + dy[d], nx = p.S.X + dx[d];
      int hp = p.F.F, c = p.F.S;
      if(ny < 0 || ny >= H || nx < 0 || nx >= W || field[ny][nx] == 'X' || m.count(MP(ny, nx))) continue;
      m[MP(ny, nx)] = 1;
      q.push(MP(MP(hp, c+1), MP(ny, nx)));
    }
  }
  return 0;
}