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>

bool syo[1000][1000];
bool sude[1000][1000];
int zi[1000][1000];
int kox[1000000];
int koy[1000000];
int kon;
int koxs[1000000];
int koys[1000000];
int kons;
int cx[10];
int cy[10];
int sx,sy;

int main()
{
	int h,w,n;
	scanf("%d %d %d",&h,&w,&n);
	for(int i = 0; i < h; i++)
	{
		char ww[1111];
		scanf("%s",ww);
		for(int ii = 0; ii < w; ii++)
		{
			if('1' <= ww[ii] && ww[ii] <= '9')
			{
				int d = ww[ii] - '1';
				cy[d] = i;
				cx[d] = ii;
			}
			if(ww[ii] == 'S')
			{
				sy = i;
				sx = ii;
			}
			if(ww[ii] == 'X')
			{
				syo[i][ii] = true;
			}
			else
			{
				syo[i][ii] = false;
			}
		}
	}
	int time = 0;
	int nx = sx;
	int ny = sy;
	for(int k = 0; k < n; k++)
	{
		for(int i = 0; i < h; i++)
		{
			for(int ii = 0; ii < w; ii++)
			{
				zi[i][ii] = 1000000;
				sude[i][ii] = false;
			}
		}
		zi[ny][nx] = 0;
		kox[0] = nx;
		koy[0] = ny;
		kon = 1;
		while(1)
		{
			kons = 0;
			for(int i = 0; i < kon; i++)
			{
				if(syo[koy[i]][kox[i]] || sude[koy[i]][kox[i]])
				{
					continue;
				}
				sude[koy[i]][kox[i]] = true;
				if(kox[i] == cx[k] && koy[i] == cy[k])
				{
					goto aa;
				}
				if(kox[i] > 0)
				{
					if(zi[koy[i]][kox[i] - 1] > zi[koy[i]][kox[i]])
					{
						zi[koy[i]][kox[i] - 1] = zi[koy[i]][kox[i]] + 1;
						koxs[kons] = kox[i] - 1;
						koys[kons] = koy[i];
						kons++;
					}
				}
				if(kox[i] < w - 1)
				{
					if(zi[koy[i]][kox[i] + 1] > zi[koy[i]][kox[i]])
					{
						zi[koy[i]][kox[i] + 1] = zi[koy[i]][kox[i]] + 1;
						koxs[kons] = kox[i] + 1;
						koys[kons] = koy[i];
						kons++;
					}
				}
				if(koy[i] > 0)
				{
					if(zi[koy[i] - 1][kox[i]] > zi[koy[i]][kox[i]])
					{
						zi[koy[i] - 1][kox[i]] = zi[koy[i]][kox[i]] + 1;
						koxs[kons] = kox[i];
						koys[kons] = koy[i] - 1;
						kons++;
					}
				}
				if(koy[i] < h - 1)
				{
					if(zi[koy[i] + 1][kox[i]] > zi[koy[i]][kox[i]])
					{
						zi[koy[i] + 1][kox[i]] = zi[koy[i]][kox[i]] + 1;
						koxs[kons] = kox[i];
						koys[kons] = koy[i] + 1;
						kons++;
					}
				}
			}
			for(int i = 0; i < kons; i++)
			{
				kox[i] = koxs[i];
				koy[i] = koys[i];
			}
			kon = kons;
		}
aa:
		time += zi[cy[k]][cx[k]];
		nx = cx[k];
		ny = cy[k];
	}
	printf("%d\n",time);
	return 0;
}

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

using namespace std;

int W, H, N;

struct Vector2{
	int x;
	int y;
};

bool exist(int map[2000][2000], Vector2 p, int step){
	if(p.x < 0 || p.y < 0 || p.x >= W || p.y >= H){
		return false;
	}
	if(map[p.y][p.x] > step + 1){
		map[p.y][p.x] = step + 1;
		return true;
	}
	return false;
}

int map[2000][2000];

int main(){
	
	string map_[2000];
	
	cin >> H >> W >> N;
	
	for(int i = 0; i < H; i++){
		cin >> map_[i];
	}
	
	int ans = 0;
	
	Vector2 start, goal, punct, p, p1;
	
	punct.x = -1;
	punct.y = -1;
	
	queue<Vector2> que;
	
	for(int loop = 0; loop < N; loop++){
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				if(map_[i][j] == 'X'){
					map[i][j] = -1;
				}else if(map_[i][j] == '0' + loop || map_[i][j] == 'S'){
					start.x = j;
					start.y = i;
					map[i][j] = 0;
				}else if(map_[i][j] == '0' + loop + 1){
					goal.x = j;
					goal.y = i;
					map[i][j] = 1 << 30;
				}else{
					map[i][j] = 1 << 30;
				}
			}
		}
		que.push(start);
		que.push(punct);
		
		bool checker = false;
		
		for(int step = 0; step < 3000; step++){
			while(true){
				p = que.front();
				que.pop();
				if(p.x == punct.x && p.y == punct.y){
					que.push(punct);
					break;
				}else if(p.x == goal.x && p.y == goal.y){
					checker = true;
					break;
				}
				p1.x = p.x - 1;
				p1.y = p.y;
				if(exist(map, p1, step)){
					que.push(p1);
				}
				p1.x = p.x + 1;
				p1.y = p.y;
				if(exist(map, p1, step)){
					que.push(p1);
				}
				p1.x = p.x;
				p1.y = p.y - 1;
				if(exist(map, p1, step)){
					que.push(p1);
				}
				p1.x = p.x;
				p1.y = p.y + 1;
				if(exist(map, p1, step)){
					que.push(p1);
				}
			}
			if(checker){
				ans += step;
				break;
			}
		}
		
		while(!que.empty()){
			que.pop();
		}
		
	}
	
	printf("%d\n", ans);
	
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

typedef long long ll;

constexpr int INF = 1e8;
constexpr int MOD = 1e9+7;

string field[1000];
int dist[1000][1000];
int dxy[] = {0,1,0,-1};
int ex[9], ey[9];

int main(void) {
    int i, j, k, h, w, n;
    cin >> h >> w >> n;
    REP (i,h) cin >> field[i];
    queue<pair<int,int>> q;
    REP (i,h) REP (j,w) {
        dist[i][j] = INF;
        if (field[i][j] == 'S') {
            q.push(make_pair(i,j));
            dist[i][j] = 0;
        }
        else if ('1' <= field[i][j] && field[i][j] <= '9') {
            int x = field[i][j] - '1';
            ey[x] = i; ex[x] = j;
        }
    }
    int ans = 0;
    REP (k,n) {
        while (!q.empty()) {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            REP (i,4) {
                int ny = y + dxy[i];
                int nx = x + dxy[(i+1)%4];
                if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
                if (field[ny][nx] != 'X' && dist[ny][nx] > dist[y][x] + 1) {
                    dist[ny][nx] = dist[y][x] + 1;
                    q.push(make_pair(ny,nx));
                }
            }
        }
        ans += dist[ey[k]][ex[k]];
        q.push(make_pair(ey[k],ex[k]));
        REP (i,h) REP (j,w) dist[i][j] = INF;
        dist[ey[k]][ex[k]] = 0;
    }
    cout << ans << endl;
    return 0;
}