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 <algorithm>
#include <iostream>
#include <string.h>
#include <map>
#include <queue>

using namespace std;

#define int_ int64_t
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define lb long double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

ll a[8];
map<string,ll> res;

int main()
{
    string s="01234567";
    queue<string> q;
    q.push(s);
    res[s]=1;
    while (!q.empty()) {
        string cur=q.front();
        q.pop();
        ll idx=0;
        for (ll i=0;i<8;i++) {
            if (cur[i]=='0') {
                idx=i;
                break;
            }
        }
        if (idx!=0&&idx!=4) {
            string tmp=cur;
            swap(tmp[idx],tmp[idx-1]);
            if (res[tmp]==0) {
                q.push(tmp);
                res[tmp]=res[cur]+1;
            }
        }
        if (idx!=3&&idx!=7) {
            string tmp=cur;
            swap(tmp[idx],tmp[idx+1]);
            if (res[tmp]==0) {
                q.push(tmp);
                res[tmp]=res[cur]+1;
            }
        }
        if (idx<4) {
            string tmp=cur;
            swap(tmp[idx],tmp[idx+4]);
            if (res[tmp]==0) {
                q.push(tmp);
                res[tmp]=res[cur]+1;
            }
        }
        if (idx>4) {
            string tmp=cur;
            swap(tmp[idx],tmp[idx-4]);
            if (res[tmp]==0) {
                q.push(tmp);
                res[tmp]=res[cur]+1;
            }
        }
    }
    while (~scanf("%lld",a)) {
        string t=to_string(a[0]);
        for (ll i=1;i<8;i++) {
            scanf("%lld",a+i);
            t+=to_string(a[i]);
        }
        printf("%lld\n",res[t]-1);
    }
}

C++: #include <iostream>
#include <utility>
#include <queue>
#define N 1001
using namespace std;
int bfs(pair<int,int>,pair<int,int>);
int h,w,d[N][N];
string str[N];
int main(){
  int n,i,j,sum;
  pair<int,int> P[10];
  cin >> h >> w >> n;
  for(i=0;i<=w;i++) str[0]+='X';
  for(i=1;i<=h;i++) cin >> str[i],str[i]='X'+str[i];
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(str[i][j]=='S') P[0].first=i,P[0].second=j;
      if('1'<=str[i][j]&&str[i][j]<='9'){
	P[str[i][j]-'0'].first=i;
	P[str[i][j]-'0'].second=j;
      }
    }
  }
  sum=bfs(P[0],P[1]);
  for(i=1;i<n;i++) sum+=bfs(P[i],P[i+1]);
  cout << sum << endl;
}
int bfs(pair<int,int> s,pair<int,int> g){
  int i,j,ret;
  pair<int,int> t;
  pair<int,int> u;
  queue< pair<int,int> > Q;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      d[i][j]=-1;
    }
  }
  Q.push(s);
  d[s.first][s.second]=0;
  while(Q.empty()!=1){
    u=Q.front();
    if(str[u.first][u.second]==str[g.first][g.second]){
      ret=d[u.first][u.second];
      break;
    }
    Q.pop();
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(u.first==i&&u.second==j){
	  if(d[i][j-1]==-1&&str[i][j-1]!='X'){
	    d[i][j-1]=d[u.first][u.second]+1;
	    t.first=i;
	    t.second=j-1;
	    Q.push(t);
	  }
	  if(d[i][j+1]==-1&&str[i][j+1]!='X'){
	    d[i][j+1]=d[u.first][u.second]+1;
	    t.first=i;
	    t.second=j+1;
	    Q.push(t);
	  }
	  if(d[i-1][j]==-1&&str[i-1][j]!='X'){
	    d[i-1][j]=d[u.first][u.second]+1;
	    t.first=i-1;
	    t.second=j;
	    Q.push(t);
	  }
	  if(d[i+1][j]==-1&&str[i+1][j]!='X'){
	    d[i+1][j]=d[u.first][u.second]+1;
	    t.first=i+1;
	    t.second=j;
	    Q.push(t);
	  }
	}
      }
    }
  }
  return ret;
}

C++: #include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
#include <sstream>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;

template <class T>
void initvv(vector<vector<T> > &v,int a,int b, const T  &t = T()){
	v.assign(a,vector<T>(b,t));
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int main(){
	int H,W;
	int N;
	cin>>H>>W>>N;

	vector<vint> vv;
	initvv(vv,H,W);
	pii pos;
	rep(i,H){
		rep(j,W){
			char t;
			cin>>t;
			if(t=='S'){
				vv[i][j]=0;
				pos.F=i;
				pos.S=j;
			}
			else if(t=='.') vv[i][j]=10;
			else if(t=='X') vv[i][j]=-10;
			else vv[i][j]=t-'0';
		}
	}
	// queue<pii> q;
	ll ans=0;
	rep(i,N){
		queue<pair<pii,int> > q;
		q.push(mkp(pos,0));
		vector<vint> vis;
		initvv(vis,H,W);
		rep(k,H) rep(j,W) vis[k][j]=1;
		while(!q.empty()){
			pair<pii,int> tmp=q.front();
			q.pop();
			if(vv[tmp.F.F][tmp.F.S]==i+1){
				pos=tmp.F;
				ans+=tmp.S;
				break;
			}
			rep(j,4){
				int x=tmp.F.F+dx[j];
				int y=tmp.F.S+dy[j];
				if(x<H&&y<W&&x>=0&&y>=0&&vis[x][y]&&vv[x][y]!=-10){
					q.push(mkp(mkp(x,y),tmp.S+1));
					vis[x][y]=0;
				}
			}
		}
	}
	cout<<ans<<endl;
	// rep(i,H){
		// rep(j,W){
			// cout<<vv[i][j]<<" ";
		// }
		// cout<<endl;
	// }
	// cout<<endl;
}

C++: #include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int que[1000000][3];
char str[1000][1001],flg[1000][1000]; 
int main(void){
	int i,j,k;
	int x,y,xx,yy,h,w,n,tai,p1,p2;
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	int min,max=1000000;
	cin>>h>>w>>n;
	for(i=0;i<=h;i++){
		for(j=0;j<=w;j++) flg[i][j]=1;
	}
	for(i=0;i<h;i++) cin>>str[i];
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(str[i][j]=='S'){
				que[0][0]=i; que[0][1]=j; que[0][2]=0;
				flg[i][j]==0;
			}
		}	
	}
	tai=1; p1=0; p2=0;
	for(i=1;i<=n;i++){
		//cout<<i<<endl;
		if(p2>max) break;
		while(1){
			y=que[p1][0]; x=que[p1][1];
			if(str[y][x]-'0'==tai){
				tai++;
		//		printf("aaaaaaaa\n");
				for(j=0;j<h;j++){
					for(k=0;k<w;k++) flg[j][k]=1;
				}
				flg[y][x]==0;
				que[0][0]=y; que[0][1]=x; que[0][2]=que[p1][2];
				p1=0; p2=0;
				break;
			}
			for(j=0;j<4;j++){
				yy=y+dy[j]; xx=x+dx[j];
				if(yy>=0&&xx>=0&&yy<h&&xx<w&&str[yy][xx]!='X'&&flg[yy][xx]!=0){
					p2++;
					que[p2][0]=yy; que[p2][1]=xx; que[p2][2]=que[p1][2]+1;
					flg[yy][xx]=0;
//					printf("yy=%d xx=%d\n",yy,xx);
				}
			}
			p1++;
			//printf("%d %d\n",p1,p2);
		}
		min=que[p1][2];
	}
	cout<<min<<endl;
	return 0;
}