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<set>
#include<queue>
#include<utility>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<numeric>
#include<functional>
#include<string>
#include<iostream>
using namespace std;
const long long int one = 1;
const long long int big = (one<<20);
typedef long long int llint;

//	. 0x2e	X 0x58	S 0x53	1~ 0x31~
int main(void){
	int H,W,N,h,i,j,x,y,t,ans=0;
	queue<tuple<int,int,int>> que;
	static char Chezu[1002][1002];//??°?????¨???????????????????????????
	static int time[1002][1002];
	int Cx[10];
	int Cy[10];
	scanf("%d %d %d",&H,&W,&N);
	for(j=0;j<=W+1;j++){Chezu[0][j]=0x58;}
	for(i=1;i<=H;i++){Chezu[i][0]=0x58;scanf(" %s",Chezu[i]+1);Chezu[i][W+1]=0x58;}
	for(j=0;j<=W+1;j++){Chezu[H+1][j]=0x58;}

	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			if(Chezu[i][j]==0x53){
				Cx[0]=i;Cy[0]=j;
			}
			if(0x31<=Chezu[i][j]&&Chezu[i][j]<=0x39){
				Cx[Chezu[i][j]-0x30]=i;
				Cy[Chezu[i][j]-0x30]=j;
			}
		}
	}
	for(h=0;h<N;h++){
		while(!que.empty()){que.pop();}
		for(i=0;i<H+2;i++){
			for(j=0;j<W+2;j++){
				time[i][j]=big;
			}
		}
		que.push(make_tuple(Cx[h],Cy[h],0));
		while(!que.empty()){
			x=get<0>(que.front());
			y=get<1>(que.front());
			t=get<2>(que.front());
			que.pop();
			if(x==Cx[h+1]&&y==Cy[h+1]){break;}
			if(time[x][y]<=t){ continue; }
			time[x][y]=t;
			if(Chezu[x+1][y]!=0x58){ que.push(make_tuple(x+1,y,t+1)); }
			if(Chezu[x-1][y]!=0x58){ que.push(make_tuple(x-1,y,t+1)); }
			if(Chezu[x][y+1]!=0x58){ que.push(make_tuple(x,y+1,t+1)); }
			if(Chezu[x][y-1]!=0x58){ que.push(make_tuple(x,y-1,t+1)); }
		}
		ans+=t;
	}
	printf("%d\n",ans);
	return 0;
}

C++: #include<cmath>
#include<cctype>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<utility>
#include<queue>

using namespace std;
#define is ==
int W,H,N;
const int MAX = 1000;
char f[MAX][MAX];
int d[MAX][MAX];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
struct P
{
  int x,y;
};
inline bool check(P p){
  return p.x < 0 or p.x >= W or p.y < 0 or p.y >= H;
}
int bfs(P s,int goal){
  if(goal > N+'0')return 0;
  fill(*d,*(d+MAX),-1);
  queue<P> que;
  que.push(s);
  d[s.x][s.y] = 0;
  while(!que.empty()){
    P cur = que.front();que.pop();

    if(f[cur.x][cur.y] is goal)return d[cur.x][cur.y] + bfs(cur,goal+1);

    for (int i = 0; i < 4; ++i){
      P np = {cur.x+dx[i],cur.y+dy[i]};
      if(check(np))continue;
      if(f[np.x][np.y] is 'X')continue;
      if(d[np.x][np.y] > -1)continue;//visited
      d[np.x][np.y] = d[cur.x][cur.y] + 1;
      que.push(np);
    }
  }
  cout << "no goal!" << endl;
  return 0;//error
}

