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<algorithm>
using namespace std;

int n;
int dis[10][10];
bool use[10];

int rec(int pos,int hp){
  int i,m = 100000000;
  for(i=0;i<=n;i++){
    if(!use[i])break;
  }
  if(i==n+1)return 0;
  for(i=0;i<=n;i++){
    if(!use[i] && i<=hp){
      use[i] = true;
      m = min(m,rec(i,hp+i))+dis[pos][i];
    }
  }
  return m;
}

int main(){
  int h,w;
  int x[10],y[10];
  string map[1000];
  int dmap[1000][1000];
  queue<int> qx,qy;

  cin >> h >> w >> n;

  for(int i=0;i<h;i++)cin >> map[i];
 
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(map[i][j] == 'S'){
	x[0] = j;
	y[0] = i;
	break;
      }
      if(map[i][j] != 'X' && map[i][j] != '.'){
	x[map[i][j] - '0'] = j;
	y[map[i][j] - '0'] = i;
      }
    }
  }

  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      dis[i][j] = 10000000;
    }
  }
  
  for(int i=0;i<n;i++){
    while(!qx.empty())qx.pop();
    while(!qy.empty())qy.pop();
    for(int k=0;k<h;k++){
      for(int j=0;j<w;j++){
	dmap[k][j] = 10000000;
      }
    }
    dmap[y[i]][x[i]] = 0;
    qx.push(x[i]);
    qy.push(y[i]);

    while(!qx.empty()){
      if(qx.front()>0 && map[qy.front()][qx.front()-1] != 'X' && dmap[qy.front()][qx.front()-1] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()][qx.front()-1] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front()-1);
	qy.push(qy.front());
      }
      if(qy.front()>0 && map[qy.front()-1][qx.front()] != 'X' && dmap[qy.front()-1][qx.front()] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()-1][qx.front()] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front());
	qy.push(qy.front()-1);
      }
      if(qx.front()<w-1 && map[qy.front()][qx.front()+1] != 'X' && dmap[qy.front()][qx.front()+1] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()][qx.front()+1] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front()+1);
	qy.push(qy.front());
      }
      if(qy.front()<h-1 && map[qy.front()+1][qx.front()] != 'X' && dmap[qy.front()+1][qx.front()] > dmap[qy.front()][qx.front()] + 1){
	dmap[qy.front()+1][qx.front()] = dmap[qy.front()][qx.front()] + 1;
	qx.push(qx.front());
	qy.push(qy.front()+1);
      }
      qx.pop();
      qy.pop();
    }
    
    for(int j=i;j<=n;j++){
      dis[i][j] = dmap[y[j]][x[j]];
      dis[j][i] = dmap[y[j]][x[j]];
    }
  }
  dis[n][n] = 0;

  use[0] = true;
  for(int i=1;i<=n;i++)use[i] = false;

  cout << rec(0,1) << endl;
}

C++: #include<iostream>
#include<queue>
#include<stdlib.h>
#include<utility>
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
const int INF=-1;
char plat[1005][1005];
int d[1005][1005];
typedef pair<int,int> p;
int H,W,N;
queue<p> cheese;
int bfs(int& sx,int& sy,char energy)
{
    d[sx][sy]=0;
    cheese.push(p(sx,sy));
    while(cheese.size()){
        p test=cheese.front();
        cheese.pop();
        if(plat[test.first][test.second]==energy){
            sx=test.first;sy=test.second;
            return d[test.first][test.second];
        }
        for(int i=0;i<4;++i){
            int nx=test.first+dx[i];int ny=test.second+dy[i];
            if(nx>=0&&nx<W&&ny>=0&&ny<H&&plat[nx][ny]!='X'&&d[nx][ny]==INF){
                cheese.push(p(nx,ny));
                d[nx][ny]=d[test.first][test.second]+1;
            }
        }

    }
}

int main()
{

    cin>>W>>H>>N;
    int sx,sy;
    for(int i=0;i<W;++i){
        for(int j=0;j<H;++j){
            char u;
            cin>>u;
            if(u=='S'){
                sx=i;sy=j;
            }
            plat[i][j]=u;
        }
    }
    char e='1';
    int ans=0;
    while(N--){
        memset(d,-1,sizeof(d));
        ans+=bfs(sx,sy,e++);
        while(cheese.size())cheese.pop();

    }
    cout<<ans<<endl;

}

C++: #include<cstdio>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 1005
struct node{
    int x,y,step;
    node(int x=0,int y=0,int step=0):x(x),y(y),step(step) {}
};
char mp[MAXN][MAXN];
int vis[MAXN][MAXN];
int w,h,n;
int dir[10][10]={{1,0},{-1,0},{0,1},{0,-1}};
int bfs(node n1,node n2){
   memset(vis,0,sizeof(vis)); 
   queue<node>q;
   q.push(n1);
   while(!q.empty()){
       node tn=q.front();
       q.pop();
       for(int i=0;i<4;i++){
           int tx=tn.x+dir[i][0],ty=tn.y+dir[i][1];
           if(tx<0 || tx>=h || ty<0 || ty>=w) continue;
           if(vis[tx][ty]) continue;
           vis[tx][ty]=1;
           if(tx==n2.x && ty==n2.y) return tn.step+1;
           if(mp[tx][ty]!='X') q.push(node(tx,ty,tn.step+1));
       }
   }
} 
int main(){
    while(~scanf("%d%d%d",&h,&w,&n)){
        node n1,n2;
        for(int i=0;i<h;i++) scanf("%s",mp[i]);
        int ans=0;
        for(int i=0;i<h;i++) 
            for(int j=0;j<w;j++){
                if(mp[i][j]=='S') n1=node(i,j,0);
                if(mp[i][j]-'0'==1) n2=node(i,j,0);
            }
        ans+=bfs(n1,n2);
        for(int i=0;i<n-1;i++){
            for(int j=0;j<h;j++){
                for(int k=0;k<w;k++){
                    if(mp[j][k]-'0'==i+1) n1=node(j,k,0);
                    if(mp[j][k]-'0'==i+2) n2=node(j,k,0);
                }
            }
            ans+=bfs(n1,n2);
        }
        cout<<ans<<endl;
    }
    return 0;
}