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 <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()

#define MAX_W 1010
#define MAX_H 1010

int H, W, N;
char A[MAX_H][MAX_W];

// 0 ~ 0b111111111

int bfs() {
  queue<int> q;
  int start_x = 0, start_y = 0;
  rep(y, H) rep(x, W) {
    if (A[y][x] == 'S') {
      start_x = x;
      start_y = y;
    }
  }
  // (x, y, s, hp, dist)
  q.push(start_x); q.push(start_y); q.push(0); q.push(1); q.push(0);
  while (!q.empty()) {
    int x  = q.front(); q.pop();
    int y  = q.front(); q.pop();
    int s  = q.front(); q.pop();
    int hp = q.front(); q.pop();
    int dist = q.front(); q.pop();

    char m = A[y][x];
    if ('1' <= m && m <= '9') {
      int x = (int)m - (int)'0';
      // hp?????????????????°?£???????
      if (hp >= x) {
        int ts = s | (1 << (x-1));
        if (ts != s) {
          hp += 1;
          s = ts;
        }
      }
    }
    // ??´??????
    if (s == ((1<<N) - 1)) return dist;
    int dx[] = {0, 1, 0, -1};
    int dy[] = {-1, 0, 1, 0};
    rep(i, 4) {
      rep(j, 4) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (A[ty][tx] != 'X') {
          q.push(tx);
          q.push(ty);
          q.push(s);
          q.push(hp);
          q.push(dist + 1);
        }
      }
    }
  }
  return -1;
}

int main() {
  cin >> H >> W >> N;
  rep(i, H) cin >> A[i];

  cout << bfs() << "\n";
  return 0;
}

C++: #include <cstdio>
#include <queue>
#include <utility>
using namespace std;
#define mp make_pair
typedef pair<int, int> pint;
const int INF = 100000000;

int h, w, n;
char maze[1024][1024];
int i, j;

struct {
	int x, y;
} dir[4] = {
	{1, 0}, // right
	{0, 1}, // down
	{-1, 0}, // left
	{0, -1} // up
};

int dist[1000][1000];

int bfs(int hp) {
	for(int x = 0; x < w; x++) {
		for(int y = 0; y < h; y++) {
			dist[y][x] = INF;
		}
	}
	dist[i][j] = 0;
	queue<pint> q;
	q.push(mp(i, j));
	while(1) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if(maze[y][x] == (char)('0' + hp)) {
			i = y;
			j = x;
			maze[i][j] = '.';
			break;
		}
		for(int k = 0; k < 4; k++) {
			int nx = x + dir[k].x;
			int ny = y + dir[k].y;
			if(0 <= nx && nx < w && 0 <= ny && ny < h && maze[ny][nx] != 'X') {
				if(dist[ny][nx] == INF) { // never searched
					dist[ny][nx] = dist[y][x] + 1;
					q.push(mp(ny, nx));
				}
			}
		}
	}
	int ret = dist[i][j];
	return ret;
}

int main() {
	scanf(" %d %d %d", &h, &w, &n);
	for(int y = 0; y < h; y++) {
		scanf(" %s", maze[y]);
	}
	int ans = 0;
	{
		bool loop = true;
		for(int x = 0; x < w; x++) {
			for(int y = 0; y < h; y++) {
				if(maze[y][x] == 'S') {
					i = y;
					j = x;
					maze[y][x] = '.';
					loop = false;
					break;
				}
			}
			if(!loop) break;
		}
	}
	for(int x = 1; x <= n; x++) {
		ans += bfs(x);
	}
	printf("%d\n", ans);
	return 0;
}

C++: /*
cd "/Users/yuuki/Desktop/C++/Codes"
g++ -o run run.cpp
./run
*/


//11-5 チーズ
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<random>
#include<cassert>
using namespace std;
#define LL long long
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while(true)

int H,W,N;
string s[1000];
pair<int, int> fact[10];
int dis[10][10];

int cost[1000][1000];

queue<pair<int,int>> que;
void move(int h, int w){
    if(h-1>=0 && s[h-1][w]!='X' && cost[h-1][w]>cost[h][w]+1){
        cost[h-1][w] = cost[h][w]+1;
        //move(h-1,w);
        que.push(make_pair(h-1,w));
    }
    if(h+1<H && s[h+1][w]!='X' && cost[h+1][w]>cost[h][w]+1){
        cost[h+1][w] = cost[h][w]+1;
        //move(h+1,w);
        que.push(make_pair(h+1,w));
    }
    if(w-1>=0 && s[h][w-1]!='X' && cost[h][w-1]>cost[h][w]+1){
        cost[h][w-1] = cost[h][w]+1;
        //move(h,w-1);
        que.push(make_pair(h,w-1));
    }
    if(w+1<W && s[h][w+1]!='X' && cost[h][w+1]>cost[h][w]+1){
        cost[h][w+1] = cost[h][w]+1;
        //move(h,w+1);
        que.push(make_pair(h,w+1));
    }
}

int max_health = 1;
bool fact_b[10];
LL ans = LL_MAX;
void cul(int health, int now, LL c){
    if(health == max_health) ans = min(ans,c);
    else{
        for(int i=1; i<=health && i<=N; i++){
            if(fact_b[i]==false){
                fact_b[i] = true;
                cul(health+i, i, c+dis[now][i]);
            }
        }
    }
}

int main(){
    cin >> H >> W >> N;
    for(int i=0; i<H; i++){
        cin >> s[i];
        for(int j=0; j<W; j++){
            if(s[i][j] == 'S') fact[0] = make_pair(i,j);
            else if(s[i][j] != 'X') fact[s[i][j]-'0'] = make_pair(i,j);
        }
    }

    for(int i=0; i<N-1 || i==0; i++){
        for(int j=0; j<H; j++){
            for(int k=0; k<W; k++){
                cost[j][k] = INT_MAX;
            }
        }
        cost[fact[i+1].first][fact[i+1].second] = 0;
        move(fact[i+1].first, fact[i+1].second);
        while(!que.empty()){
            move(que.front().first, que.front().second);
            que.pop();
        }
        for(int j=0; j<N; j++){
            dis[i+1][j+1] = cost[fact[j+1].first][fact[j+1].second];
            dis[j+1][i+1] = cost[fact[j+1].first][fact[j+1].second];
        }
        if(i == 0){
            dis[0][1] = cost[fact[0].first][fact[0].second];
            dis[1][0] = cost[fact[0].first][fact[0].second];
        }
        max_health += i+1;
    }
    if(N!=1) max_health += N;
    
    for(int i=0; i<N+1; i++){
        fact_b[i] = false;
    }
    fact_b[0] = true;
    cul(1,0,0);
    cout << ans << endl;

    return 0;
}