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<functional>
#include<queue>
#include<cctype>
#include<algorithm>

#define MAXN 1024

using namespace std;

struct state{
  int i,j;
  int cost;
  state(int i, int j, int cost):i(i),j(j),cost(cost){}
};

const int di[] = {-1,0,1,0};
const int dj[] = {0,1,0,-1};
const int infty =  1<<28;

int dist[10][10];

bool isinside(int i, int j, int H, int W){
  return 0<=i&&i<H&&0<=j&&j<W;
}

int compute_dist(int n, int H, int W, char M[MAXN][MAXN]){
  int si,sj;
  queue< state > q;
  bool vis[H][W];
  dist[n][n]=0;
  for(int i = 0; i < H; ++i){
    for(int j = 0; j < W; ++j){
      vis[i][j]=false;
      if(M[i][j]-'0' == n){
	si = i;
	sj = j;
      }
    }
  }
  q.push( state(si,sj,0) );
  while(!q.empty()){
    state nst=q.front();q.pop();
    for(int k = 0; k < 4; ++k){
      int ni = nst.i + di[k];
      int nj = nst.j + dj[k];
      if( isinside(ni,nj,H,W) && !vis[ni][nj] && M[ni][nj] !='X' ){
	if( isdigit(M[ni][nj]) ){
	  dist[n][M[ni][nj]-'0'] = nst.cost+1;
	}
	vis[ni][nj]=true;
	q.push( state(ni,nj,nst.cost+1) );
      }
    }
  }
}

int solve(int H, int W, int N, char M[MAXN][MAXN])
{
  int vis[N];
  for(int i = 0; i <= N; ++i){
    compute_dist(i,H,W,M);
    if(i>0)vis[i-1]=i;
  }
  int min_cost = infty;
  do{
    int now=0;
    int now_power = 1;
    int cost=0;
    for(int i = 0; i < N; ++i){
      if( now_power < vis[i] ){
	cost = infty;
	break;
      }else{
	now_power += 1;
	//cout << now << ' ' << vis[i] << ' ' << dist[now][vis[i]] << endl;
	cost += dist[now][vis[i]];
	now = vis[i];
      }
    }
    min_cost = min( min_cost, cost );
  }while(next_permutation(vis,vis+N));
  return min_cost;
}

int main()
{
  int H,W,N;
  while(cin >> H >> W >> N){
    static char M[MAXN][MAXN];
    for(int i = 0; i < H; ++i){
      for(int j = 0; j < W; ++j){
	cin >> M[i][j];
	if(M[i][j]=='S')M[i][j]='0';
      }
    }
    cout << solve(H,W,N,M) << endl;
  }
  return 0;
}

C++: #include<stdio.h>
#include<string.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++: #include "StdAfx.h"
#include <iostream>   
#include<stack> 
#include<queue> 
#include<string> 
#include <math.h>
using namespace std;

const int MAX_H = 1000;
const int MAX_W = 1000;
const int a = 100000000;

typedef pair<int, int> P;

int H = 0, W = 0, N = 0; 
 
int food[11][2];
char cheese[MAX_H][MAX_W] = {0}; 
int r[MAX_H][MAX_W]; 
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; 

int search(int &sx, int &sy, int &ex, int &ey)
{
 
    P p;
    queue<P> que;
    for(int i=0; i<H; i++)
   {
        for(int j=0; j<W; j++)
       {
           r[i][j] = a;

        }
    }
    que.push(P(sx,sy));
    r[sx][sy] = 0;

    while(que.size())
   {  
        p = que.front();
        que.pop();
        if(p.first == ex && p.second == ey)
			break;
	

	    for(int i=0; i<4; i++)
	   {
		    int xn = p.first + dx[i];
		    int yn = p.second + dy[i];


		    if(xn >= 0 && xn < H && yn >= 0 && yn < W && cheese[xn][yn]!='X' && r[xn][yn] == a )
		   {
			    que.push(P(xn,yn));
			    r[xn][yn] = r[p.first][p.second] + 1;
		    }
	    }

	}
	return r[ex][ey];
}

int main()
{
	int dis = 0;
    cin >> H >> W >> N;
    for(int i=0; i<H; i++)
   {
        for(int j=0; j<W; j++)
       {
          cin >> cheese[i][j];
          if(cheese[i][j] == 'S')
         {
             food[0][0] = i;
             food[0][1] = j;
             cheese[i][j] = '.';
          }
          if(cheese[i][j]>48&&cheese[i][j]<58)
         {
             int num = cheese[i][j] - 48;  
             food[num][0] = i;
             food[num][1] = j;
          }
       }
    }
   

    for(int i=0; i<N; i++)
   {
       dis += search(food[i][0], food[i][1], food[i+1][0], food[i+1][1]); 
    }
    
	cout << dis << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1050;

char s[N][N];
bool vis[N][N];
int n,m,tot,res,ex,ey;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int d[N][N];

void bfs(int x,int y,int cnt){
	memset(vis,false,sizeof(vis));
	queue<P>q;
	while(!q.empty()) q.pop();
	P sta;
	sta.fir=x,sta.sec=y;
	vis[x][y]=true;
	q.push(sta);
	while(!q.empty()){
		P p=q.front();
		q.pop();
		if(s[p.fir][p.sec]==cnt+'0'){
			if(cnt<tot) bfs(p.fir,p.sec,cnt+1);
			return;
		}
		for(int i=0;i<4;i++){
			int tx=p.fir+dx[i];
			int ty=p.sec+dy[i];
			if(!vis[tx][ty]&&s[tx][ty]!='X'&&tx>=1&&tx<=n&&ty>=1&&ty<=m){
				res++;
				vis[tx][ty]=true;
				q.push(P(tx,ty));
				d[tx][ty]=d[p.fir][p.sec]+1;
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&tot);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='S') {bfs(i,j,1);}
			if(s[i][j]==tot+'0') ex=i,ey=j;
		}
	}
	printf("%d\n",d[ex][ey]);
	return 0;
}