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<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int DIRECTSIZE = 4;
struct _direct {
    int drow;
    int dcol;
} direct[DIRECTSIZE] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int N = 1000;
const int N2 = 10;
char grid[N][N], visited[N][N];
int h, w, n;
struct _factory {
    int row;
	int col;
} factory[N2];

struct _node {
    int row;
	int col;
	int level;
};

int bfs(int n, char goal) {
    memset(visited, 0, sizeof(visited));
    _node start={factory[n-1].row, factory[n-1].col, 0}, temp;
    visited[start.row][start.col] = 1;
    queue<_node> q;
    q.push(start);
    while(!q.empty()) {
        _node front = q.front();
        q.pop();
        for(int i=0; i<DIRECTSIZE; i++) {
            int nextrow = front.row + direct[i].drow;
            int nextcol = front.col + direct[i].dcol;
            if( 0 <= nextrow && nextrow < h && 0 <= nextcol && nextcol < w) {
                if(grid[nextrow][nextcol] == goal) {
                    return front.level + 1;
                }
				else if(visited[nextrow][nextcol] == 0 && grid[nextrow][nextcol] != 'X') {
                    visited[nextrow][nextcol] = 1;
                    temp.row = nextrow;
                    temp.col = nextcol;
                    temp.level = front.level + 1;
                    q.push(temp);
                }
            }
        }
    }
    return 0;
}

int main() {
    while (~scanf("%d %d %d", &h, &w, &n)){
        for(int i = 0; i < h; i++) {
			scanf("%s", grid[i]);
            for(int j = 0; j < w; j++) {
                if(grid[i][j] == 'S') {
                    factory[0].row = i;
                    factory[0].col = j;
				}
				else if(isdigit(grid[i][j])) {
                    factory[grid[i][j] - '0'].row = i;
                    factory[grid[i][j] - '0'].col = j;
                }
            }
		}
        int minstep = 0;
        char goal = '1';
        for(int i=1; i<=n; i++) {
            minstep += bfs(i, goal);
            goal++;
        }
        printf("%d\n", minstep);
    }
    return 0;
}

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

using namespace std;

const double inf = (int)1e8;

int main(){
    int h, w, n;
    cin >> h >> w >> n;

    vector<string> field(h);
    int d[h][w];
    int mx, my;
    for(int i=0; i< h; i++){
        cin >> field[i];
        for(int j=0; j < field[i].size(); j++) if(field[i][j] == 'S'){mx = i; my = j; field[i][j] = '.';}
    }
    int count = 0;
    for(int i = 1; i <= n; i++){
        for(int i=0; i< h; i++)for(int j=0; j < w; j++) d[i][j] = inf;
        queue<pair<int, int>> q;
        q.push(make_pair(mx, my));
        d[mx][my] = 0;
        while(q.size()){
            pair<int, int> p = q.front(); q.pop();
            if(field[p.first].substr(p.second, 1) == to_string(i)){count += d[p.first][p.second]; mx = p.first; my = p.second; break;}
            int dx[4] = {1, 0, -1, 0};
            int dy[4] = {0, 1, 0, -1};
            for(int j=0; j < 4; j++){
                int nx = p.first+dx[j], ny = p.second+dy[j];
                if(0 <= nx && nx < h && 0 <= ny && ny < w && field[nx][ny] != 'X' && d[nx][ny] == inf){
                    q.push(make_pair(nx, ny));
                    d[nx][ny] = d[p.first][p.second] + 1;
                }
            }
        }
    }
    cout << count << endl;
}

C++: #include<iostream>
#include<deque>
#define pb push_back
#define pf push_front
using namespace std ;

char map[1001][1001] = {} ;
char num[] = { '0','1','2','3','4','5','6','7','8','9' } ;
int num_map[1001][1001] = {} ;
int dx[] = { -1,0,1,0 } ;
int dy[] = { 0,-1,0,1 } ;
deque<int> qx ;
deque<int> qy ;
deque<int> qc ;

