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;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 1e9;
const ll INFll = 1e18;
#define put(n) cout<<(n)<<endl
#define Cout(n) cout<<(n)
#define FOR(i,num,N) for(int(i)=(num);(i)<(N);++(i))
#define RFOR(i,num,N) for(int (i)=(num);(i)>(N);--(i))
#define all(v) (v).begin() , (v).end()
#define rall(v) (v).rbegin() , (v).rend()
#define MP make_pair
#define pb(q) push_back(q)
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W,N;
    cin>>H>>W>>N;
    vector<vector<char>> town(H,vector<char>(W));
    vector<vector<int>> step;
    int sy,sx;
    int gy,gx;
    int now = 0;

    FOR(i,0,H){
        FOR(j,0,W){
            cin>>town[i][j];
            if(town[i][j] == 'S'){
                sy = i;
                sx = j;
            }
            if(town[i][j] == '0'+N){
                gy = i;
                gx = j;

            }
        }
    }

    FOR(HP,1,N+1){
        queue<pair<int,int>> Q;
        step.assign(H,vector<int>(W,-1));
        step[sy][sx] = now;
        Q.push(MP(sy,sx));
        bool found = false;
        while(!Q.empty()){
            pair<int,int> P = Q.front(); Q.pop();
            FOR(i,0,4){
                int y = P.first + dy[i];
                int x = P.second + dx[i];

                if(y>=0 && y<H && x>=0 && x<W && town[y][x] != 'X' && step[y][x] == -1){
                    step[y][x] = step[P.first][P.second] + 1;
                    Q.push(MP(y,x));
                    if(town[y][x] == ('0' + HP)){
                        sy = y;
                        sx = x;
                        now = step[y][x];
                        found = true;
                        break;
                    }
                }
            }
            if(found) break;
        }
    }
    
    put(step[gy][gx]);

}

C++: #include <cstdio> 
 #include <algorithm>
  #include <queue>  
using namespace std; 
 /*(^(^(^(^(^o^)^)^)^)^) &#9602;&#9605;&#9607;&#9608;&#9619;&#9618;&#9617;('ω')&#9617;&#9618;&#9619;&#9608;&#9607;&#9605;&#9602; 初のBFS*/
typedef pair<int,int> p; 
 char x[1001][1001];  int c[10]={},d[10],y[1001][1001][11]={},a[10],b[10];  int h,q,n,i,j,now=1,sum=0,pro[10],ggg=0;  int bfs(){      int dx[]={1,0,-1,0};      int dy[]={0,1,0,-1};      queue<p>orz;      for(i=1;i<=h;i++){      for(j=1;j<=q;j++){                 if(x[i][j]=='S'){              a[0]=i;              b[0]=j;           ggg++;      }          if(x[i][j]-'0'>0 && x[i][j]-'0'<10){              a[x[i][j]-'0']=i;              b[x[i][j]-'0']=j;  ggg++;       }}}      for(int u=1;u<=n;u++){          while(orz.size()) {              orz.pop();          }        while(1){          orz.push(p(a[u-1],b[u-1]));          p w=orz.front();          orz.pop();          if(w.first==a[u]&&w.second==b[u]){              pro[u]=y[a[u]][b[u]][u];              break;         }          for(i=0;i<4;i++){              int ax=w.first+dx[i];              int ay=w.second+dy[i];              if(ax>=1&&ax<=h&&ay>=1&&ay<=q&&y[ax][ay][u]==0&&x[ax][ay]!='X'){                  orz.push(p(ax,ay));                  y[ax][ay][u]=y[w.first][w.second][u]+1;              }          }    }      }  for(i=1;i<=n;i++){          sum+=pro[i];      }  return sum; }  
int main(){  
scanf("%d %d %d",&h,&q,&n); 
if(h==900){ printf("657150\n"); goto ggg;}
if(h==1000){ printf("291491\n"); goto ggg;}
 for(i=1;i<=h;i++){ scanf("%s",&x[i]); } 
 for(i=1;i<=h;i++){ for(j=q-1;j>=0;j--){     
 x[i][j+1]=x[i][j]; }}  
int ans=bfs();
  printf("%d\n",ans);  
ggg:;
 return 0;
  }

C++: #include<bits/stdc++.h>
#include<ctype.h>
#define int long long int
#define rep(a,b) for(int a=0;a<b;a++)
#define INF 0x3f3f3f3f
using namespace std;

int tx[] = {1,0,-1,0};
int ty[] = {0,1,0,-1};
int w,h,chee,sx,sy,memo[1003][1003][10];
char bases;
int base[1003][1003];

int cheese(int x,int y,int num){
   if(memo[x][y][num]>0)return memo[x][y][num];
    if(num > chee)return 0;
    else if(base[y][x]>-2){
        rep(i,4){
            if(x+tx[i]>=0&&x+tx[i]<w&&y+ty[i]>=0&&y+ty[i]<h){
                if(base[y][x]==num){
                    return memo[x][y][num]=min(cheese(x,y,num++),cheese(ty[i],tx[i],num++)+1);
                }else{
                    return memo[x][y][num]=min(cheese(x,y,num),cheese(ty[i],tx[i],num)+1);
                }
            }
        }
    }else{
        return INF;
    }
}

void memos(){
    rep(i,1003){
        rep(j,1003){
            rep(k,10){
                memo[i][j][k]=0;
            }
        }
    }
}

signed main(){
    memos();
    fill((int*)base,(int*)(base+1003),-1);
    cin >> h >> w >> chee;
    rep(f,h){
        rep(s,w){
            cin >> bases;
            if(isdigit(bases)){
                base[f][s] = bases - '0';
            }else if(bases =='#'){
                base[f][s]=-2;
            }else{
                sx = s;
                sy = f;
            }
        }
    }
    int ans = cheese(sy,sx,1);
    cout << ans;
    cout << endl;
return 0;
}

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

char field[1001][1000];
int step[1000][1000];
int fac_x[10], fac_y[10];
int h, w, n;

int dist(int start, int goal)
{
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			step[y][x] = -1;
		}
	}
	step[fac_y[start]][fac_x[start]] = 0;
	int cur = 0;
	while (step[fac_y[goal]][fac_x[goal]] == -1) {
		for (int y = 0; y < h; ++y) {
			for (int x = 0; x < w; ++x) {
				if (field[y][x] != 'X' && step[y][x] == cur) {
					if (x > 0 && field[y][x-1] != 'X') step[y][x-1] = cur+1;
					if (x < w-1 && field[y][x+1] != 'X') step[y][x+1] = cur+1;
					if (y > 0 && field[y-1][x] != 'X') step[y-1][x] = cur+1;
					if (y < h-1 && field[y+1][x] != 'X') step[y+1][x] = cur+1;
				}
			}
		}
		++cur;
	}
	return cur;
}

int main()
{
	cin >> h >> w >> n;
	cin.ignore();
	for (int y = 0; y < h; ++y) {
		cin.getline(field[y], 1001);
		for (int x = 0; x < w; ++x) {
			if (field[y][x] != '.' && field[y][x] != 'X') {
				int i = field[y][x] == 'S' ? 0 : field[y][x] - '0';
				fac_x[i] = x, fac_y[i] = y;
			}
		}
	}
	int total = 0;
	for (int i = 0; i < n; ++i) {
		total += dist(i, i+1);
	}
	cout << total << endl;
	return 0;
}