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>

using namespace std;
typedef pair<int, int> P;
char maze[1005][1005];
int d[1005][1005];
int dirx[4] = {0, -1, 0, 1};
int diry[4] = {1, 0, -1, 0};
int h, w, n, hard; 
int si, sj;
const int INF = 1<<30;
int tot = 0; 

void BFS(int ai, int aj){
	queue<P> que;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			d[i][j] = INF;
		}
	}
	que.push(P(ai, aj));
	d[ai][aj] = 0;
	while(!que.empty()){
		P a = que.front();
		que.pop();
		int x = a.first, y = a.second;
		if(maze[x][y]-'0' == hard){
			tot += d[x][y];
			si = x; sj = y;
			break;
		}
		for(int i = 0; i < 4; i++){
			int dx = x+dirx[i], dy = y+diry[i];
			if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){
				d[dx][dy] = d[x][y]+1;
				que.push(P(dx, dy));
			}
		}
	}
}

int main(int argc, char const *argv[]){
	while(scanf("%d%d%d", &h, &w, &n) != EOF){
		getchar();
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				scanf("%c", &maze[i][j]);
				if(maze[i][j] == 'S'){
					si = i; sj = j;
				}
			}
			getchar();
		}
		tot = 0;
		hard = 1;
		for(int i = 0; i < n; i++){
			BFS(si, sj);
			hard++;
		}
		cout << tot << endl;
	}
	return 0;
}

C++: //
//  0558.cpp
//  
//
//  Created by Yoshida Satoshi on 2017/11/16.
//
//

#include <iostream>
#include <queue>
#include <utility>
#include <stdlib.h>

#define MAX 1000
#define INF 100000000
#define FOR(index,max) for(int index=0;index<max;index++)

using namespace std;

typedef pair<int, int> P;

int main(){
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    
    int nx,ny;
    
    queue<P> que;
    int H,W,N;
    int state[MAX][MAX];//0:????????°or????????? -1:????????¶???
    bool isVisited[MAX][MAX];
    int d[MAX][MAX];
    int ans=0;
    int sx[9];
    int sy[9];
    P p;
    char in;
    cin>>H>>W>>N;
    FOR(i,H){
        FOR(j,W){
            cin>>in;
            if(in=='S'){
                sx[0]=i;
                sy[0]=j;
                state[i][j]=0;
            }
            else if(in=='X') state[i][j]=-1;
            else if(in=='.') state[i][j]=0;
            else{
                state[i][j]=0;
                sx[in-'0']=i;
                sy[in-'0']=j;
                
            }
        }
    }
    
    FOR(k,N){
        FOR(i,H){
            FOR(j,W){
                isVisited[i][j]=false;
                d[i][j]=INF;
            }
        }
        que.push(P(sx[k],sy[k]));
        d[sx[k]][sy[k]]=0;
        while(que.size()){
            p=que.front();
            que.pop();
            
            if(p==P(sx[k+1],sy[k+1]))   break;
            
            FOR(l,4){
                nx=p.first+dx[l];
                ny=p.second+dy[l];
                
                if(!(nx<0||ny<0||nx>H-1||ny>W-1||state[nx][ny]==-1||d[nx][ny]==INF)){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }
            }
        }
        
        ans += d[sx[k+1]][sy[k+1]];
    }
    
    cout<<ans<<endl;
    
    return 0;
}

C++: #include<iostream>
#include<queue>
#include<stdlib.h>
#include<utility>
#include<memory>
#include<string>
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
const int INF=-1;
char plat[1005][1005];
int d[1005][1005];
typedef pair<int,int> p;
int H,W,N;
queue<p> cheese;
int bfs(int& sx,int& sy,char energy)
{
    d[sx][sy]=0;
    cheese.push(p(sx,sy));
    while(cheese.size()){
        p test=cheese.front();
        cheese.pop();
        if(plat[test.first][test.second]==energy){
            sx=test.first;sy=test.second;
            return d[test.first][test.second];
        }
        for(int i=0;i<4;++i){
            int nx=test.first+dx[i];int ny=test.second+dy[i];
            if(nx>=0&&nx<W&&ny>=0&&ny<H&&plat[nx][ny]!='X'&&d[nx][ny]==INF){
                cheese.push(p(nx,ny));
                d[nx][ny]=d[test.first][test.second]+1;
            }
        }

    }
}

int main()
{

    cin>>W>>H>>N;
    int sx,sy;
    for(int i=0;i<W;++i){
        for(int j=0;j<H;++j){
            char u;
            cin>>u;
            if(u=='S'){
                sx=i;sy=j;
            }
            plat[i][j]=u;
        }
    }
    char e='1';
    int ans=0;
    while(N--){
        memset(d,-1,sizeof(d));
        ans+=bfs(sx,sy,e++);
        while(cheese.size())cheese.pop();

    }
    cout<<ans<<endl;

}

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

typedef pair<int, int> Point;
int h, w, n;
string grid[1001];

int bfs(int sx, int sy, int gx, int gy){
    bool visited[1001][1001] = {false};
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    visited[sy][sx] = true;

    queue<pair<Point, int> > que;
    pair<Point, int> state;
    que.push(make_pair(Point(sx, sy), 0));
    while (1){
        state = que.front();
        que.pop();

        if (state.first.first == gx && state.first.second == gy){
            return state.second;
        }

        for (int i = 0; i < 4; i++){
            int nx = state.first.first + dx[i];
            int ny = state.first.second + dy[i];
            if (0 <= nx && nx < w && 0 <= ny && ny < h 
                && grid[ny][nx] != 'X' && visited[ny][nx] == false){
                visited[ny][nx] = true;
                que.push(make_pair(Point(nx, ny), state.second + 1));
            }
        }
    }
}

int main(int argc, char const *argv[]){
    int sx, sy, gx, gy;
    int ans = 0;
    cin>>h>>w>>n;
    for (int i = 0; i < h; i++){
        cin>>grid[i];
    }

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (grid[i][j] == 'S'){
                sx = j; sy = i;
            }
            if (grid[i][j] == '1'){
                gx = j; gy = i;
            }
        }
    }

    for (int size = 2; size-1 <= n; size++){
        ans += bfs(sx, sy, gx, gy);

        sx = gx; sy = gy;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                if (grid[i][j] - '0' == size){
                    gx = j; gy = i;
                }
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}