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>

#define INF 1e9
#define MAX_H 1000
#define MAX_W 1000

using namespace std;

struct Cood {int x, y; };

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

char field[MAX_H][MAX_W + 1];
int d[MAX_H][MAX_W + 1];
queue<Cood> q;
int h, w, n;
int total_time = 0;

void init_bfs() {
    queue<Cood> new_q;
    swap(q, new_q);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            d[i][j] = INF;
        }
    }
}
/* current position (y, x) with current power 'current' & last cheeese target is 'last' */
int bfs(int sy, int sx, int target, int last) {
    init_bfs();
    int next_y, next_x;
    q.push(Cood{sx, sy});
    d[sy][sx] = 0;

    while (q.size()) {
        Cood current = q.front(); q.pop();
        if (field[current.y][current.x] == '0' + target) {
            total_time += d[current.y][current.x];
            if (target == last) {
                return total_time;
            } else {
                return bfs(current.y, current.x, target + 1, last);
            }
        }

        for (int i = 0; i < 4; ++i) {
            next_y = current.y + dy[i];
            next_x = current.x + dx[i];
            if (0 <= next_y && next_y < h && 0 <= next_x && next_x < w
                && field[next_y][next_x] != 'X' && d[next_y][next_x] == INF) {
                q.push(Cood{next_x, next_y});
                d[next_y][next_x] = d[current.y][current.x] + 1;
            }
        }
    }
}

int main() {
    //freopen("0558_1.in", "r", stdin);
    cin >> h >> w >> n;
    int sx, sy;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> field[i][j];
            if (field[i][j] == 'S') {
                sy = i, sx = j;
            }
        }
    }
    total_time = 0; // init
    cout << bfs(sy, sx, 1, n) << endl;
    return 0;
}

C++: #include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_HW = 1000;
int n, h, w, rat, s[2], g[2], flag[MAX_HW+1][MAX_HW+1][2];
int town[MAX_HW+1][MAX_HW+1];
char town2[MAX_HW+1][MAX_HW+1];
queue <P> que;
P p;
void bfs(int sy, int sx){
	que.push(P(sy, sx));
	flag[sy][sx][0]=rat;
	while (que.size()){
	RE:
		p = que.front();
		que.pop();
		for (int i = -1; i <= 1; i++){
			for (int j = -1; j <= 1; j++){
				if (i == 0 || j == 0){
					if (town2[p.first + i][p.second + j] != 'X'&&flag[p.first + i][p.second + j][0] != rat&&p.first + i < h&&p.first + i >= 0 && p.second + j < w&&p.second + j >= 0) {
							flag[p.first+i][p.second+j][0] = rat;
							flag[p.first + i][p.second + j][1] = flag[p.first][p.second][1] + 1;
							if (town[p.first + i][p.second + j] == rat){
							if (rat == n) return;
							rat++;
							flag[p.first+i][p.second+j][0] = rat;
							while (que.size()){
								que.pop();
							}
							que.push(P(p.first + i, p.second + j));
							goto RE;
						}
						else{
						que.push(P(p.first + i, p.second + j));
						}
					}
				}
			}
		}
	}
}
int main(){
	cin >> h >> w >> n;
	rat = 1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cin >> town2[i][j];
			town[i][j] = town2[i][j] - 48;
			if (town2[i][j] == 'S'){
				s[0] = i;
				s[1] = j;
			}
			if (town[i][j] == n){
				g[0] = i;
				g[1] = j;
			}
		}
	}
	bfs(s[0], s[1]);
	cout << flag[g[0]][g[1]][1] << endl;
	return 0;
}

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

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF (1 << 30)
#define mp make_pair

using namespace std;

typedef pair<int, int> P;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int h, w, n;
int ans = 0;
int sx, sy, gx, gy;
char field[1010][1010];
int went[1010][1010];

/*struct state{
	int x;
	int y;
	int count;
};*/

int bfs(P start, int tmp) {
	rep(i, h) {
		rep(j, w) {
			went[i][j] = INF;
			if(field[i][j] == tmp + '0') {
				gy = i;
				gx = j;
			}
		}
	}
	went[start.first][start.second] = 0;

	queue<P> q;
	q.push(start);

	while(!q.empty()) {
		P p = q.front();
		q.pop();
		//cout << p.first << " " << p.second.first << " " << p.second.second << endl;
		if(p.first == gy && p.second == gx) return went[p.first][p.second];
		rep(i, 4) {
			int nx = p.second + dx[i];
			int ny = p.first + dy[i];
			if(nx >= 0 && ny >= 0 && nx < w && ny < h && went[ny][nx] == INF && field[ny][nx] != 'X') {
				q.push(P(ny, nx));
				went[ny][nx] = went[p.first][p.second] + 1;
			}
		}
	}
}

int main() {
	cin >> h >> w >> n;
	rep(i, h) rep(j, w) {
		cin >> field[i][j];
		if(field[i][j] == 'S') sx = j, sy = i;
	}
	/*rep(i, h) {
		rep(j, w) cout << field[i][j];
		cout << endl;
	}*/
	for(int i = 1; i <= n; ++i) {
		ans += bfs(P(sy, sx), i);
	}
	cout << ans << endl;
	return 0;
}

C++: #include <iostream>
#include<queue>
using namespace std;
using namespace std;
int total=0;
char ch[1000][1000];
int d[1000][1000];
const int INF=100000000;
int sum=0;
int sx,sy,ex,ey,n,h,w;
int bfs();
int main()
{
    cin>>h>>w>>n;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        cin>>ch[i][j];
        for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
       if(ch[i][j]=='S')
       {
       sx=i;
       sy=j;
       }
       char k='1';
    for(int c=0;c<n;c++)
      for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            if(ch[i][j]==k)
            {
                k++;
                ex=i;
                ey=j;
                sum=sum+bfs();
                sx=ex;
                sy=ey;
            }


    cout<<sum<<endl;
    return 0;
}
int bfs()
{
    typedef pair<int,int> p;
    queue<p> que;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        d[i][j]=INF;
        int nx,ny, x[4]={-1,0,1,0},y[4]={0,1,0,-1},sum=0;
       que.push(p(sx,sy));
       d[sx][sy]=0;
       while(que.size())
       {
           p q=que.front();
           que.pop();
           if(q.first==ex&&q.second==ey)
                break;
           for(int i=0;i<4;i++)
           {
               nx=q.first+x[i];
               ny=q.second+y[i];
           if(nx>=0&&nx<h&&ny>=0&&ny<w&&ch[nx][ny]!='X'&&d[nx][ny]==INF)
           {
              d[nx][ny]=d[q.first][q.second]+1;
               que.push(p(nx,ny));
           }
           }

       }
       return d[ex][ey];
}