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 <queue>
#include <string.h>
using namespace std;

using PII = pair<int, int>;
const int MAXN = 1e3 + 50;
int H, W, N, res, cnt, cur;
char mat[MAXN][MAXN];
std::queue<PII> que;

int vis[MAXN][MAXN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(int& x, int& y){
    
    while (!que.empty()) que.pop(); // clear all
    memset(vis, 0, sizeof(vis));

    que.push({x, y});

    int lop, dep = 0;
    // cout << "Counter is: --> " << cnt << endl;
    while (!que.empty()){
        lop = que.size();
        // cout << "Depth: " << dep << endl;
        for (int i = 0; i < lop; ++ i){
            auto pf = que.front(); que.pop();
            int cx = pf.first, cy = pf.second;
            if (vis[cx][cy]) continue;
            vis[cx][cy] = 1;
            // cout << cx << " " << cy << endl;
            if (mat[cx][cy] - '0' >= 0 && mat[cx][cy] - '0' <= 9 && mat[cx][cy] - '0' <= cur){
                mat[cx][cy] = '.';
                ++ cnt, ++ cur; // find one, add one to cur
                res += dep;
                x = cx, y = cy;
                return;
            }

            for (int i = 0; i < 4; ++ i){
                int nx = cx + dx[i], ny = cy + dy[i];
                if (nx < 0 || nx >= H || ny < 0 || ny >= W || mat[nx][ny] == 'X') continue;
                que.push({nx, ny});
            }
        }
        ++ dep;
    }


}

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

    cur = 1;
    res = cnt = 0;
    int cx, cy;
    for (int i = 0; i < H; ++ i){
        for (int j = 0; j < W; ++ j){
            cin >> mat[i][j];
            if (mat[i][j] == 'S') cx = i, cy = j;
        }
    }

    while (cnt < N){
        bfs(cx, cy);
    }

    cout << res << endl;
    return 0;
}

C++: #include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#define MAXHW 1000 + 1

using namespace std;
typedef pair<int, int> P;

int n, m, H, W, N, d[MAXHW][MAXHW];
char fac[MAXHW][MAXHW];

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

int bfs(int a, int b, int s){
	memset(d, -1, sizeof(d));
	queue<P> q;
	d[a][b] = 0;
	q.push(P(a, b));
	
	while(!q.empty()){
		P p = q.front();
		q.pop();
		
		if(fac[p.first][p.second] == char(s + '0')){
			n = p.first, m = p.second;
			return d[p.first][p.second];
		}
		
		for(int i = 0; i < 4; i++){
			int h = p.first + dy[i];
			int k = p.second + dx[i];
			if(h >= 0 && h < H && k >= 0 && k < W && fac[h][k] != 'X' && d[h][k] == -1){
				d[h][k] = d[p.first][p.second] + 1;
				q.push(P(h, k));
			}
		}
	}
}

int main(){
	int sum = 0;
	scanf("%d %d %d", &H, &W, &N);
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cin >> fac[i][j];
			if(fac[i][j] == 'S')
				n = i, m = j;
		}
	}
	for(int i = 1; i <= N; i++)
		sum += bfs(n, m, i);
	
	cout << sum << endl;
	return 0;
}

C++: #include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-8
#define REP(i, m) for(long long i=0; i<m; ++i)
#define FOR(i, n, m) for(long long i=n; i<m; ++i)
#define ALL(v) v.begin(), v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

vector<vector<char> > m;
vector<vector<bool> > used;
int w,h;
void dfs(P p) {
	used[p.first][p.second]=true;
	int dh[]={1,0,-1,0};
	int dw[]={0,1,0,-1};
	REP(i,4) {
		P np=P(p.first+dh[i],p.second+dw[i]);
		if(np.first>=0&&np.first<h&&np.second>=0&&np.second<w&&m[np.first][np.second]=='.'&&!used[np.first][np.second]) dfs(np);
	}
}
int main() {
	ios::sync_with_stdio(false);
	int h,w,n;
	cin>>h>>w>>n;
	vector<string> m(h);
	REP(i,h) cin>>m[i];
	P sp=P(-1,-1);
	REP(i,h) REP(j,w) {
		if(m[i][j]=='S') {
			sp.first=i;
			sp.second=j;
		}
	}
	int tgt=1;
	ll res=0;
	while(tgt<=n) {
		int dh[]={1,0,-1,0};
		int dw[]={0,1,0,-1};
		vector<vector<int> > d(h,vector<int>(w,INF));
		queue<P> q;
		q.push(sp);
		d[sp.first][sp.second]=0;
		while(!q.empty()) {
			P p=q.front();
			q.pop();
			if(m[p.first][p.second]==(char)('0'+tgt)) {
				sp.first=p.first;
				sp.second=p.second;
				res+=d[p.first][p.second];
				break;
			}
			REP(i,4) {
				ll nh=p.first+dh[i];
				ll nw=p.second+dw[i];
				if(nh>=0&&nh<h&&nw>=0&&nw<w&&m[nh][nw]!='X'&&d[nh][nw]==INF) {
					d[nh][nw]=d[p.first][p.second]+1;
					q.push(P(nh,nw));
				}
			}
		}
		++tgt;
	}
	cout<<res<<endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
int dis[1015][1015];
char mp[1015][1015];
int n, m, k;
int di[] = {1, -1, 0, 0}, dj[] = {0, 0, 1, -1};

int bfs(int si, int sj, char t) {
    queue<PII> q;
    q.push({si, sj});
    memset(dis, 0xff, sizeof(dis));
    dis[si][sj] = 0;
    while(!q.empty()) {
        auto now = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int ni = di[i] + now.first;
            int nj = dj[i] + now.second;
            if(mp[ni][nj] == t) return dis[now.first][now.second] + 1;
            if(mp[ni][nj] != 'X' && dis[ni][nj] == -1) {
                q.push({ni, nj});
                dis[ni][nj] = dis[now.first][now.second] + 1;
            }
        }
    }
    assert(false);
}
void _find(int& f, int& s, char c) {
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(mp[i][j] == c) {
                f = i;
                s = j;
                return;
            }
        }
    }
    assert(false);
}
int main() {
    while(scanf("%d %d %d", &n, &m, &k) != EOF) {
        memset(mp, 'X', sizeof(mp));
        for(int i = 1; i <= n; ++i) {
            scanf("%s", mp[i] + 1);
        }
        int ans = 0, px, py;
        _find(px, py, 'S');
        for(int i = 1; i <= k; ++i) {
            ans += bfs(px, py, '0' + i);
            _find(px, py, '0' + i);
        }
        printf("%d\n", ans);
    }
    return 0;
}