int main(){
	
	int h , w , n ;
	int nx , ny , nc ;
	int ans = 0 ;
	
	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' ){
				qy.pb(i) ;
				qx.pb(j) ;
			}
		}
	}
	
	for( int i=1 ; i<=n ; i++ ){
		num_map[qy.front()][qx.front()] = i ;
		qc.pb(0) ;
		while(1){
			nx = qx.front() ;
			ny = qy.front() ;
			nc = qc.front() ;
			
			if( map[ny][nx] == num[i] ) break ;
			for( int j=0 ; j<4 ; j++ ){
				if( 0 <= ny+dy[j] && ny+dy[j] < h &&
					0 <= nx+dx[j] && nx+dx[j] < w &&
					num_map[ny+dy[j]][nx+dx[j]] < i &&
					map[ny+dy[j]][nx+dx[j]] != 'X' ){
						num_map[ny+dy[j]][nx+dx[j]] = i ;
						qy.pb( ny+dy[j] ) ;
						qx.pb( nx+dx[j] ) ;
						qc.pb( nc+1 ) ;
				}
			}
			qx.pop_front() ;
			qy.pop_front() ;
			qc.pop_front() ;
		}
		qy.clear() ;
		qx.clear() ;
		qc.clear() ;
		qy.pb(ny) ;
		qx.pb(nx) ;
		ans += nc ;
	}
	
	cout << ans << endl ;
	
return 0;
}

C++: #include<iostream>
#include<queue>
#define x first
#define y second
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int h,w,k;
pair<int,int> p[10];
bool t[1010][1010],vis[1010][1010];
queue<pair<int,pair<int,int> > >Q;
int main(){
	cin>>h>>w>>k;
	rep(i,0,h)rep(j,0,w){
		t[i][j]=true;
		char z;cin>>z;
		if(z=='X')t[i][j]=0;
		if(z=='S')p[0]=make_pair(i,j);
		if(z>'0'&&z<='9')p[z-'0']=make_pair(i,j);
	}
	int a=0;
	rep(r,0,k){
		while(!Q.empty())Q.pop();
		Q.push(make_pair(0,p[r]));
		rep(i,0,h)rep(j,0,w)vis[i][j]=0;
		while(1){
			int L=Q.front().x,Y=Q.front().y.x,X=Q.front().y.y;
			if(Y==p[r+1].x&&X==p[r+1].y){
				a+=L;
				break;
			}
			vis[Y][X]=1;
			int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
			rep(i,0,4){
				int f=Y+dy[i],g=X+dx[i];
				if(f>=0&&f<h&&g>=0&&g<w){
					if(t[f][g]==1&&vis[f][g]==0){
						Q.push(make_pair(L+1,make_pair(f,g)));
					}
				}
			}
			Q.pop();
		}
	}
	cout<<a<<endl;
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#define INF 1000000000
using namespace std;
typedef pair<int,int> P;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int h,w,n;
vector<string> s;
bool inf(int y,int x){return(y>=0&&y<h&&x>=0&&x<w)?1:0;}
int bfs(P sp,P sg){
	int ret=0;
	queue<P> que;
	que.push(sp);
	vector<vector<int> > d(h,vector<int>(w,INF));
	d[sp.first][sp.second]=0;
	while(!que.empty()){
		P t=que.front();
		que.pop();
		int y=t.first,x=t.second;
		if(t==sg){
			return d[sg.first][sg.second];
		}
		for(int i=0;i<4;i++){
			int ny=dy[i]+y,nx=dx[i]+x;
			if(inf(ny,nx)&&d[ny][nx]>d[y][x]+1&&s[ny][nx]!='X'){
				que.push(P(ny,nx));
				d[ny][nx]=d[y][x]+1;
			}
		}
	}
	return -1;
}
int main(){
	while(cin>>h>>w>>n,h||w||n){
		s=vector<string>(h);
		vector<P> pm(n+1);
		for(int i=0;i<h;i++){
			cin>>s[i];
			for(int j=0;j<w;j++){
				if(s[i][j]=='S'){
					pm[0]=P(i,j);
				}else if(isdigit(s[i][j])){
					pm[s[i][j]-'0']=P(i,j);
				}
			}
		}
		int ans=0;
		for(int i=0;i<n;i++){
			ans+=bfs(pm[i],pm[i+1]);
		}
		cout<<ans<<endl;
	}
	return 0;
}