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 <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int bfs(vector<string>& t, int c,int h, int w) {
  int si = 0, sj = 0;
  int ti = 0, tj = 0;
  REP(i,h)REP(j,w){
    if(t[i][j] == c + '0'){
      si = i;
      sj = j;
    }
    if(t[i][j] == c + '1'){
      ti = i;
      tj = j;
    }
  }
  vector<vector<int>> vis(h,vector<int>(w,1000000000));
  vis[si][sj] = 0;
  queue<pair<int,int>> q;
  q.push(make_pair(si,sj));
  while(!q.empty()) {
    auto p = q.front();
    q.pop();
    int i = p.first;
    int j = p.second;
    int di[4] = {1,0,-1,0};
    int dj[4] = {0,1,0,-1};
    REP(k,4){
      int ni=i+di[k];
      int nj=j+dj[k];
      if(ni<0||nj<0||ni>=h||nj>=w) continue;
      if(t[ni][nj] == 'X') continue;
      if(vis[ni][nj] > vis[i][j] + 1) {
        vis[ni][nj] = vis[i][j] + 1;
        q.push(make_pair(ni,nj));
      }
    }
  }
  return vis[ti][tj];
}

int main() {
  int h,w,n;
  cin >> h >> w >> n;
  vector<string> t(h);
  REP(i,h) cin >> t[i];
  int sum = 0;
  REP(i,h)REP(j,w)
    if(t[i][j] == 'S')
      t[i][j] = '0';
  REP(i,n) {
    sum += bfs(t,i,h,w);
  }
  cout << sum << endl;
  return 0;
}

C++: #include<stdio.h>
#include<utility>
#include<queue>
using namespace std;

char maze[1000][1001];
void solve()
{
	bool flag[1000][1000]={0};
	int h,w,n,pow=1,ans=0;
	int h_route[4]={1,0,-1,0};
	int w_route[4]={0,1,0,-1};
	typedef pair <int,int> P;
	typedef pair<int ,P> P2;
	P data[10];


	scanf("%d %d %d\n",&h,&w,&n);
	
	for(int i=0;i<h;i++)
		for(int j=0;j<w+1;j++)
		{
			scanf("%c",&maze[i][j]);
			if(maze[i][j]=='S')
				data[0]=P(i,j);
			else if(maze[i][j] >='1' && maze[i][j] <='9')
				data[maze[i][j]-'0']=P(i,j);
		}

	for(int i=0;i<n;i++)
	{
		queue<P2> que;
		que.push(P2(ans,P(data[i].first,data[i].second)));
		while(!que.empty())
		{

			P2 temp = que.front();
			que.pop();
			if(temp.second.first==data[i+1].first && temp.second.second==data[i+1].second)
			{
				memset(flag,0,sizeof(flag));
				ans=temp.first;
				break;
			}
			for(int j=0;j<4;j++)
			{
				int Th=temp.second.first+h_route[j];
				int Tw=temp.second.second+w_route[j];
				if(Th>=0 && Th<h && Tw>=0 && Tw<w && maze[Th][Tw]!='X' && flag[Th][Tw]!=1)
				{
					que.push(P2(temp.first+1,P(Th,Tw)));
					flag[Th][Tw]=1;
				}
			}
		}
		
	}
	printf("%d\n",ans);
}

int main()
{
	solve();
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    bool isVisited[MAX][MAX];
    int d[MAX][MAX];
    int ans=0;
    P start[9];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                start[0].first=i;
                start[0].second=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                start[atoi(in)].first=i;
                start[atoi(in)].second=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                isVisited[i][j]=false;
                d[i][j]=INF;
            }
        }
        que.push(start[k]);
        d[start[k].first][start[k].second]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==start[k+1])   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.seond+dy[i];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]==INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[start[k+1].first][start[k+1].second];
    }
    
    cout<<ans<<endl;
    
    return 0;
}

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

int flg[1000][1000];
void ini(){
	for(int i=0;i<1000;i++){
		for(int j=0;j<1000;j++){
			flg[i][j]=-1;
		}
	}
}

int main(){
	int x,y,n;
	int map[1001][1001];
	int cnt=0;
	pair<int,int> p;
	ntoa[10]="123456789";
	
	cin>>y>>x>>n;
	for(int i=0i<y;i++){
		for(int j=0;j<x;j++){
			cin>>map[i][j];
			if(map[i][j]=='S'){
				p = make_pair(i,j);
			}
		}
	}
	for(int i=0;i<n;i++){
		ini();
		queue<pair<int,int>> q;
		q.push(p);
		flg[p.first][p.second]=0;
		//幅優先
		while(!q,empty()){
			pair<int,int> temp=q.front();
			q.pop();
			int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
			for(int i2=0;i2<4;i2++){
				if( temp.first+dy[i2]<y && temp.first+dy[i2]>-1 && temp.second+dx[i2]<x && temp.second+dx[i2]>-1){
					if(map[temp.first+dy[i2]][temp.second+dx[i2]] != 'X' && flg[temp.first+dy[i2]][temp.second+dx[i2]] == -1){
						q.push(make_pair(temp.first+dy[i2],temp.second+dx[i2]));
						flg[temp.first+dy[i2]][temp.second+dx[i2]] = flg[temp.first][temp.second]+1;
					}
				}
				if(map[temp.first][temp.second] == ntoa[i]){
					cnt+=flg[temp.first][temp.second];
					p=temp;
				}
			}
		}
		//	
	}
	cout<<cnt;
	return 0;
}