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<cstring>
#include<queue>
using namespace std;
struct p{
	int x;
	int y;
	int cnt;
};

int maps[1000][1000]={};
char map[1000][1000]={};
bool mapb[1000][1000]={},used[1000][1000]={};

int main(){
	queue<p> m;
	p f;
	p v;
	int h,w,n,i,j,z,sp=1,mv[4][2]={{0,-1},{1,0},{0,1},{-1,0}},count=0;
	char u,math[10]="123456789";
	cin>>h>>w>>n;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>u;
			for(z=0;z<9;z++){
				if(u==math[z]){
					maps[i][j]=z+1;
					mapb[i][j]=true;
				}
			}
			map[i][j]=u;
			if(u=='S'){
				f.x=j;
				f.y=i;
				f.cnt=0;
				m.push(f);
			}
		}
	}
	while(1){
		f=m.front();
		m.pop();
		if(used[f.y][f.x]==true){
			continue;
		}
		else{
			used[f.y][f.x]=true;
		}
		if(mapb[f.y][f.x]==true&&maps[f.y][f.x]<=sp){
			mapb[f.y][f.x]=false;
			cout<<f.x+1<<" "<<f.y+1<<" "<<f.cnt<<endl;
			count++;
			sp++;
			memset(used,0,sizeof(used));
			while(!m.empty()){
				m.pop();
			}
			m.push(f);
			used[f.y][f.x]=true;
			if(count==n){
				break;
			}
		}
		for(i=0;i<4;i++){
			if(map[f.y+mv[i][1]][f.x+mv[i][0]]!='X'&&(f.x+mv[i][0])>=0&&(f.x+mv[i][0])<w&&(f.y+mv[i][1])>=0&&(f.y+mv[i][1])<h){
				v.x=f.x+mv[i][0];
				v.y=f.y+mv[i][1];
				v.cnt=f.cnt+1;
				m.push(v);
			}
		}
	}
	cout<<f.cnt<<endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

#define PS push
#define PB push_back
#define MP make_pair
#define fi first
#define se second
const int INF = 0x3f3f3f3f;
#define cer(x) cout<<#x<<'='<<endl
#define REP0(i,n) for(int i = 0; i < n; i++)
#define REP1(i,n) for(int i = 1; i <= n; i++)
#define DWN(i,n) for(int i = n; i > 0; i--)
#define DWN_(i,n) for(int i = n; i >= 0; i--)
#define REP(i,s,e) for(int i = s; i < e; i++)
#define REP_(i,s,e) for(int i = s; i <= e; i++)
#define CLR(a,v) memset(a,v,sizeof(a))
typedef long long ll;

inline int read()
{
    int ret; char c; while(c = getchar(),c<'0'||c>'9');
    ret = c-'0';
    while(c = getchar(),c>='0'&&c<='9') ret = ret*10 + c-'0';
    return ret;
}

inline int reads()
{
    int ret; char c; while(c = getchar(),c != '-' && (c<'0'||c>'9'));
    bool Sign = c == '-';
    ret = Sign?0:c-'0';
    while(c = getchar(),c>='0'&&c<='9') ret = ret*10 + c-'0';
    return Sign?-ret:ret;
}

const int SZ = 1e3+5;

char g[SZ][SZ];
int H,W,N;
int vis[SZ][SZ],clk;
struct Node
{
    int x,y,f,h;
    bool operator <(const Node&th) const {
        return f > th.f || ( f == th.f && h > th.h);
    }
}pos[10];

int tar;
inline int MHT(Node &o)
{
    return (abs(pos[tar].x-o.x) + abs(pos[tar].y-o.y))>>1;
}

void GetPos()
{
    REP0(i,H){
        REP0(j,W){
            char c = g[i][j];
            if(c == 'S'){
                pos[0] = {i,j};
            }else if('1'<= c && c <='9' ){
                pos[c-'0'] = {i,j};
            }
        }
    }
}

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

inline bool valid(int x,int y)
{
    return x>=0&&x<H&&y>=0&&y<W&&g[x][y]!='X'&&vis[x][y] != clk;
}

int astar_bfs(int st)
{
    priority_queue<Node> q;
    Node u;
    u.x = pos[st].x;
    u.y = pos[st].y;
    u.h = u.f = MHT(u);
    q.push(u);
    clk++;
    while(q.size()){
        u = q.top(); q.pop();
        if(u.x == pos[tar].x && u.y == pos[tar].y ) return u.f-u.h;
        REP0(k,4){
            Node v;
            v.x = u.x + dx[k];
            v.y = u.y + dy[k];
            if(!valid(v.x,v.y)) continue;
            vis[v.x][v.y] = clk;
            v.h = MHT(v);
            v.f = u.f-u.h+1+v.h;
            q.push(v);
        }
    }
    return -1;
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    H = read(); W = read(); N = read();
    for(int i = 0; i < H; i++){
        scanf("%s",g[i]);
    }
    GetPos();
    int ans = 0;
    REP1(i,N){
        tar = i;
        ans += astar_bfs(i-1);
    }
    printf("%d\n",ans);
    return 0;
}

C++: #include<stdio.h>
#include<queue>
using namespace std;
int main(){
  int ans=0,x,y,h,w,n,i,j,g1[15],g2[15],a[1010][1010],k=0,b[1010][1010];
  char s;
  queue<int> q1;
  queue<int> q2;
  scanf("%d %d %d\n",&h,&w,&n);
  for(i=0;i<=h+1;i++){
    for(j=0;j<=w+1;j++){
      a[i][j]=-2;
    }
  }
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      scanf("%c",&s);
      if(s=='S'){
        a[i][j]=-1;
        q1.push(i),q2.push(j);
      }
      else if(s=='.'){
        a[i][j]=-1;
      }
      else if(s>='1' && s<='9'){
        a[i][j]=-1;
        g1[s-'0'-1]=i,g2[s-'0'-1]=j;
      }
    }
    scanf("\n");
  }
  for(i=0;i<n;i++){
    for(j=0;j<=h+1;j++){
      for(k=0;k<=w+1;k++){
        b[j][k]=a[j][k];
      }
    }
        b[q1.front()][q2.front()]=0;
  while(1){
    x=q1.front(),y=q2.front();
    if(x==g1[i] && y==g2[i]){
      break;
    }
    q1.pop(),q2.pop();
    if(b[x+1][y]==-1){
      q1.push(x+1),q2.push(y);
      b[x+1][y]=b[x][y]+1;
    }
    if(b[x-1][y]==-1){
      q1.push(x-1),q2.push(y);
      b[x-1][y]=b[x][y]+1;
    }
    if(b[x][y+1]==-1){
      q1.push(x),q2.push(y+1);
      b[x][y+1]=b[x][y]+1;
    }
     if(b[x][y-1]==-1){
      q1.push(x),q2.push(y-1);
      b[x][y-1]=b[x][y]+1;
    }
  }
    ans=ans+b[g1[i]][g2[i]];
    while(!q1.empty()){
      q1.pop(),q2.pop();
    }
    q1.push(g1[i]),q2.push(g2[i]);
  }
  printf("%d\n",ans);
  return 0;
}