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

#define INF (1e+9)
#define LLINF (1e+18)
#define LL long long

using namespace std;

typedef struct info{
	int nx;
	int ny;
	int cost;
	int target;
	info(int a,int b,int c,int d){
		nx = a;
		ny = b;
		cost = c;
		target = d;
	}
}info;

bool isNumChar(char c){
	if((0 <= c-48)&&(c-48 <= 9))return true;
	return false;
}

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

int W,H;
int N;

int sx[16] = {0};
int sy[16] = {0};

char field[1024][1024] = {""};
int record[1024][1024][12] = {0};
bool flag[16] = {false};

queue<info> que;


int ans;



int recordReset(){
	for(int i = 0;i < 1024;i++){
		for(int j = 0;j < 1024;j++){
			for(int k = 0;k < 12;k++){
				record[i][j][k] = INF;
			}
		}
	}
}

int bfs(){
	info now(0,0,0,0);
	info next(0,0,0,0);
	for(int i = 0;i < N;i++){
		next = info(sx[i],sy[i],0,i+1);
		que.push(next);
	}

	recordReset();
	while(!que.empty()){
		now = que.front();
		que.pop();
		if(!flag[now.target]){
			//printf("###(%d,%d):::cost<%d>:::target<%d>\n",now.nx,now.ny,now.cost,now.target);
			if(record[now.nx][now.ny][now.target] > now.cost){
				record[now.nx][now.ny][now.target] = now.cost;
				if((sx[now.target] == now.nx)&&(sy[now.target] == now.ny)){
					flag[now.target] = true;
					//printf("###target<%d> completed\n",now.target);
					ans += record[now.nx][now.ny][now.target];
				}
				else{
					switch(field[now.nx][now.ny]){
					case 'X':
						break;
					default:
						for(int i = 0;i < 4;i++){
							next = info(now.nx + dx[i],now.ny + dy[i],now.cost + 1,now.target);
							que.push(next);
						}
						break;
					}
				}
			}
		}
	}
}


int main (void){
	//while(true){
		scanf("%d%d",&H,&W);
		scanf("%d",&N);
		//if((W == 0)&&(H == 0))break;

		ans = 0;

		//Reset Field
		for(int i = 0;i < 1024;i++){
			for(int j = 0;j < 1024;j++){
				field[j][i] = 'X';
			}
		}

		//Reset Flag
		for(int i = 0;i < 16;i++){
			flag[i] = false;
		}

		//Reading Data
		for(int i = 1;i <= H;i++){
			scanf(" ");
			for(int j = 1;j <= W;j++){
				scanf("%c",&field[j][i]);
				if(isNumChar(field[j][i])){
					sx[field[j][i]-48] = j;
					sy[field[j][i]-48] = i;
					//printf("###<%d>(%d,%d)\n",field[j][i] - 48,sx[field[j][i] - 48],sy[field[j][i] - 48]);

				}
				else if(field[j][i] == 'S'){
					sx[0] = j;
					sy[0] = i;
					//printf("###<S>(%d,%d)\n",j,i);
				}
			}
		}

		//DBG
		/*for(int i = 0;i < N;i++){
			printf("<%d>(%d,%d)\n",i,sx[i],sy[i]);
		}*/

		bfs();

		printf("%d\n",ans);
	//}

	return 0;
}

C++: #include <iostream>
#include <queue>
#define min(x,y) ((x)<(y)?(x):(y))
#define INFI 65535

using namespace std;
typedef pair<int, int> P;

int Strength = 1;
char Maps[1010][1010];
int dist[1010][1010];
int H, W, N;
int hor[] = {1,0,-1,0};
int ver[] = {0,-1,0,1};
int ans;


void clear();
void show();
P bfs(int cheese,P n);

int main(void) {
    cin>>H>>W>>N;
    P s,e;
    for (int i = 0; i<H; i++)
        cin>>Maps[i];
    for (int i = 0; i<H; i++)
        for (int j = 0; j<W; j++)
            if (Maps[i][j]=='S') s.first = i, s.second = j;
    
    
    for (int i = 1; i<=N; i++) {
        clear();
        s = bfs(i, s);
    }
    
    printf("%d\n", ans);
    return 0;
}

