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 <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,W,N;
  cin >> H >> W >> N;
  
  vector<string> S(H);
  for (int i=0; i<H; i++) cin >> S.at(i);
  
  vector<pair<int,int>> cheese_map(N+1);
  for (int i=0; i<H; i++) {
     for (int j=0; j<W; j++) {
       char c = S.at(i).at(j);
       if ( '1' <= c && c <= '9' ) {
         int n = c - '0';
         cheese_map.at(n) = make_pair( j, i);
       }
       if ( c == 'S') cheese_map.at(0) = make_pair( j, i);
     }
  }
  int time = 0;
  vector<int> xm = {-1, 0, 1, 0};
  vector<int> ym = { 0,-1, 0, 1};
  queue<pair<int, int>> q;
  
  for(int i=0; i<N; i++) {
    vector<vector<int>> time_map(H, vector<int>(W, -1));
    pair<int, int> st = cheese_map.at(i);
    pair<int, int> gl = cheese_map.at(i+1);
    time_map.at( st.second ).at( st.first ) = time;
    q.push( st );
    
    while (!q.empty()) {
      pair<int, int> sp = q.front(); 
      int sx = sp.first;
      int sy = sp.second;
      q.pop();
      
      for (int i=0; i<4; i++) {
        int x = sx + xm.at(i);
        int y = sy + ym.at(i);
        if ( x < 0 || W <= x ) continue;
        if ( y < 0 || H <= y ) continue;
        if ( S.at(y).at(x) == 'X' ) continue;
        if ( time_map.at(y).at(x) == -1) {
          q.push( make_pair( x, y ) );
          time_map.at(y).at(x) = time_map.at(sy).at(sx) + 1;
        }
      }
    }
    time = time_map.at( gl.second ).at( gl.first );
  }
  
  cout << time << endl;

}

C++: #include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define INF 10000000
#define rep(i,s,t) for(int i=s;i<=(t);i++)
#define MP(a,b) make_pair(a,b)
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int h,w,n;
char m[1000][1000];

int bfs(int s){
	static int d[1000][1000];
	queue<pair<int,int> > q;
	pair<int,int> a,b;
	rep(i,1,h)rep(j,1,w)
		if(m[i][j]=='0'+s){
			d[i][j]=0;
			q.push(MP(i,j));
		}
		else d[i][j]=INF;
	while(1){
		a = q.front();
		q.pop();
		rep(k,0,3){
			b = MP(a.first+dy[k],a.second+dx[k]);
			if(m[b.first][b.second]=='X')continue;
			if(d[a.first][a.second]+1 < d[b.first][b.second]){
				d[b.first][b.second] = d[a.first][a.second]+1;
				if(m[b.first][b.second]=='0'+s+1)return d[b.first][b.second];
				q.push(b);
			}
		}
	}
	return -1;
}
int main(){
	cin>>h>>w>>n;
	memset(m,'X',sizeof(m));
	rep(i,1,h)rep(j,1,w){
		cin>>m[i][j];
		if(m[i][j]=='S')m[i][j]='0';
	}
	int ans=0;
	rep(i,0,n-1)ans += bfs(i);
	cout<<ans<<endl;
}

C++: #include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define rep(x,y) for(x=0;x<(y);++x)
typedef pair<int, int> P;
const int MAX_N=1011;//提交之前改成1011
const int dw[4]={1,0,-1,0},dh[4]={0,1,0,-1};
const char sdt='S',vac='.',blc='X',hdns[11]={'0','1','2','3','4','5','6','7','8','9'};
void in();
void solve();
void bfs(char g);
int H,W,N;//高，&#23485;，目&#26631;数
int sh,sw;//起始位置
int cdis;//当前&#26102;&#38388;
char maze[MAX_N][MAX_N];//地&#22270;,h-第一&#32500;，w-第二&#32500;，从1&#24320;始
int dis[MAX_N][MAX_N];//距&#31163;&#26631;&#35760;

int main()
{
	in();
	solve();
	return 0;
}
void in()
{
	cin>>H>>W>>N;
	int h,w;
	for(h=1;h<=H;++h)
	{
		for(w=1;w<=W;++w)
		{
			cin>>maze[h][w];
			if(sdt==maze[h][w])
			{
				sh=h;
				sw=w;
			}
		}
	}
}
void solve()
{
	int n;
	int tm=0;
	for(n=1;n<=N;++n)
	{
		memset(dis,-1,sizeof(dis));//&#27599;一次都重新&#35774;置起始&#32456;止点，重新&#26631;&#35760;距&#31163;
		bfs(hdns[n]);
		tm+=cdis;
	}
	cout<<tm<<endl;
}
void bfs(char g)
{
	queue<P> que;
	P nl=P(sh,sw);
	int ch,cw;
	que.push(nl);
	dis[sh][sw]=0;
	int i,ndis;
	while(1)//一定会找到的，不用写que.size()
	{
		nl=que.front();
		que.pop();
		ndis=dis[nl.first][nl.second];
		rep(i,4)
		{
			ch=nl.first+dh[i];
			cw=nl.second+dw[i];
			if(!(H<ch||ch<1||W<cw||cw<1||blc==maze[ch][cw]||-1!=dis[ch][cw]))
			{
				if(g==maze[ch][cw])
				{
					cdis=ndis+1;
					sh=ch;
					sw=cw;
					return;
				}
				que.push(P(ch,cw));
				dis[ch][cw]=ndis+1;
			}
		}
	}
FIND:
	return;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
vector<vector<int>> d(1000,vector<int>(1000,INF));
vector<vector<char>> maze;
vector<pair<int,int>> goals;
P start;
int R,C,N;
int bfs(int sx,int sy,int gx,int gy){
  queue<P> que;
  que.push(P(sx,sy));
  d[sx][sy]=0;
  while(que.size()){
    P p=que.front();que.pop();
    if(p.first==gx&&p.second==gy)break;
    rep(i,4){
      int nx = p.first+dx[i];
      int ny = p.second+dy[i];
      if(0<=nx && nx<R && 0<=ny && ny<C && maze[nx][ny] != 'X' && d[nx][ny]==INF){
        que.push(P(nx,ny));
        d[nx][ny] = d[p.first][p.second]+1;
      }
    }
  }
  return d[gx][gy];
}
      
int main(){
  cin >> R >> C >>N;
  maze.resize(R);
  goals.resize(N);
  rep(i,R){
    rep(j,C){
      char c;
      cin >> c;
      maze[i].push_back(c);
    }
  }
  /*rep(i,R){
    rep(j,C){
      cout << maze[i][j];
    }
    cout << endl;
  }*/
  goals[0].first = 10000;
  rep(i,N){
    rep(j,R){
      rep(k,C){
        int a = i+1;
        char ka = a+'0';
        if(maze[j][k]=='S'){
          start.first=j;
          start.second=k;
        }
        if(maze[j][k]==ka){
          goals[i].first=j;
          goals[i].second=k;
        }
      }
    }
  }
  //cout << start.first << "," << start.second << endl;
  /*rep(i,N){
    cout << goals[i].first << "," << goals[i].second << endl;
  }*/
  int path = bfs(start.first,start.second,goals[0].first,goals[0].second);
  rep(i,N-1){
    rep(j,1000){
      rep(k,1000){
        d[j][k] = INF;
      }
    }
    path+=bfs(goals[i].first,goals[i].second,goals[i+1].first,goals[i+1].second);
  }
  cout << path << endl;
                                                                   
  
  //int res = bfs();
  //cout << res << endl;


  return 0;
}