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

struct OZAWA
{
	int x;
	int y;
	int c;
};
int Flag[1001][1001];
char MAP[1001][1001];
int main(void)
{
	int H,W,N,Nc=0,X[10],Y[10];
	OZAWA ba,v;
	queue<OZAWA> Q;
	int mv[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
	char Cheese[10] ={'1','2','3','4','5','6','7','8','9'};
	memset(MAP,'X',sizeof(MAP));
	memset(Flag,0,sizeof(Flag));
	scanf("%d %d %d",&H,&W,&N);
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			//printf("%d %d ",i,j);
			cin >> MAP[i][j];
			//printf("Q");
			if(MAP[i][j] == 'S'){
				ba.x = j;
				ba.y = i;
				ba.c = 0;
				Flag[i][j] = 1;
				Q.push(ba);
				//printf("Sin\n");
			}
			for(int ii=0;ii<9;ii++){
				if(MAP[i][j] == Cheese[ii]){

					X[ii] = j;
					Y[ii] = i;
					//printf("\n@@@\n");
				}
			}
		}
	}
	//printf("S %d %d\n",ba.x,ba.y);
	for(int ii=0;ii<2;ii++)
		//printf("%d %d\n",X[ii],Y[ii]);
	while(!Q.empty()){
		//printf("QA\n");
		ba = Q.front();
		Q.pop();
		if(ba.x==X[Nc] && ba.y==Y[Nc]){
			Nc++;
			memset(Flag,0,sizeof(Flag));
			while(!Q.empty()){
				Q.pop();
			}
			Q.push(ba);
		}
		if(Nc == N) break;
		for(int i=0;i<4;i++){
			if(MAP[ba.y+mv[i][1]][ba.x+mv[i][0]]!='X' && Flag[ba.y+mv[i][1]][ba.x+mv[i][0]]==0){
				v.x=ba.x+mv[i][0];
				v.y=ba.y+mv[i][1];
				v.c=ba.c+1;
				Q.push(v);
				Flag[v.y][v.x] = 1;
				//printf("%d %d\n",v.x,v.y);
			}
		}
	}
	cout <<ba.c<<endl;
	return 0;
}

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

#define INF 1000000

using namespace std;

int H, W, N, sy, sx, k[1001][1001];
char c[1001][1001];
queue<pair<int, int>> q;

void reset(int y, int x){
    int i, j;

    while(!q.empty())q.pop();

    for(i = 0; i < 1001; i++){
        for(j = 0; j < 1001; j++){
            if(i != y || j != x){
                k[i][j] = INF;
            }
        }
    }

    q.push(make_pair(y, x));
}

int solve(int n){
    int y, x;

    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();
        if(c[y][x] == n + '0'){
            break;
        }
        if(x > 0 && c[y][x - 1] != 'X' && k[y][x - 1] == INF){
            q.push(make_pair(y, x - 1));
            k[y][x - 1] = k[y][x] + 1;
        }
        if(x < W - 1 && c[y][x + 1] != 'X' && k[y][x + 1] == INF){
            q.push(make_pair(y, x + 1));
            k[y][x + 1] = k[y][x] + 1;
        }
        if(y > 0 && c[y - 1][x] != 'X' && k[y - 1][x] == INF){
            q.push(make_pair(y - 1, x));
            k[y - 1][x] = k[y][x] + 1;
        }
        if(y < H - 1 && c[y + 1][x] != 'X' && k[y + 1][x] == INF){
            q.push(make_pair(y + 1, x));
            k[y + 1][x] = k[y][x] + 1;
        }
    }
    sy = y;
    sx = x;

    return y * W + x;
}

int main()
{
    int i, j, z;

    cin >> H >> W >> N;
    for(i = 0; i < H; i++){
        for(j = 0; j < W; j++){
            cin >> c[i][j];
            if(c[i][j] == 'S'){
                sy = i;
                sx = j;
            }
        }
    }
    k[sy][sx] = 0;

    for(i = 1; i <= N; i++){
        reset(sy, sx);
        z = solve(i);
    }

    cout << k[z / W][z % W] << endl;
}

C++: #include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

typedef std::pair<int, int> T;

const int vecx[4] = { 1,0,-1,0 };
const int vecy[4] = { 0,-1,0,1 };
int h, w, n;
T goal[10];
char filed[1000][1000];
int si, sj;
int ans;
int dis[1000][1000];

void bfs(T _goal, T _start) {
	std::queue<T> q;
	q.push(_start);
	while (q.size()) {
		T tmp = q.front();
		q.pop();
		if (tmp == _goal) {
			ans += dis[_goal.first][_goal.second];
			break;
		}
		int x = tmp.first;
		int y = tmp.second;
		for (int i = 0; i < 4; i++) {
			if (x + vecx[i] < 0 || x + vecx[i] >= h || y + vecy[i] < 0 || y + vecy[i] >= w)continue;
			if (filed[x + vecx[i]][y + vecy[i]] != 'X') {
				dis[x + vecx[i]][y + vecy[i]] = dis[x][y] + 1;
				q.push(std::make_pair(x + vecx[i], y + vecy[i]));
			}
		}
	}
}

int main() {
	std::cin >> h >> w >> n;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			std::cin >> filed[i][j];
			if (filed[i][j] == 'S') {
				goal[0].first = i;
				goal[0].second = j;
			}
			if (filed[i][j] > '0' && filed[i][j] <= '9') {
				goal[filed[i][j] - '0'].first = i;
				goal[filed[i][j] - '0'].second = j;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		bfs(goal[i + 1], goal[i]);
		for (int j = 0; j < h; j++)for (int k = 0; k < w; k++)dis[j][k] = 0;
	}
	std::cout << ans << std::endl;
	return 0;
}

C++: #include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAX 1001
const char INF = '#';
const int MM = 10000000;
typedef pair<int,int> P;

int num,d[MAX][MAX],n,m;
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
char field[MAX+1][MAX+1];

int bfs(int sy,int sx,int gy,int gx){
    queue<P> que;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
            d[i][j] = MM;
    
    que.push(P(sy,sx));
    d[sy][sx] = 0;
    
    while(que.size()){
        P p = que.front(); que.pop();
        if(p.first == gy && p.second == gx) break;
        
        for(int i = 0 ; i < 4 ; i++){
            int nx = p.first+dx[i];
            int ny = p.second+dy[i];
            
            if(0 <= nx && nx < n && 0 <= ny && ny < m && field[nx][ny] != 'X'
               &&d[nx][ny] == MM){
                que.push(P(nx,ny));
                d[nx][ny] = d[p.first][p.second]+1;
            }
        }
    }
    
    return d[gy][gx];
}

int main(){
    fill(field[0],field[MAX],INF);

    cin >> n >> m >> num;
    vector<P> v(num+1);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> field[i][j];
            if(field[i][j]=='S'){
                v[0].first = i;
                v[0].second = j;
            }
            if('0' <= field[i][j] && field[i][j] <= '9'){
                v[field[i][j]-'0'].first = i;
                v[field[i][j]-'0'].second = j;
            }
        }
    }

    int ans = 0;
    for(int i = 1 ; i < num+1 ; i++){
        ans += bfs(v[i-1].first,v[i-1].second,v[i].first,v[i].second);
    }
    cout << ans << endl;

    return 0;
}