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 <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>

//ios::sync_with_stdio(false);

using namespace std;

const int INF = (1<<30) - 1;

int bfs(vector<string>& field, pair<int, int> start, pair<int, int> end){
    int dh[] = {0, 0, 1, -1};
    int dw[] = {1, -1, 0, 0};
    
    int H = field.size();
    int W = field[0].size();
    vector<vector<int> > d(H, vector<int>(W, INF));
    queue<pair<int, int> > nodes;
    
    d[start.first][start.second] = 0;
    nodes.push(start);
    
    while(!nodes.empty()){
        auto node = nodes.front(); nodes.pop();
        for(int i=0; i<4; i++){
            int nh = dh[i] + node.first;
            int nw = dw[i] + node.second;
            
            if(0<=nh&&nh<H && 0<=nw&&nw<W && field[nh][nw] != 'X' && d[nh][nw] == INF){
                d[nh][nw] = d[node.first][node.second] + 1;
                
                if(nh == end.first && nw == end.second)
                    return d[nh][nw];
                
                nodes.push(make_pair(nh, nw));
            }
        }
    }
    return -1;
}

int main(){
    int H, W, N;
    cin >> H >> W >> N;
    
    vector<string> field(H);
    for(int i=0; i<H; i++)
        cin >> field[i];
    
    vector<pair<int, int> > cheeses(N+1);
    
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            char& c = field[i][j];
            if(c == 'S'){
                cheeses[0] = make_pair(i, j);
            }else if(c != '.' && c != 'X'){
                cheeses[c-'0'] = make_pair(i, j);
            }
        }
    }
    
    
    int ans = 0;
    for(int i=0; i<N; i++){
        ans += bfs(field, cheeses[i], cheeses[i+1]);
    }
    
    cout << ans << endl;
    
	return 0;
}

C++: #include <cstdio>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

char map[2048][2048];
int d[2048][2048];
	
pair<int,int> ch[10];

int w,h,n;

const int INF = 999999999;

int solve(pair<int,int> s,pair<int,int> g){
	//printf("(%d,%d) -> (%d,%d)\n",s.first,s.second,g.first,g.second);
	
	for(int i=0;i<w;i++){
		for(int j=0;j<h;j++){
			d[i][j] = INF;
		}
	}
	pair<int,int> v[4] = {
		pair<int,int>(1,0),
		pair<int,int>(-1,0),
		pair<int,int>(0,1),
		pair<int,int>(0,-1)
	};
	
	
	queue< pair<int,int> > que;
	pair<int,int> p,pp;
	
	d[s.first][s.second] = 0;
	que.push(s);
	
	
	while(que.size() > 0){
		if(d[g.first][g.second] != INF){
			return d[g.first][g.second];
		}
		p = que.front();
		//printf("(%d,%d)\n",g.first,g.second);
		que.pop();
		for(int i=0;i<4;i++){
			pp.first = p.first + v[i].first;
			pp.second = p.second + v[i].second;
			if(pp.first < 0 || pp.first >= w || pp.second < 0 || pp.second >= h){continue;}
			if(map[pp.first][pp.second] != 'X' && d[pp.first][pp.second] == INF){
				d[pp.first][pp.second] = d[p.first][p.second] + 1;
				que.push(pp);
			}
		}
	}
	
	return -1;
}

int main(){
	char c;
	scanf("%d %d %d",&h,&w,&n);
	//printf("%dx%d %d\n",w,h,n);
	for(int j=0;j<h;j++){
		for(int i=0;i<w;i++){
			while(scanf("%c",&c) && c == '\n');
			map[i][j] = c;
			if('1' <= c && c <= '9'){
				ch[c - '1' + 1] = pair<int,int>(i,j);
			}
			if('S' == c){
				ch[0] = pair<int,int>(i,j);
			}
		}
	}
	
	int ans = 0;
	int ss;
	for(int i = 0;i < n;i++){
		pair<int,int> s,g;
		s = ch[i];
		g = ch[i + 1];
		//printf("(%d,%d) -> (%d,%d)\n",s.first,s.second,g.first,g.second);
		ss = solve(s,g);
		ans += ss;
	}
	printf("%d\n",ans);
}

C++: #include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

struct OZAWA
{
	int x;
	int y;
	int c;
};
int Flag[1000][1000];
char MAP[1000][1000];
queue<OZAWA> Q;
OZAWA ba,v;
int main(void)
{
	int H,W,N,Nc=0,X[10],Y[10];
	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=0;i<H;i++){
		for(int j=0;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[0],Y[0]);
	while(!Q.empty()){
		//printf("QA\n");
		ba = Q.front();
		Q.pop();
		if(ba.x==X[Nc] && ba.y==Y[Nc]){
			//printf("OZA");
			Nc++;
			memset(Flag,0,sizeof(Flag));
			while(!Q.empty()){
				Q.pop();
			}
			if(Nc == N) break;
			Q.push(ba);
		}
		//printf("aaa\n");
		//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 && (ba.x+mv[i][0])>=0&&(ba.x+mv[i][0])<W&&(ba.y+mv[i][1])>=0&&(ba.y+mv[i][1])<H){
				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;
}