P bfs(int cheese,P n) {
    queue<P> que;
    que.push(n);
    dist[n.first][n.second] = 0;
    
    P top;
    while (que.size()) {
        top = que.front();
        if (Maps[top.first][top.second]-'0'==cheese) {
            ans += dist[top.first][top.second];
            break;
        }
        
        que.pop();
        for (int i = 0; i<4; i++) {
            int nv = top.first+ver[i], nh = top.second+hor[i];
            if (nv>=0 && nv<H && nh>=0 && nh<W && dist[nv][nh]==INFI && Maps[nv][nh]!='X') {
                que.push(P(nv,nh));
                dist[nv][nh] = min(dist[nv][nh], dist[top.first][top.second]+1);
            }
        }
    }
    return top;
}

void clear() {
    for (int i = 0; i<H; i++)
        for (int j = 0; j<W; j++)
            dist[i][j] = INFI;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
typedef long long ll;
#define INF 1e9
typedef pair<int,int> P;

int H,W,N;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
vector<vector<int> > maze;
vector<vector<int> > d;

bool mobility(int i, int j){
  return i>=0 && i<W && j >= 0 && j<H && maze[i][j]!=INF && d[i][j] == INF;
}

int bfs(int sx, int sy, int cur){
  int x,y,i;
  queue<P> que;
  que.push(P(sx,sy));
  REP(y,H)REP(x,W){
    if(x!=sx || y!=sy) d[x][y] = INF;
  }
  while(!que.empty()){
    P p = que.front();que.pop();
    x = p.first;y = p.second;
    if(maze[x][y] == cur) break;
    REP(i,4){
      int nx = x + dx[i], ny = y + dy[i];
      if(mobility(nx,ny)){
        que.push(P(nx,ny));
        d[nx][ny] = d[x][y] + 1;
      }
    }
  }
  if(cur == N) return d[x][y];
  return bfs(x,y,cur+1);
}

int main(void){
  int x,y,sx,sy;
  cin >> H >> W >> N;
  maze.resize(W,vector<int> (H));
  d.resize(W,vector<int> (H,INF));
  REP(y,H)REP(x,W){
    char c;
    cin >> c;
    if(isdigit(c)) maze[x][y] =  c - '0';
    else if(c == 'X') maze[x][y] = INF;
    else if(c == '.') maze[x][y] = 0;
    else{
      maze[x][y] = 0;
      sx = x;
      sy = y;
    }
  }
  d[sx][sy] = 0;
  cout << bfs(sx,sy,1) << endl;
  return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<queue>

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

string masu[1000];
int visit[1000][1000];

class T{
	public:
	int y,x,num;
	T(int y,int x,int num):y(y),x(x),num(num){}
};

int main(){
	int h,w,n;
	cin>>h>>w>>n;
	
	rep(i,h){
		cin>>masu[i];
		rep(j,w){
			if(masu[i][j]=='S')masu[i][j]='0';
		}
	}
	
	int ans = 0;
	
	for(int p=0;p<n;p++){
		rep(i,1000)rep(j,1000)visit[i][j]=0;
		
		int sty,stx;
		rep(i,h)rep(j,w)if(masu[i][j]==('0'+p)){
			sty = i;
			stx = j;
		}
		
		queue<T> que;
		que.push(T(sty,stx,0));
		while(1){
			if(que.empty())break;
			
			T u = que.front();
			que.pop();
			
			if(u.x<0 || u.y<0 || u.x>=w || u.y>=h)continue;
			if(visit[u.y][u.x]==1)continue;
			visit[u.y][u.x]=1;
			if(masu[u.y][u.x]=='X')continue;
			
			if(masu[u.y][u.x]==('1'+p)){
				ans += u.num;
				break;
			}
			
			int dx[4]={1,0,-1,0};
			int dy[4]={0,1,0,-1};
			rep(i,4){
				que.push(T(u.y+dy[i], u.x+dx[i], u.num+1));
			}
		}
	}
	
	printf("%d\n",ans);
	
}