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>
#include<cstring>
using namespace std;
int m,n;
int maxe=0;
int che=0;
int k;
struct node{
  int x,y;
};
char mape[1111][1111];
int d[1111][1111];
queue<node> q;
int da[]={0,0,1,-1};
int db[]={1,-1,0,0};
void bfs(){
  while(!q.empty()&&che<k){
    node nn;
    int x=q.front().x;
    int y=q.front().y;
    q.pop();
    if(mape[x][y]>='0'&&mape[x][y]<='9'){
      che++;
      maxe+=d[x][y];
    }
    else mape[x][y]='X';
    for(int i=0;i<4;i++)
      if(x+da[i]>=0&&x+da[i]<m&&y+db[i]>=0&&y+db[i]<n&&mape[x+da[i]][y+db[i]]!='X'){
	int w=x+da[i];
	int e=y+db[i];
	d[w][e]=d[x][y]+1;
	nn.x=w;
	nn.y=e;
	mape[w][e]='X'
	q.push(nn);
      }
  }
}
int main(){
  cin>>m>>n>>k;
  while(!q.empty())q.pop();
  node nn;
  memset(d,-1,sizeof(d));
  for(int i=0;i<m;i++)
    for(int j=0;j<n;j++){
      cin>>mape[i][j];
      if(mape[i][j]=='S'){
	nn.x=i;
	nn.y=j;
	d[i][j]=0;
	q.push(nn);
	mape[i][j]='X';
      }
    }
  bfs();
  cout<<maxe<<"\n";
}

