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<string>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAX 1000
int y[MAX][MAX];
int x[MAX][MAX];
int px[10];
int py[10];
int main(){
	memset(y,127,sizeof(y));
	char T[12]={'.','1','2','3','4','5','6','7','8','9','S','X'};
	int n,m,c,d,sum;
	string S;
	sum=0;
	cin>>n>>m>>c;
	for(int i=0;i<n;i++){
		cin>>S;
		for(int j=0;j<m;j++){
			for(int k=0;k<12;k++){
				if(S[j]==T[k]){
					x[i][j]=k;
					if(k==10){
						px[0]=i;
						py[0]=j;
					}
					if(k>=1 && k<=9){
						px[k]=i;
						py[k]=j;
					}
				}
			}
		}
	}
	for(int i=1;i<=c;i++){
		memset(y,127,sizeof(y));
		y[px[i-1]][py[i-1]]=0;
		for(int j=0;j<n*m/3+2;j++){
			for(int k=0;k<n;k++){
				for(int l=0;l<m;l++){
					if(k>=1){
						if(x[k-1][l]!=11){
							y[k-1][l]=min(y[k-1][l],y[k][l]+1);
						}
					}
					if(l>=1){
						if(x[k][l-1]!=11){
							y[k][l-1]=min(y[k][l-1],y[k][l]+1);
						}
					}
					if(x[k+1][l]!=11){
						y[k+1][l]=min(y[k+1][l],y[k][l]+1);
					}
					if(x[k][l+1]!=11){
						y[k][l+1]=min(y[k][l+1],y[k][l]+1);
					}
				}
			}
		}
		sum += y[px[i]][py[i]];
	}
	cout<<sum<<endl;
	return 0;
}

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

typedef struct{
 int x;
 int y;
}P;

char graph[1000][1000];
P aim[10];
P s,g;//s?????????g??????
int N,W,H;
int vis[1000][1000]; 
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int bfs(P s,P g);

int main(){
    int i,j,t,step=0;
    cin>>H>>W>>N;
    
    for(i=0;i<H;i++)
    for(j=0;j<W;j++){
        cin>>graph[i][j];
      if(graph[i][j]<='9'&&graph[i][j]>='1'){ 
         t=graph[i][j]-'0';
         aim[t].x=i;
         aim[t].y=j;
      } 
      else if(graph[i][j]=='S'){
          s.x=i;
          s.y=j;
          graph[i][j]='.';
      }
    
    for(i=1;i<=N;i++){
       g.x=aim[i].x;
       g.y=aim[i].y;
       step+=bfs(s,g);
       s.x=g.x;
       s.y=g.y;
       graph[g.x][g.y]='.';
    }
   
    cout<<step<<endl;
}

int bfs(P s,P g){
    queue<P> que;
      P n;
    
    for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
     vis[i][j]=-1;
     
     que.push(s);
     vis[s.x][s.y]=0;
     
     while(que.size()){
         
       P p=que.front();
         que.pop();
       if(p.x==g.x&&p.y==g.y)
       break;
       
       for(int i=0;i<4;i++){
           n.x=p.x+dx[i];
           n.y=p.y+dy[i];
        if(0<=n.x&&n.x<H&&0<=n.y&&n.y<W&&graph[n.x][n.y]!='X'&&vis[n.x][n.y]==-1){
               que.push(n);
               vis[n.x][n.y]=vis[p.x][p.y]+1;
           }
       }
   }
     return vis[g.x][g.y];
}

C++: #include <iostream>
#include <queue>

#define INF 1e9
#define MAX_H 1000
#define MAX_W 1000

using namespace std;

struct Cood {int x, y; };

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

char field[MAX_H][MAX_W + 1];
int d[MAX_H][MAX_W + 1];
queue<Cood> q;
int h, w, n;
int total_time = 0;

void init_bfs() {
    queue<Cood> new_q;
    swap(q, new_q);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            d[i][j] = INF;
        }
    }
}
/* current position (y, x) with current power 'current' & last cheeese target is 'last' */
int bfs(int sy, int sx, int target, int last) {
    init_bfs();
    int next_y, next_x;
    q.push(Cood{sx, sy});
    d[sy][sx] = 0;

    while (q.size()) {
        Cood current = q.front(); q.pop();
        if (field[current.y][current.x] == '0' + target) {
            total_time += d[current.y][current.x];
            if (target == last) {
                return total_time;
            } else {
                return bfs(current.y, current.x, target + 1, last);
            }
        }

        for (int i = 0; i < 4; ++i) {
            next_y = current.y + dy[i];
            next_x = current.x + dx[i];
            if (0 <= next_y && next_y < h && 0 <= next_x && next_x < w
                && field[next_y][next_x] != 'X' && d[next_y][next_x] == INF) {
                q.push(Cood{next_x, next_y});
                d[next_y][next_x] = d[current.y][current.x] + 1;
            }
        }
    }
}

int main() {
    //freopen("0558.in", "r", stdin);

    while (cin >> h >> w >> n, h|w) {
        int sx, sy;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                cin >> field[i][j];
                if (field[i][j] == 'S') {
                    sy = i, sx = j;
                }
            }
        }
        total_time = 0; // init
        cout << bfs(sy, sx, 1, n) << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 1005

char JOI[MAX][MAX];
int h,w,n;
int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};

pair<int, int> goal[10];
bool check(int a,int b){
    return (a>=1&&a<=h&&b>=1&&b<=w);
}

int step[MAX][MAX];
int bfs(const pair<int, int>& st, const pair<int, int>& en){
    queue<pair<int,int> > q;
    q.push(st);
    memset(step, -1, sizeof(step));
    step[st.first][st.second]=0;
    int stp=0;
    while(!q.empty()){
        pair<int, int> S=q.front(); q.pop();
        int x=S.first;  int y=S.second;
        stp=step[x][y];
        for(int i=0; i<4; i++){
            int cx=x+dx[i]; int cy=y+dy[i];
            if(check(cx, cy)){
                if(JOI[cx][cy]!='X'&&step[cx][cy]==-1){
                    if(cx==en.first&&cy==en.second) return stp+1;
                    q.push(make_pair(cx, cy));
                    step[cx][cy]=stp+1;
                }
            }
        }
    }
}
int main(){
    cin>>h>>w>>n;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin>>JOI[i][j];
            if(JOI[i][j]=='S') goal[0]=make_pair(i, j);
            else if(JOI[i][j]>='0'&&JOI[i][j]<='9'){
                int x=JOI[i][j]-'0';
                goal[x]=make_pair(i, j);
            }
        }
    }
    int ans=0;
    for(int i=0; i<n; i++){
        ans+=bfs(goal[i],goal[i+1]);
    }
    cout<<ans<<endl;
}