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 <iostream>
#include <stdlib.h> 
#include <queue>
#include <utility>

using namespace std;

typedef struct pair{
    int x;
    int y;
}pair_t;

const int INF = 10000000;

int bfs();

int H,W,N;
char** field;
int** d;


int dx[4] = {0,0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int sx, sy;

int main() {
      cin >> H >> W >> N;
      field =(char**) malloc(sizeof(char*)*H);
      d =(int**) malloc(sizeof(int*)*H);
    
      for(int i=0; i<H;i++){
          char* row = (char*)malloc(sizeof(char)*W);
          int* dr = (int*)malloc(sizeof(int)*W);
          cin >> row;
          field[i] = row;
          d[i] = dr;
      }
    
      for(int i=0; i < H; i++){
          for(int j=0; j < W; j++){
    
              if(field[i][j]=='S'){
                  sx = j;
                  sy = i;
                  field[i][j] = '.';
              }
          }
      }

      int result = bfs();
    
      cout << result << endl;

     // for(int i=0; i<H; i++){
     //     free(field[i]);
     // }

     // free(field);
  

  return 0;
}

void init_d(int x, int y, int n){

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

    d[y][x] = n;
}

void clear(queue<pair_t> &q){
    queue<pair_t> empty;
    swap(q, empty);
}

int bfs(){
    int cheeze = 1;

    queue<pair_t> que;

    pair_t first = {sx, sy};
    que.push(first);
    d[sy][sx] = 0;

    init_d(sx, sy, 0);

    while(que.size()){
NEXT:
        pair_t p = que.front();
        que.pop();

        for(int i = 0; i<4; i++){
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];

            if(0<= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] != 'X' && d[ny][nx] == INF){
                if(field[ny][nx] != '.'){
                    if((int)(field[ny][nx] - '0') == cheeze ){

                        if(cheeze == N){
                            return d[p.y][p.x] + 1;
                        }


                        init_d(nx, ny, d[p.y][p.x] + 1);
                        clear(que);

                        pair_t n = {nx, ny};
                        que.push(n);
                        
                        cheeze++;
                        goto NEXT;
                    }
                }

                pair_t n = {nx, ny};
                d[ny][nx] = d[p.y][p.x] + 1;
                que.push(n);

            }
        }
    }
    return -1;
}

C++: #include<iostream>
#include<queue>
#include<climits>
#include<cstdlib>
using namespace std;
int d[1111][1111];
char input[1111][1111];
bool visited[1111][1111];
int H,W,N,S_x,S_y,answer=0;
const int dirx[]={0,-1,0,1};
const int diry[]={1,0,-1,0};
int now='1';
int D[11];
queue<int> q;
void BFS();
void clean();
int main(){
	int i,j;
	char ch; 
	cin>>H>>W>>N;
	for(i=0;i<H*W;i++){
		cin>>ch;
		input[i%W][i/W]=ch;
		d[i%W][i/W]=0;
		if(ch=='S'){
			S_x=i%W;S_y=i/W;
		}
	}
	while(now<=N+48){
		BFS();
		now++;
	}
	for(i=1;i<=N;i++){
		answer+=D[i];}
	cout<<answer<<endl;
}
void BFS(){
	int x,y,k,mx,my;
	q.push(S_x);
	q.push(S_y);
	visited[S_x][S_y]=true;
	while(!q.empty()){
		x=q.front();q.pop();
		y=q.front();q.pop();
		for(k=0;k<4;k++){
			mx=x+dirx[k];
			my=y+diry[k];
			if(mx<W&&mx>=0&&my<H&&my>=0){ 
			if(input[mx][my]!='X'&&!visited[mx][my]){
				q.push(mx);
				q.push(my);
				d[mx][my]=d[x][y]+1;
				if(input[mx][my]==(char)now){S_x=mx;S_y=my;D[now-48]=d[mx][my];}
				visited[mx][my]=true;
			}}
		}
	}
	clean();
}
void clean(){
	int i,j;
	for(i=0;i<W;i++)
		for(j=0;j<H;j++){
			visited[i][j]=false;
			d[i][j]=0;}
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

#define mp make_pair
#define f first
#define s second

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> T;

const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int h,w;
string grid[1000];

int bfs(P S,P G){

  queue<T>que;
  que.push(T(0,S));

  while(!que.empty()){
    T now=que.front();
    if(now.s.f==G.f && now.s.s==G.s)return now.f;

    que.pop();
    for(int i=0;i<4;i++){
      if(0<=now.s.f+dx[i] && 0<=now.s.s+dy[i] &&
	 now.s.f+dx[i]<h && now.s.s+dy[i]<w &&
	 grid[now.s.f+dx[i]][now.s.s+dy[i]]!='X'){
	que.push(T(now.f+1,P(now.s.f+dx[i],now.s.s+dy[i])));
	grid[now.s.f][now.s.s]='X';
      }
    }
  }
}

int main(void){
  int n;
  string in[1000];
  P v[1001];

  cin >> h >> w >> n;

  for(int i=0;i<h;i++)cin >> in[i];

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(in[i][j]=='S')v[0]=mp(i,j);
      if(in[i][j]!='X'&&in[i][j]!='.')
	v[in[i][j]-'0']=mp(i,j);
    }
  }

  int ans=0;
  for(int i=0;i<n;i++){

    for(int j=0;j<h;j++)
      grid[j]=in[j];

    ans+=bfs(v[i],v[i+1]);
  }

  cout << ans << endl;

  return 0;
}

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

struct Node{
	int x,y;
};

const int max_n=1000+10;
int h,w,n,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;
Node sN;
char c[max_n][max_n];

void bfs(int m){
	if(m>n)return;
	queue<Node> q;
	memset(d,0,sizeof(d));
	q.push(sN);
	d[sN.x][sN.y]=1;
	while(!q.empty()){
		Node p=q.front();
		q.pop();
		
		if(c[p.x][p.y]=='0'+m){
		    ans+=d[p.x][p.y]-1;
		    sN.x=p.x;
		    sN.y=p.y;
		    return;
		}
		for(int i=0;i<4;i++){
			Node nN;
			nN.x=p.x+dx[i];
			nN.y=p.y+dy[i];
			if(nN.x>=0 && nN.x<h 
            && nN.y>=0 && nN.y<w 
		   	&& c[nN.x][nN.y]!='X' && !d[nN.x][nN.y]){
				q.push(nN);
				d[nN.x][nN.y]=d[p.x][p.y]+1;
			}
		}
	}
}

int main(){
    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<h;i++)
        scanf("%s",c[i]);
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            if(c[i][j]=='S'){
            	sN.x=i;
            	sN.y=j;
            	break;
            }
    for(int i=1;i<=n;i++)bfs(i);
    cout<<ans<<endl;
    return 0;
}