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>
#define INF 1e9
using namespace std;
int H,W,N;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int d[1005][1005];
int X[1000000],Y[1000000];
int headX, headY;
int tailX, tailY;
int sx[10],sy[10];
void pushX(int x){
  X[tailX++]=x;
  tailX%=1000000;
}
int popX(){
  return X[headX++];
  headX%=1000000;
}
void pushY(int y){
  Y[tailY++]=y;
  tailY%=1000000;
}
int popY(){
  return Y[headY++];
  headY%=1000000;
}
void re(){
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      d[i][j]=INF;
    }
  }
}
int main(){
  int cnt=0;
  cin>>H>>W>>N;
  char mp[1005][1005];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>mp[i][j];
      if(mp[i][j]=='.' || mp[i][j]=='X') continue;
      else if(mp[i][j]=='S'){
	sx[0]=j;
	sy[0]=i;
      }
      else{
	sx[mp[i][j]-'0']=j;
	sy[mp[i][j]-'0']=i;
      }
    }
  }
  
  re();
  d[sy[cnt]][sx[cnt]]=0;
  int ke=0;
  while(1){
    if(cnt==N) break;
    pushX(sx[cnt]);
    pushY(sy[cnt]);
    d[sy[cnt]][sx[cnt]]=ke;
    cnt++;
    
    while(1){
      int x = popX();
      int y = popY();
      
      if(x==sx[cnt] && y==sy[cnt]) break;
      
      for(int i=0;i<4;i++){
	int nx = x + dx[i], ny = y + dy[i];
	if(nx < 0 || ny < 0 || nx >= W || ny >= H || mp[ny][nx]=='X') continue;
	
	if(d[ny][nx] > d[y][x]+1){
	  d[ny][nx] = d[y][x]+1;
	  pushX(nx);
	  pushY(ny);
	}
      }
    }
    headX=0;
    headY=0;
    tailX=0;
    tailY=0;
    /*
    for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(d[i][j]==INF) cout<<0;
      else cout<<d[i][j];
      cout<<" ";
    }
    cout<<endl;
  }
    */
    ke=d[sy[cnt]][sx[cnt]];
    //cout<<sy[cnt]<<" "<<sx[cnt]<<endl;
    //cout<<ke<<endl;
    re();
    
    
  }
  cout<<ke<<endl;
  return 0;
    
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef struct xyt{
	int xx;
	int yy;
	int tt;
}xyt;

int H, W, N, minute = 0;
char area[1001][1001] = {{0}};
bool areab[1001][1001] = {};
bool visit[1001][1001];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};


void dfs(int x, int y){
	int X, Y, time;
	int HP =1;
	xyt start = {x, y, 0};
	queue <xyt> Q;
	Q.push (start);
	for(int i = 1; i<=1000;i++){
		for(int j = 1; j<= 1000 ;j++){
			visit[j][i]=0;
		}
	}

	while(HP <= N){
		X = Q.front().xx;
		Y = Q.front().yy;
		time = Q.front().tt;
		Q.pop();
		
		//cout << HP << endl;
		for(int i = 0; i <= 4 ;i++){
			int nx = X + dx[i];
			int ny = Y + dy[i];
			//cout << nx <<" " << ny << " " << area[nx][ny] << endl;
			xyt now;
			if(X + dx[i] <= 0 || Y + dy[i] <= 0 || X + dx[i] > W || Y + dy[i] > H)continue;
			if(visit[nx][ny]==1)continue;
			
			if(areab[X + dx[i]][Y + dy[i]] == 0){
				if(area[X + dx[i]][Y + dy[i]] == HP + '0'){
					minute += time + 1;
					while(!Q.empty()){
						Q.pop();
					}
					now.xx = X + dx[i];
					now.yy = Y + dy[i];
					now.tt = 0;
					Q.push (now);
					HP++;
					for(int k = 1; k<=1000;k++){
						for(int l = 1; l<= 1000 ;l++){
							visit[k][l]=0;
						}
					}
					break;
				}else{
					now.xx = X + dx[i];
					now.yy = Y + dy[i];
					now.tt = time + 1;
					Q.push (now);
					visit[X+dx[i]][Y+dy[i]]=1;
				}
			}
		}
	}
	return;
}


