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;


const int Max = 1005;
const int INF = 1000000000;
typedef pair<int,int>p;

p factory[15];

char a[Max][Max];
int b[Max][Max];
int h, w, n;

void initmartix(){
	for( int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			b[i][j] = INF;
}

bool judge(int x, int y){
	if (x >= 0 && x < h && y>= 0 && y < w && a[x][y] != 'X' && b[x][y] == INF)
		return true;
	return false;
}
		
int bfs(p ps, p pe){
	queue<p> que;
	initmartix();
	b[ps.first][ps.second] = 0;
	que.push(ps);
	
	while (que.size()){
		p top = que.front();
		que.pop();
		if (top == pe) break;
		int dx[4] = {0, 1, 0, -1};
		int dy[4] = {1, 0, -1, 0};
		for (int i = 0; i < 4; i++){
			int nx = top.first + dx[i];
			int ny = top.second + dy[i];
			if (judge(nx, ny)){
				b[nx][ny] = b[top.first][top.second] + 1;
				que.push(p(nx, ny));
			}
		}
	}
	return b[pe.first][pe.second];
}
		
void solve(){
	int sum = 0;
	for (int i = 0; i < n; i++){
		int time = bfs(factory[i], factory[i+1]);
		if (time != INF)	
			sum += time;

	}
	cout << sum << endl;
}
//读取。
int main(){
	cin >> h >> w >> n;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cin >> a[i][j];
			char tmp = a[i][j];
			if (tmp != '.' && tmp != 'X'){
				
				if (a[i][j] == 'S'){
					factory[0] = p(i, j);
				}
				else{
					factory[tmp - '0'] = p(i, j);
				}
			}
		}
	}
//解题。
	solve();
	return 0;
}

C++: #include <iostream>
#include <queue>
#include <algorithm>
#define N 12
#define INFINITY 2000000000
using namespace std;
void bfs();
int h,w,n,num[1002][1002],d[N*N],M[N*N][N*N],u,m;
string color[N*N],in[N*N];
int main(){
  int i,j,k;
  cin >> h >> w >> n;
  for(i=0;i<h+2;i++)
    for(j=0;j<w+2;j++)
      num[i][j]=-1;
  for(i=1;i<=h;i++) cin >> in[i],in[i]='X'+in[i];
  k=0;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(in[i][j]!='X') num[i][j]=k,k++;
    }
  }
  m=max(h,w);
  for(i=0;i<=m;i++)
    for(j=0;j<=m;j++)
      M[i][j]=0;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(num[i][j]!=-1&&num[i+1][j]!=-1)
	M[num[i][j]][num[i+1][j]]=M[num[i+1][j]][num[i][j]]=1;
      if(num[i][j]!=-1&&num[i][j+1]!=-1)
	M[num[i][j]][num[i][j+1]]=M[num[i][j+1]][num[i][j]]=1;
    }
  }
  bfs();
  return 0;
}
void bfs(){
  int i,j,p=1,t=0,flag=0,x=1;
  char start='S',goal='1';
  queue<int> q;
  while(1){
    if(flag==1) start=x+'0',goal=x+'0'+1,x++;
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	color[num[i][j]]="WHITE",d[num[i][j]]=INFINITY;
      }
    }
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(in[i][j]==start) color[num[i][j]]="GLAY",d[num[i][j]]=0,q.push(num[i][j]);
      }
    }
    while(q.empty()!=1){
      u=q.front();
      q.pop();
      for(i=1;i<=h;i++){
	for(j=1;j<=w;j++){
	  if(M[u][num[i][j]]&&color[num[i][j]]=="WHITE"){
	    color[num[i][j]]="GLAY";
	    d[num[i][j]]=d[u]+1;
	    q.push(num[i][j]);
	  }
	}
      }
      color[u]="BLACK";
    }
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(in[i][j]==goal) t+=d[num[i][j]];
      }
    }
    flag=1;
    if(x>n) break;
  }
  cout << t << endl;
}

C++: #include<iostream>
#include<queue>
#define x first
#define y second
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int h,w,k;
pair<int,int> p[12];
bool t[1010][1010],vis[1010][1010];
queue<pair<int,pair<int,int> > >Q;
int main(){
	cin>>h>>w>>k;
	rep(i,0,h)rep(j,0,w){
		t[i][j]=true;
		char z;cin>>z;
		if(z=='X')t[i][j]=0;
		if(z=='S')p[0]=make_pair(i,j);
		if(z>'0'&&z<='9')p[z-'0']=make_pair(i,j);
	}
	int a=0;
	rep(r,0,k){
		Q.push(make_pair(0,p[r]));
		rep(i,0,h)rep(j,0,w)vis[i][j]=0;vis[p[r].x][p[r].y]=1;
		while(1){
			int L=Q.front().x,Y=Q.front().y.x,X=Q.front().y.y;
			if(Y==p[r+1].x&&X==p[r+1].y){
				a+=L;
				break;
			}
			int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
			rep(i,0,4){
				int f=Y+dy[i],g=X+dx[i];
				if(f>=0&&f<h&&g>=0&&g<w){
					if(t[f][g]==1&&vis[f][g]==0){
						vis[f][g]=1;
						Q.push(make_pair(L+1,make_pair(f,g)));
					}
				}
			}
			Q.pop();
		}
		while(!Q.empty())Q.pop();
	}
	cout<<a<<endl;
	return 0;
}

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

using namespace std;

const int INF = 10000000;
const int MAX_H = 1003;
const int MAX_W = 1003;
int H, W, N;
char blocks[MAX_H][MAX_W];
int init_row, init_col;

int init() {
	fill_n((char*)blocks, MAX_H * MAX_W, 'X');
	cin >> H >> W >> N;
	for (int i = 1; i <= H; i++) {
		scanf("%s", blocks[i] + 1);
		blocks[i][strlen(blocks[i])] = 'X';
	}
	
	H += 2;
	W += 2;
	
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (blocks[i][j] == 'S') {
				init_row = i;
				init_col = j;
			}
		}
	}
	
	return 0;
}

int bfs(int start_row, int start_col, int goal_row, int goal_col) {
	queue<int> que_i;
	queue<int> que_j;
	que_i.push(start_row);
	que_j.push(start_col);
	
	int d[MAX_H][MAX_W];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			d[i][j] = INF;
		}
	}
	d[start_row][start_col] = 0;
	
	while (!que_i.empty()) {
		int i = que_i.front(); que_i.pop();
		int j = que_j.front(); que_j.pop();
		
		int di[] = {1, -1, 0, 0};
		int dj[] = {0, 0, 1, -1};
		
		if (i == goal_row && j == goal_col) return d[i][j];
		
		for (int k = 0; k < 4; k++) {
			int ti = i + di[k];
			int tj = j + dj[k];
			
			if (blocks[ti][tj] != 'X') {
				if (d[ti][tj] > d[i][j] + 1) {
					d[ti][tj] = d[i][j] + 1;
					que_i.push(ti);
					que_j.push(tj);
				}
			}
		}
	}
	
	return 0;
}

void solve() {
	vector<int> to_i(N);
	vector<int> to_j(N);
	
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char ch = blocks[i][j];
			if ('1' <= ch && ch <= '9') {
				to_i[(int)(ch - '1')] = i;
				to_j[(int)(ch - '1')] = j;
			}
		}
	}
	
	int s_i = init_row;
	int s_j = init_col;
	
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int n = bfs(s_i, s_j, to_i[i], to_j[i]);
		ans += n;
		s_i = to_i[i];
		s_j = to_j[i];
	}
	
	cout << ans << endl;
}

int main() {
	init();
	solve();
}