C++: #include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string.h>
#include<functional>
//aoj 0558
using namespace std;
int n,bs;
int hs,sl;
int dh[5]={0,0,0,1,-1};
int dll[5]={0,1,-1,0,0};
int cun[1003][1003];
struct pt{
	int hh;
	int ll;
	int step;
};
pt dl1[11];
char vis[1003][1003];
pt dl[1<<16];
void bfs(int h,int l,int gs)
{
	int qy=1<<16;
	qy--;
	memset(dl,0,sizeof(dl));
	memset(vis,0,sizeof(vis));
	int front=1;
	int back=2;
	pt ls;
	ls.hh=h;
	ls.ll=l;
	ls.step=0;
	dl[1]=ls;
	vis[h][l]=1;
	while(front<back)
	{
		pt lss=dl[front&qy];
		front++;
		for(int i=1;i<=4;i++)
		{
			if(lss.hh+dh[i]>0&&lss.hh+dh[i]<=hs&&lss.ll+dll[i]>0&&lss.ll+dll[i]<=sl&&cun[lss.hh+dh[i]][lss.ll+dll[i]]!=111&&vis[lss.hh+dh[i]][lss.ll+dll[i]]!=1)
			{
				pt jr;
				jr.hh=lss.hh+dh[i];
				jr.ll=lss.ll+dll[i];
				jr.step=lss.step+1;
				if(cun[lss.hh+dh[i]][lss.ll+dll[i]]==gs)
				{
					bs+=jr.step;
					return;
				}else{
					dl[back&qy]=jr;
					vis[jr.hh][jr.ll]=1;
					back++;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&hs,&sl,&n);
	while(getchar()!='\n');
	for(int i=1;i<=hs;i++)
	{
		for(int j=1;j<=sl;j++)
		{
			char aaa;
			scanf("%c",&aaa);
			if(aaa=='X')
			{
				cun[i][j]=111;
			}
			if(aaa=='S')
			{
				pt ls;
				ls.hh=i;
				ls.ll=j;
				dl1[0]=ls;
				cun[i][j]=22;
			}
			if(aaa>='1'&&aaa<='9')
			{
				pt ls;
				ls.hh=i;
				ls.ll=j;
				dl1[aaa-'0']=ls;
				cun[i][j]=aaa-'0';
			}
		}
		
		while(getchar()!='\n');
	}
	for(int i=0;i<=n-1;i++)
	{
		bfs(dl1[i].hh,dl1[i].ll,i+1);
	}
	printf("%d\n",bs);
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<string>
using namespace std;
bool a[10000][10000];
long long  f[10000][10000];
long long  sum = 0, sum3=10000000;
bool sum2 = false;
void solve(int i, int j,int mi,int mj,int h,int w) {
	if (i == mi&&j == mj&&sum3>f[i][j]) {
		sum3 = f[i][j];
		sum2 = true;
		return;
	}
	if (a[i][j + 1] && f[i][j] + 1 < f[i][j + 1] && j + 1 < w) {
		f[i][j + 1] = f[i][j] + 1;
		solve(i, j + 1, mi, mj, h, w);
	}
	if (a[i][j - 1] && f[i][j] + 1 < f[i][j - 1] && j - 1 >= 0) {
		f[i][j - 1] = f[i][j] + 1;
		solve(i, j - 1, mi, mj, h, w);
	}
	if (a[i + 1][j] && f[i][j] + 1 < f[i + 1][j] && i + 1 < h) {
		f[i + 1][j] = f[i][j] + 1;
		solve(i + 1, j, mi, mj, h, w);
	}
	if (a[i - 1][j] && f[i][j] + 1 < f[i - 1][j] && i - 1 >= 0) {
		f[i - 1][j] = f[i][j] + 1;
		solve(i - 1, j, mi, mj, h, w);
	}
}
int main() {
	long long  h, w, n;
	cin >> h >> w >> n;
	long long  b[100][2], c;
	string d;
	for (int i = 0; i < h; i++) {
		cin >> d;
		for (int j = 0; j < w; j++) {
			if (d[j] == 'X')
				a[i][j] = false;
			else
				a[i][j] = true;
			if (d[j] >= '1'&&d[j] <= '9') {
				int e = (int)d[j] - '0';
				b[e][0] = i;
				b[e][1] = j;
			}
			if (d[j] == 'S') {
				b[0][0] = i;
				b[0][1] = j;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < h; j++)
			fill(f[j], f[j] + w, 1000001);
		sum2 = false;
		f[b[i][0]][b[i][1]] = 0;
		solve(b[i][0], b[i][1], b[i + 1][0], b[i + 1][1], h, w);
		sum += f[b[i + 1][0]][b[i + 1][1]];
	}
	cout << sum << endl;
}

C++: #include <bits/stdc++.h>

using namespace std;

struct Node{
	int x,y,t;
	Node(int x_,int y_,int t_){
		x = x_;
		y = y_;
		t = t_;
	}
};

int H,W,N;
int area[1001][1001];
bool memo[1001][1001];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int bfs(int sx,int sy,int HP){
	fill_n(*memo,1001*1001,0);
	queue<Node> Q;
	Q.push(Node(sx,sy,0));
	int ret;

	while(!Q.empty()){
		int X,Y,T;
		Node node = Q.front();
		X = node.x;
		Y = node.y;
		T = node.t;
		Q.pop();
		if(area[X][Y] == HP){
			ret = T;
			break;
		}
		if(memo[X][Y] == 1)continue;
		memo[X][Y] = 1;
		for(int i = 0;i < 4;i++){
			int nx = X + dx[i];
			int ny = Y + dy[i];
			if(nx < 0 || ny < 0 || nx >= W || ny >= H)continue;
			if(area[nx][ny] == -1)continue;
			Q.push(Node(nx,ny,T+1));
		}
	}
	return ret;
}

int main(){
	fill_n(*area,1001*1001,0);
	int sx[10];
	int sy[10];
	char c;
	int ans = 0;
	cin >> H >> W >> N;
	for(int i = 0;i < H;i++){
		for(int j = 0;j < W;j++){
			cin >> c;
			if(c == 'X'){
				area[j][i] = -1;
			}else if(c == '.'){
				area[j][i] = 0;
			}else if(c == 'S'){
				area[j][i] = 0;
				sx[0] = j;
				sy[0] = i;
			}else{
				area[j][i] = c - '0';
				sx[c - '0'] = j;
				sy[c - '0'] = i;
			}
		}
	}
	for(int i = 0;i < N;i++){
		ans += bfs(sx[i],sy[i],i+1);
	}
	cout << ans << endl;
}