int main(){
	cin >> H >> W >> N;
	for(int i = 1; i <= H ;i++){
		for(int j = 1; j <= W ;j++){
			cin >> area[j][i];
			if(area[j][i] == 'X'){
				areab[j][i] = 1;
			}
		}
	}
	for(int i = 1; i <= H ;i++){
		for(int  j = 1; j <= W ;j++){
			if(area[j][i] == 'S'){
				dfs(j, i);
			}
		}
	}
	cout << minute << endl;
	return 0;
}

C++: #include<iostream>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef pair<int,int>Pt;
#define fr first
#define sc second
Pt st[10];
int h,w,n,dx[]={0,1,0,-1},dy[]={1,0,-1,0},used[1000][1000];
char mas[1000][1000],tmp[]="S123456789";
int bfs(Pt,Pt);
int main(){
  cin >> h >> w >> n;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> mas[i][j];
      for(int k=0;k<=n;k++){
	if(mas[i][j] == tmp[k]) st[k] = Pt(i,j);
      }
    }
  }
  int cnt = 0;
  for(int i=1;i<=n;i++){
    memset(used,-1,sizeof(used));
    cnt += bfs(st[i-1],st[i]);
  }
  cout << cnt << endl;
}

int bfs(Pt S,Pt G){
  queue<Pt> que;
  que.push(S);
  used[S.fr][S.sc] = 0;
  while(!que.empty()){
    Pt p = que.front();
    que.pop();
    if(p == G) break;
    for(int i=0;i<4;i++){
      int nx = p.fr + dx[i],ny = p.sc + dy[i];
      if(nx>=0 && nx<h && ny>=0 && ny<w && used[nx][ny]==-1 && mas[nx][ny]!='X'){
	used[nx][ny] = used[p.fr][p.sc] + 1;
	que.push(Pt(nx,ny));
      }
    }
  }
  return used[G.fr][G.sc];
}

C++: #include <cstdio>
#include <map>
#include <queue>
#include <string>

using namespace std;

const int INF = 100000000;
const int MAX_H = 1000;
const int MAX_W = 1000;
const int MAX_N = 9;

int H, W, N;
char field[MAX_H][MAX_W];
int d[MAX_H][MAX_W]; // ?????????????????\??´?????§??????????????°, 1~N??§?????????????????§????????°??????+1
int step[MAX_N+1]; // ?????????????????\??´?????§??????????????°, 1~N??§?????????????????§????????°??????+1
int sx, sy, gx, gy;
int power = 1; // ??????????????????
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

typedef pair<int, int> P;

void reset_d() {
  for (int i = 0; i < H; i++)
    for(int j = 0; j < W; j++) d[i][j] = INF;
}

int bfs(int sx, int sy, int c) {
  queue<P> que;
  reset_d();
  d[sx][sy] = c;
  que.push(P(sx, sy));
  while(que.size()) {
    P p = que.front(); que.pop();
    if (field[p.first][p.second] - '0' == N && step[N] != 0) break;
    for (int i = 0; i < 4; i++) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if ( 0 <= nx && nx <= H && 0 <= ny && ny <= W && field[nx][ny] != 'X' && d[nx][ny] == INF) {
        d[nx][ny] = d[p.first][p.second] + 1;
        que.push(P(nx, ny));
        if (field[nx][ny] - '0' == power) {
          step[power] = d[nx][ny];
          power++;
          return bfs(nx, ny, d[nx][ny]);
        }
      }
    }
  }
  return step[N];
}

void solve(int sx, int sy) {
  int res = bfs(sx, sy, 0);
  printf("%d\n", res);
}


int main() {
  scanf("%d %d %d", &H, &W, &N);
  for (int i = 0; i < H; i++) {
    scanf("%s", field[i]);
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (field[i][j] == 'S') {
        sx = i;
        sy = j;
      }
      if (field[i][j] == 'G') {
        gx = i;
        gy = j;
      }
    }
  }
  solve(sx, sy);
  return 0;
}