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>
#define N 1002
using namespace std;
int bfs(pair<int,int>,pair<int,int>);
int h,w,d[N][N];
string str[N];
int main(){
  int n,i,j,sum;
  pair<int,int> P[10];
  cin >> h >> w >> n;
  for(i=0;i<=w+1;i++) str[0]+='X',str[h+1]+='X';
  for(i=1;i<=h;i++) cin >> str[i],str[i]='X'+str[i]+'X';
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(str[i][j]=='S') P[0].first=i,P[0].second=j;
      if('1'<=str[i][j]&&str[i][j]<='9'){
	P[str[i][j]-'0'].first=i;
	P[str[i][j]-'0'].second=j;
      }
    }
  }
  sum=bfs(P[0],P[1]);
  for(i=1;i<n;i++) sum+=bfs(P[i],P[i+1]);
  cout << sum << endl;
}
int bfs(pair<int,int> s,pair<int,int> g){
  int i,j,ret;
  pair<int,int> t;
  pair<int,int> u;
  queue< pair<int,int> > Q;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      d[i][j]=-1;
    }
  }
  Q.push(s);
  d[s.first][s.second]=0;
  while(Q.empty()!=1){
    u=Q.front();
    if(str[u.first][u.second]==str[g.first][g.second]){
      ret=d[u.first][u.second];
      break;
    }
    Q.pop();
    if(d[u.first][u.second-1]==-1&&str[u.first][u.second-1]!='X'){
      d[u.first][u.second-1]=d[u.first][u.second]+1;
      t.first=u.first;
      t.second=u.second-1;
      Q.push(t);
    }
    if(d[u.first][u.second+1]==-1&&str[u.first][u.second+1]!='X'){
      d[u.first][u.second+1]=d[u.first][u.second]+1;
      t.first=u.first;
      t.second=u.second+1;
      Q.push(t);
    }
    if(d[u.first-1][u.second]==-1&&str[u.first-1][u.second]!='X'){
      d[u.first-1][u.second]=d[u.first][u.second]+1;
      t.first=u.first-1;
      t.second=u.second;
      Q.push(t);
    }
    if(d[u.first+1][u.second]==-1&&str[u.first+1][u.second]!='X'){
      d[u.first+1][u.second]=d[u.first][u.second]+1;
      t.first=u.first+1;
      t.second=u.second;
      Q.push(t);
    }
  }
  return ret;
}

C++: #include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int h, w, n;
const int MAX_N = 1005;
char map[MAX_N][MAX_N];
int visit[MAX_N][MAX_N];
struct point{
	int x, y;
	int step;
	point(){
		x = 0; y = 0; step = 0;
	}
	point(int xx, int yy, int ss){
		x = xx;
		y = yy;
		step = ss;
	}
};
struct point p[16];

int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int ok(int x, int y){
	if (x >= 0 && x<h && y >= 0 && y<w) return 1;
	return 0;
}

int bfs(int next){
	for (int i = 0; i<MAX_N; i++){
		for (int j = 0; j < MAX_N; j++){
			visit[i][j] = 0;
		}
	}
	int nextcheese = next + 1;

	queue<point> q;
	point cur(p[next].x, p[next].y, 0);
	q.push(cur);
	while (q.size()){
		cur = q.front(); q.pop();
		int x = cur.x, y = cur.y;
		int nx, ny;
		for (int i = 0; i<4; i++){
			nx = x + dx[i]; ny = y + dy[i];
			if (ok(nx, ny)){
				if ((map[nx][ny] - '0') == nextcheese) return ++cur.step;
				if ((map[nx][ny] != 'X') && visit[nx][ny] == 0){
					q.push(point(nx, ny, cur.step + 1));
					visit[nx][ny] = 1;
				}
			}
		}
	}
}

void solve(){
	cin >> h >> w >> n;
	for (int i = 0; i<h; i++){
		for (int j = 0; j<w; j++){
			cin >> map[i][j];
		}
	}
	for (int i = 0; i<h; i++){
		for (int j = 0; j<w; j++){
			char ch = map[i][j];
			switch (ch){
			case '.': break;
			case 'X': break;
			case 'S': p[0].x = i; p[0].y = j; map[i][j] = '.'; break;
			default:
				int t = (ch - '0');
				p[t].x = i; p[t].y = j;
			}
			/* if(map[i][j]=='S'){
			p[0].x=i; p[0].y = j;
			map[i][j]='.';
			}
			else if(isdigit(map[i][j])){
			int index=map[i][j]-'0';
			p[index].x=i; p[index].y=j;
			}*/
		}
	}
	int step = 0;
	for (int i = 0; i<n; i++){
		step += bfs(i);
	}
	printf("%d\n", step);
}


int main(){
	solve();
}

C++: #include <iostream>
#include <cctype>
#include <queue>
#include <string.h>
using namespace std;
const int DIRECTSIZE = 4;
struct _direct {
    int drow;
    int dcol;
} direct[DIRECTSIZE] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int N = 1000;
const int N2 = 10;
char grid[N][N], visited[N][N];
int h, w, n;
struct _factory {
    int row, col;
} factory[N2];

struct _node {
    int row, col, level;
};

int bfs(int n, char goal)
{
    memset(visited, 0, sizeof(visited));

    _node start={factory[n-1].row, factory[n-1].col, 0}, temp;

    visited[start.row][start.col] = 1;

    queue<_node> q;
    q.push(start);

    while(!q.empty()) {
        _node front = q.front();
        q.pop();

        for(int i=0; i<DIRECTSIZE; i++) {
            int nextrow = front.row + direct[i].drow;
            int nextcol = front.col + direct[i].dcol;
            if( 0 <= nextrow && nextrow < h && 0 <= nextcol && nextcol < w) {
                if(grid[nextrow][nextcol] == goal) {
                    return front.level + 1;
                } else if(visited[nextrow][nextcol] == 0 && grid[nextrow][nextcol] != 'X') {
                    visited[nextrow][nextcol] = 1;
                    temp.row = nextrow;
                    temp.col = nextcol;
                    temp.level = front.level + 1;
                    q.push(temp);
                }
            }
        }
    }

    return 0;
}

int main()
{
    while(cin >> h >> w >> n) {
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++) {
                cin >> grid[i][j];

                if(grid[i][j] == 'S') {
                    factory[0].row = i;
                    factory[0].col = j;
                } else if(isdigit(grid[i][j])) {
                    factory[grid[i][j] - '0'].row = i;
                    factory[grid[i][j] - '0'].col = j;
                }
            }

        int minstep = 0;
        char goal = '1';
        for(int i=1; i<=n; i++) {
            minstep += bfs(i, goal);
            goal++;
        }

        cout << minstep << endl;
    }

    return 0;
}