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 <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
int h, w, n;
string data[1100];
int main() {
  while (cin >> h >> w >> n) {
    rep(i, h) cin >> data[i];
    pair<int, int> ce[10];
    rep(i, h) rep(j, w) {
      if (data[i][j] == 'S') {
        ce[0] = pair<int, int>(i, j);
      }
      if (isdigit(data[i][j])) {
        ce[data[i][j] - '0'] = pair<int, int>(i, j);
      }
    }
    int sum = 0;
    rep(i, n) {
      int mp[1100][1100];
      rep(i, 1100) rep(j, 1100) mp[i][j] = INF;
      bool used[1100][1100] = {};

      mp[ce[i].first][ce[i].second] = 0;
      used[ce[i].first][ce[i].second] = true;
      queue<pair<int, int>> que;
      que.push(ce[i]);
      while (que.size()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        rep(i, 4) {
          int ddy = y + dy[i];
          int ddx = x + dx[i];
          if (ddy >= 0 && ddy < h && ddx >= 0 && ddx < w &&
              data[ddy][ddx] != 'X' && !used[ddy][ddx]) {
            used[ddy][ddx] = true;
            mp[ddy][ddx] = mp[y][x] + 1;
            que.push(pair<int, int>(ddy, ddx));
          }
        }
      }
      sum += mp[ce[i + 1].first][ce[i + 1].second];
    }
    cout << sum << endl;
  }

  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)
#define INF 1 << 28
#define S second
#define F first
typedef pair<int,int> Pi;

int mx[] = {1,0,-1,0};
int my[] = {0,1,0,-1};

int main()
{
  int H, W, N;
  int sx,sy;
  char mas[1005][1005];
  Pi point[10];
  cin >> H >> W >> N;
  Rep(i,H) Rep(j,W) {
    cin >> mas[i][j];
    if(mas[i][j] == 'S') {
      sx = j, sy = i;
    }
    if(mas[i][j] >= '1' && mas[i][j] <= '9') {
      point[mas[i][j] - '0'] = Pi(i,j);
    }
  }

  int sum = 0;
  for(int p = 1; p <= N; p++) {
    int mc[1005][1005];
    fill(mc[0],mc[1005],INF);
    queue<Pi>que;
    mc[sy][sx] = 0;
    que.push(Pi(sy,sx));
    while(!que.empty()) {
      int x = que.front().S;
      int y = que.front().F;
      que.pop();
      if(mas[y][x] == p + '0')break;
      Rep(i,4) {
	int nx = x + mx[i];
	int ny = y + my[i];
	if(nx >= 0 && ny >= 0 && nx < W && ny < H && mas[ny][nx] != 'X' && mc[ny][nx] == INF) {
	  mc[ny][nx] = mc[y][x] + 1;
	  que.push(Pi(ny,nx));
	}
      }
    }
    sum += mc[point[p].F][point[p].S];
    sy = point[p].F, sx = point[p].S;
  }
  cout << sum << endl;
  return 0;
}

C++:   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] = 100000;
    }
  }

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

using namespace std;

#define MAXSIZE 1024

char square[MAXSIZE][MAXSIZE];
int H, W, N;
int flag[MAXSIZE][MAXSIZE];
int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };

struct Node
{
	int x;
	int y;
};

int BFS(int &x, int &y, int n) {
	for (int i = 0; i < H; i ++)
	{
		for (int j = 0; j < W; j++)
		{
			flag[i][j] = -1;
		}
	}
	queue<Node> que;
	Node node;
	node.x = x;
	node.y = y;
	que.push(node);
	flag[x][y] = 0;
	while (!que.empty())
	{
		Node cur = que.front();
		que.pop();
		for (int i = 0; i < 4; i++)
		{
			x = cur.x + dir[i][0];
			y = cur.y + dir[i][1];
			if (square[x][y] - '0' == n)
			{
				return flag[cur.x][cur.y] + 1;
			}
			if (x >= 0 && x < H && y >= 0 && y < W && square[x][y] != 'X' && flag[x][y] == -1)
			{
				Node next;
				next.x = x;
				next.y = y;
				flag[x][y] = flag[cur.x][cur.y] + 1;
				que.push(next);
			}
		}
	}
	return 0;
}

int main() {
	int start_X, start_Y;
	int step = 0;
	cin >> H >> W >> N;
	for (int i = 0; i < H; i ++)
	{
		for (int j = 0; j < W;  j++)
		{
			cin >> square[i][j];
			if (square[i][j] == 'S')
			{
				start_X = i;
				start_Y = j;
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		step += BFS(start_X, start_Y, i);
	}
	cout << step << endl;
	return 0;
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;
const int INF = 1e+8;
// 入力
int w, h, n;
char c[1001][1001];
// 4近傍
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
// d[y][x] := スタートから(x,y)までの最短距離 (未探索のときは INF )
int d[1001][1001];

// 文字 s から文字 s+1 までの最短距離を返す. (s は'0'-'8')
int bfs(char s){
	int sx, sy, gx, gy;
	// 初期化とスタート位置とゴール位置を探す.
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			d[y][x] = INF;
			if( c[y][x] == s ){
				sx = x;
				sy = y;
			}
			if( c[y][x] == s+1 ){
				gx = x;
				gy = y;
			}
		}
	}
	// スタート位置をキューに入れる
	queue<P> q;
	q.push( P(sx,sy) );
	d[sy][sx] = 0;
	int res = INF;
	while( !q.empty() ){
		int x = q.front().first;
		int y = q.front().second;
		int cost = d[y][x];
		q.pop();
		
		// ゴールのとき
		if( x == gx && y == gy ){
			res = cost;
			break;
		}
		
		// 4方向探索
		for(int i=0 ; i < 4 ; i++ ){
			int mx = x + dx[i];
			int my = y + dy[i];
			if( mx < 0 || my < 0 || w <= mx || h <= my ) continue;
			if( c[my][mx] == 'X' ) continue;
			
			if( cost+1 < d[my][mx] ){
				d[my][mx] = cost + 1;
				q.push( P(mx,my) );
			}
		}
	}
	return res;
}

int main(){
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> c[y];
	}
	// 処理しやすいように 'S' を '0' に置き換える.
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			if( c[y][x] == 'S' ) c[y][x] = '0';
		}
	}
	int ans = 0;
	for(int i=0 ; i < n ; i++ ){
		ans += bfs(i+'0');
	}
	cout << ans << endl;
}