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 <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define INF 0x7f7f7f7f
#define PI acos(-1.0)

#define L(x)    (x) << 1
#define R(x)    (x) << 1 | 1
#define lowbit(x)   (x)&(-x)
#define Mid(l, r)   (l + r) >> 1
#define Min(x, y)   (x) < (y) ? (x) : (y)
#define Max(x, y)   (x) < (y) ? (y) : (x)
#define iabs(x)     (x) < 0 ? -(x) : (x)
#define CLR(arr, val)    memset(arr, val, sizeof(arr))

using namespace std;

char map[1024][1024];
bool vis[1024][1024];
int cur, h, w;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

struct node {
	int x, y, step;
} sta;

bool check(int x, int y) {
	if (x >= 0 && x < h && y >= 0 && y < w && !vis[x][y] && map[x][y] != 'X')	return true;
	return false;
}



void bfs(node s) {
	memset(vis, 0, sizeof(vis));
	
	queue<node> que;
	que.push(s);
	node next;
	while (!que.empty()) {
		s = que.front(); que.pop();
		
		next.step = now.step + 1;
		for (int i = 0; i < 4; i++) {
			next.x = now.x + dir[i][0];
			next.y = now.y + dir[i][1];

			if (check(next.x, next.y)) {
				vis[s.x][s.y] = true;
				if (map[next.x][next.y] == cur + '0') {
					sta = next;
					return ;
				}
				que.push(next);
			}
		}
	}
}

int main() {
	int n;
	while (cin >> h >> w >> n) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				if (map[i][j] == 'S')	sta.x = i, sta.y = j, map[i][j] = '.';
			}
		}
		sta.step = 0;
		for (cur = 1; cur <= n; cur++) {
			bfs(sta);
		}
		cout << sta.step << 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];
	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;
		int cou=0;
		XX[ys[x]][xs[x]]=cou;
		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;
					vec2.push_back(make_pair(vec1[i].first+dy[j],vec1[i].second+dx[j]));
				}
			}
			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;
}

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

#define p(x) cout << "(" << x.first << "," << x.second << ")" << endl;

using namespace std;
const int MAX_H = 1005;
const int MAX_W = 1005;

char D[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];

int H, W, N;

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

typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef vector<PII> VII;

int bfs(PII from, PII to) {
  queue<PIII> que;
  memset(visited, false, sizeof(visited[0][0]) * MAX_H * MAX_W);

  que.push(make_pair(from, 0));
  while (!que.empty()) {
    PIII p = que.front(); que.pop();
    int d = p.second;
    if (p.first == to) {
      return d;
    }
    for (int k = 0; k < 4; k++) {
      int i2 = p.first.first + dx[k];
      int j2 = p.first.second + dy[k];
      if (0 <= i2 && i2 < H && 0 <= j2 && j2 < W && D[i2][j2] != 'X' && !visited[i2][j2]) {
        visited[i2][j2] = true;
        que.push(make_pair(make_pair(i2, j2), d+1));
      }
    }
  }
  return -1;
}

int main() {
  cin >> H >> W >> N;

  VII pos(N+1);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      char c;
      cin >> c;
      D[i][j] = c;
      if (c == 'S') {
        pos[0] = make_pair(i, j);
      } else if (c > '0') {
        pos[c - '0'] = make_pair(i, j);
      }
    }
  }

  int res = 0;
  for (int i = 0; i < N; i++) {
    res += bfs(pos[i], pos[i+1]);
  }
  cout << res << endl;

  return 0;
}

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

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

struct Info {
    int r;
    int c;
    int cost;
    Info(int r, int c, int cost) : r(r), c(c), cost(cost){}
};

int bfs(vector<string> map, pair<int, int> start, char target) {
    int res = 0;
    queue<Info> que;
    que.push(Info(start.first, start.second, 0));
    while (!que.empty()) {
        Info info = que.front(); que.pop();
        if (map[info.r][info.c] == target) {
            res = info.cost;
            break;
        }
        map[info.r][info.c] = 'o';
        for (int i = 0; i < 4; i++) {
            int nr = info.r + dr[i];
            int nc = info.c + dc[i];
            if (nr >= 0 && nr < map.size() && nc >= 0 && nc < map[nr].size()
                    && map[nr][nc] != 'X' && map[nr][nc] != 'o') {
                Info nextInfo = Info(nr, nc, info.cost + 1);
                que.push(nextInfo);
            }
        }
    }

    return res;
}

int getCost(vector<string>& map, int next, int N) {
    char from = 'S';
    if (next > 1) from = char(next - 1 + '0');
    char to = char(next + '0');
    pair<int, int> start;
    for (int i = 0; i < map.size(); i++) {
        for(int j = 0; j < map[i].size(); j++) {
            if (map[i][j] == from) {
                start = pair<int, int>(i, j);
                int c = bfs(map, start, to);

                return c;
            }
        }
    }
    return 0;
}

int solve(vector<string>& map, int N) {
    int cost = 0;
    for (int k = 1; k <= N; k++) {
        cost += getCost(map, k, N);
    }
    return cost;
}

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    vector<string> map;
    for (int i = 0; i < H; i++) {
        string s; cin >> s;
        map.push_back(s);
    }
    int answer = solve(map, N);
    cout << answer << endl;
}