int main(){
  ios::sync_with_stdio(false);
  cin >> H >> W >> N;
  P s;
  for (int j = 0; j < H; ++j){
    for (int i = 0; i < W; ++i){
      cin >> f[i][j];
      if(f[i][j] == 'S')s.x = i,s.y = j;
    }
  }
  cout << bfs(s,'1') << endl;
  
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define FF first.first
#define FS first.second
typedef pair<int,int>P;
typedef pair<P,int>PP;
char map1[1001][1001];
char mapcpy[1001][1001];
int main(void)
{
	int h,w,n;
	int i,j,cnt,sx,sy;
	int xx,yy,cost;
	int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
	queue<PP> que;
	
	cin>>h>>w>>n;
	
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>map1[i][j];
			if(map1[i][j]=='S'){
				sx=j;
				sy=i;
			}
		}	
	}
	for(i=0;i<h;i++){
		strcpy(mapcpy[i],map1[i]);
		//cout<<mapcpy[i]<<endl;
	}
	
	cost=0;cnt=1;
	que.push(PP(P(sy,sx),cost));
	while(!que.empty()){
		PP q=que.front();
		que.pop();
		
		//cout<<"yy="<<q.FF<<" "<<"xx="<<q.FS<<"cost="<<cost<<endl;
		if(map1[q.FF][q.FS]!='X'){
			if(map1[q.FF][q.FS]>='0'&&map1[q.FF][q.FS]<='9'){
				//cout<<"IN"<<endl;
				//cout<<endl;
				if(map1[q.FF][q.FS]-'0'==cnt){
					cnt++;
					for(i=0;i<h;i++){
						strcpy(map1[i],mapcpy[i]);
					}
					while(!que.empty()){
						que.pop();
					}
				}
			}




			/*for(i=0;i<h;i++){
				for(j=0;j<w;j++){
					cout<<map1[i][j];
				}	
				cout<<endl;
			}*/

			for(i=0;i<4;i++){
				yy=q.FF+dy[i];
				xx=q.FS+dx[i];
				cost=q.second;
				if(xx>=0&&yy>=0&&xx<w&&yy<h&&map1[yy][xx]!='X'){
					
					que.push(PP(P(yy,xx),cost+1));
				}	
			}
		}
		map1[q.FF][q.FS]='X';
		if(cnt>n) break;
	}
	/*for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cout<<map1[i][j];
		}	
		cout<<endl;
	}*/
	cout<<cost<<endl;
	
	
	return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int xs[10],ys[10];
int H,W,N;
string S[1002];
int main()
{
	scanf("%d%d%d",&H,&W,&N);
	for(int i=0;i<W+2;i++){
		S[0]+='X';
		S[H+1]+='X';
	}
	for(int i=1;i<=H;i++){
		string x;
		cin >> x;
		S[i]+='X'+x+'X';
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(S[i][j]!='X'&&S[i][j]!='.'){
				if(S[i][j]=='S'){
					xs[0]=j;
					ys[0]=i;
				}
				else{
					xs[S[i][j]-'0']=j;
					ys[S[i][j]-'0']=i;
				}
			}
		}
	}
	int XX[102][102];
	bool FF[102][102];
	int ans=0;
	vector<pair<int,int> >vec1;
	vector<pair<int,int> >vec2;
	int dx[4]={-1,0,0,1};
	int dy[4]={0,-1,1,0};
	for(int x=0;x<N;x++){
		vec1.clear();
		vec2.clear();
		for(int i=0;i<H+2;i++)for(int j=0;j<W+2;j++){
			XX[i][j]=-1;
			FF[i][j]=false;
		}
		int cou=0;
		XX[ys[x]][xs[x]]=cou;
		FF[ys[x]][xs[x]]=true;
		vec1.push_back(make_pair(ys[x],xs[x]));
		while(XX[ys[x+1]][xs[x+1]]==-1){
			vec2.clear();
			for(int i=0;i<vec1.size();i++){
				for(int j=0;j<4;j++){
					if(S[vec1[i].first+dy[j]][vec1[i].second+dx[j]]=='X')continue;
					if(XX[vec1[i].first+dy[j]][vec1[i].second+dx[j]]!=-1)continue;
					if(FF[vec1[i].first+dy[j]][vec1[i].second+dx[j]])continue;
					vec2.push_back(make_pair(vec1[i].first+dy[j],vec1[i].second+dx[j]));
					FF[vec1[i].first+dy[j]][vec1[i].second+dx[j]]=true;
				}
			}
			vec1.clear();
			for(int i=0;i<vec2.size();i++)vec1.push_back(vec2[i]);
			cou++;
			for(int i=0;i<vec1.size();i++){
				XX[vec1[i].first][vec1[i].second]=cou;
			}
			
		}
		ans+=XX[ys[x+1]][xs[x+1]];
	}
	printf("%d\n",ans);
	return 0;
}