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 <cstdlib>
#include <queue>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
using namespace std;

int main()
{
    const int INF = 10000;
    int w, h, n, si, sj, ni, nj, ti, tj, s_d, next_itr;
    pair<int, int> tmp_p;
    cin >> h >> w >> n;
    vector<string> field(h);
    vector<vector<int>> d;
    vector<pair<int, int>> cheeze(n+1);
    d.resize(h);
    queue<pair<int, int>> q;
    for(int i=0; i<h; ++i){
        cin >> field[i];
        d[i].resize(w);
        for(int j=0; j<w; ++j){
            d[i][j] = INF;
            if(field[i][j] == 'S'){
                si = i;
                sj = j;
            }
            if(0 <= field[i][j] - '1' && field[i][j] - '1' <= '9' - '1'){
                cheeze[field[i][j] - '1' + 1] = make_pair(i, j);
                // cout << "pair: " << (abs(field[i][j] - '1') + 1) << " (" << i << ", " << j << ")" << endl;
            }
        }
    }
    // push start point
    q.push(make_pair(si, sj));
    d[si][sj] = 0;
    s_d = -1;
    next_itr = 1;
    ti = cheeze[next_itr].first;
    tj = cheeze[next_itr].second;
    while(!q.empty()){
        tmp_p = q.front();
        q.pop();
        ni = tmp_p.first;
        nj = tmp_p.second;
        // cout << ni << " " << nj << ":" << d[ni][nj] << endl;
        if(ni == ti && nj == tj){
            s_d = d[ni][nj];
            queue<pair<int, int>>().swap(q);
            // cout << "Clear S_d is " << s_d << endl;
            q.push(make_pair(ni, nj));
            for(int i=0; i<h; ++i){
                for(int j=0; j<w; ++j){
                    if(i == ni && j == nj){
                        continue;
                    }
                    d[i][j] = INF;
                }
            }
            if(next_itr >= n){
                break;
            }
            else {
                next_itr++;
                ti = cheeze[next_itr].first;
                tj = cheeze[next_itr].second;
            }
        }
        // up
        if(0 <= ni-1 && d[ni-1][nj] == INF && field[ni-1][nj] != 'X'){
            d[ni-1][nj] = d[ni][nj] + 1;
            q.push(make_pair(ni-1, nj));
        }
        // down
        if(ni+1 < h && d[ni+1][nj] == INF && field[ni+1][nj] != 'X'){
            d[ni+1][nj] = d[ni][nj] + 1;
            q.push(make_pair(ni+1, nj));
        }
        // left
        if(0 <= nj-1 && d[ni][nj-1] == INF && field[ni][nj-1] != 'X'){
            d[ni][nj-1] = d[ni][nj] + 1;
            q.push(make_pair(ni, nj-1));
        }
        // right
        if(nj+1 < w && d[ni][nj+1] == INF && field[ni][nj+1] != 'X'){
            d[ni][nj+1] = d[ni][nj] + 1;
            q.push(make_pair(ni, nj+1));
        }
    }
    cout << d[ti][tj] << endl;
    return 0;
}

C++: #include <iostream>
#include <queue>
using namespace std;

int h,w,n;
int en;//energy indicates which cheese to eat next
const int MAX_N=1000;
char map[MAX_N][MAX_N];
struct point{
    int x,y;
    int step;
    point(int xx, int yy, int ss){
        x=xx;
        y=yy;
        step=ss;
    }
};
struct point p[10];
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};

int ok(int x, int y){
    if(x>=0 && x<h && y>=0 && y<w) return 1;
    return 0;
}

int bfs(int next){
    int nextcheese = next +1; int res=0;
    
    queue<point> q;
    point cur(p[next].x, p[next].y,0);
    q.push(cur);
    while(q.size()){
        cur = q.front(); q.pop(); 
        int x=cur.x, y=cur.y;
        int nx, ny;
        for(int i=0; i<4; i++){
            nx = x+dx[i]; ny=y+dy[i];
            if(ok(nx, ny)){
                if((map[nx][ny]-'0')==nextcheese) return ++cur.step;
                if(map[nx][ny]=='.'){
                    point temp(nx, ny, cur.step+1);
                    q.push(temp);
                }
            }
        }
    }
}

void solve(){
    int sx, sy;
    scanf("%d%d%d", &h, &w, &n);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>ch; map[i][j]=ch;
            switch(ch){
                case '.': break;
                case 'X': break;
                case 'S': p[0].x = i; p[0].y = j; break;
                default:
                int t=ch-'0';
                p[t].x = i; p[t].y = j;
            }
        }
    }
    int step=0;
    for(int i=0; i<n; i++){
        step+=bfs(i);
    }
    printf("%d", step);
}


int main(){
    solve();
}

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];
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=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();
			}
			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;
}