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 <iostream>
using namespace std;

struct State{
	int x, y, cnt;
};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	int w, h, n;
	string m[1001];
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> m[y];
	}
	
	struct State cheese[11];
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			char c = m[y][x];
			if( c == 'S' ){
				cheese[0].x = x;
				cheese[0].y = y;
				cheese[0].cnt = 0;
			}
			if( c >= '1' && c <= '9' ){
				cheese[ c - '0' ].x = x;
				cheese[ c - '0' ].y = y;
				cheese[ c - '0' ].cnt = 0;
			}
		}
	}
	int ans = 0;
	for(int i=1 ; i <= n ; i++ ){
		struct State sp = cheese[i-1];
		struct State gp = cheese[i];
		queue<struct State> q;
		q.push( sp );
		while( !q.empty() ){
			struct State p = q.front();
			q.pop();
			if( p.x == gp.x && p.y == gp.y ){
				ans += p.cnt;
				break;
			}
			
			for(int i=0 ; i < 4 ; i++ ){
				int mx = p.x + dx[i];
				int my = p.y + dy[i];
				if( mx < 0 || my < 0 || mx >= w || my >> h ) continue;
				if( m[my][mx] != 'X' ){
					struct State next;
					next.x = mx;
					next.y = my;
					next.cnt = p.cnt + 1;
					q.push( next );
				}
			}
		}
	}
	cout << ans << endl;
}

C++: // 2014/07/07 Tazoe

#include <iostream>
#include <queue>
using namespace std;

const int INF = 100000000;

struct Point{
	int x;
	int y;
};

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

	char M[1002][1002];
	for(int y=0; y<H+2; y++){
		for(int x=0; x<W+2; x++){
			M[y][x] = 'X';
		}
	}

	struct Point P[10];

	for(int y=1; y<=H; y++){
		for(int x=1; x<=W; x++){
			cin >> M[y][x];

			if(M[y][x]=='S'){
				P[0].x = x;
				P[0].y = y;
			}
			else if('0'<=M[y][x] && M[y][x]<='9'){
				P[M[y][x]-'0'].x = x;
				P[M[y][x]-'0'].y = y;
			}
		}
	}

	int sum = 0;

	for(int i=0; i<N; i++){
		int d[1002][1002];
		for(int y=1; y<=H; y++){
			for(int x=1; x<=W; x++){
				d[y][x] = INF;
			}
		}

		// BFS

		queue<struct Point> que;

		struct Point p;
		p.x = P[i].x;
		p.y = P[i].y;
		que.push(p);
		d[p.y][p.x] = 0;

		while(!que.empty()){
			p = que.front();
			que.pop();

			if(p.x==P[i+1].x && p.y==P[i+1].y){
				sum += d[p.y][p.x];
				break;
			}

			if(M[p.y][p.x+1]!='X' && d[p.y][p.x+1]==INF){	// 東
				struct Point q;
				q.x = p.x+1;
				q.y = p.y;
				que.push(q);
				d[q.y][q.x] = d[p.y][p.x]+1;
			}
			if(M[p.y][p.x-1]!='X' && d[p.y][p.x-1]==INF){	// 西
				struct Point q;
				q.x = p.x-1;
				q.y = p.y;
				que.push(q);
				d[q.y][q.x] = d[p.y][p.x]+1;
			}
			if(M[p.y+1][p.x]!='X' && d[p.y+1][p.x]==INF){	// 南
				struct Point q;
				q.x = p.x;
				q.y = p.y+1;
				que.push(q);
				d[q.y][q.x] = d[p.y][p.x]+1;
			}
			if(M[p.y-1][p.x]!='X' && d[p.y-1][p.x]==INF){	// 北
				struct Point q;
				q.x = p.x;
				q.y = p.y-1;
				que.push(q);
				d[q.y][q.x] = d[p.y][p.x]+1;
			}
		}
	}

	cout << sum << endl;

	return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1100;
int h,w,n,dis[maxn][maxn],sx,sy,ans=0;
char maze[maxn][maxn];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int>P;
int bfs(int x,int y,int c){
	char order=c+'0';
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)dis[i][j]=maxn;
	queue<P>que;
	que.push(P(x,y));
	dis[x][y]=0;
	while(que.size()){
		P point=que.front();que.pop();
		if(maze[point.first][point.second]==order){
			sx=point.first,sy=point.second;
			return dis[point.first][point.second];
			break;
		}
		for(int i=0;i<4;i++){
			int nx=point.first+dx[i],ny=point.second+dy[i];
			if(1<=nx&&nx<=h&&1<=ny&&ny<=w&&maze[nx][ny]!='X'&&dis[nx][ny]==maxn){
				que.push(P(nx,ny));
				dis[nx][ny]=dis[point.first][point.second]+1;
			}
		}
	}
}
int main()
{
	//freopen("read.txt", "r", stdin);
	cin>>h>>w>>n;
	getchar();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>maze[i][j];
			if(maze[i][j]=='S'){
				sx=i;sy=j;
			}
		}
		getchar();
	}
	for(int k=1;k<=n;k++){
		ans+=bfs(sx,sy,k);
	}
	cout<<ans<<endl;
	//fclose(stdin);
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
struct p{
public:
    int y,x;
};
void clear( queue<p> &q )
{
   queue<p> empty;
   swap( q, empty );
}

int main(void){
    int h,w,n,i,j,ans=0;
    cin>>h>>w>>n;
    char c;
    vector<vector<char>> field(h,vector<char>(w));
    vector<vector<int>> mem(h,vector<int>(w, 0));
    queue<p> q;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            cin>>c;
            field[i][j]=c;
            if(c=='S'){
                q.push((p){i,j});
            }
        }
    }
    for(i='1';i<n+'1';i++){
        p po;
        while(!q.empty()){
            po=q.front();q.pop();
            if(field[po.y][po.x]==i) break;
            if(po.y+1<h && field[po.y+1][po.x]!='X' && mem[po.y+1][po.x]==0){
                mem[po.y+1][po.x]=mem[po.y][po.x]+1;
                q.push((p){po.y+1,po.x+0});
            }
            if(po.x+1<w && field[po.y][po.x+1]!='X' && mem[po.y][po.x+1]==0){
                mem[po.y][po.x+1]=mem[po.y][po.x]+1;
                q.push((p){po.y+0,po.x+1});
            }
            if(po.y-1>=0 && field[po.y-1][po.x]!='X' && mem[po.y-1][po.x]==0){
                mem[po.y-1][po.x]=mem[po.y][po.x]+1;
                q.push((p){po.y-1,po.x});
            }
            if(po.x-1>=0 && field[po.y][po.x-1]!='X' && mem[po.y][po.x-1]==0){
                mem[po.y][po.x-1]=mem[po.y][po.x]+1;
                q.push((p){po.y,po.x-1});
            }
        }
        ans+=mem[po.y][po.x];
        clear(q);
        q.push((p){po.y,po.x});
        mem=vector<vector<int>>(h,vector<int>(w, 0));
    }
    cout<<ans<<endl;
}