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<queue>
#include<string>
#include <cstring>
#include<cstdio>
using namespace std;

  int used[1000][1000];
  char m[1000][1000];
  int H,W,N,sx,sy;
  
  const int dx[4]={1,0,-1,0};
  const int dy[4]={0,1,0,-1};

bool check(int x,int y){
  return x>=0&&y>=0&&x<=W&&y<=H&&m[x][y]!='X';
}

void debug()
{
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++){
      printf("%3d", used[i][j]);
    }
    puts("");
  }
  puts("");
} 
int bfs(int p){
  memset(used, 0, sizeof used);
  queue<pair<int,int> > que;
  que.push(make_pair(sx,sy));
  while(!que.empty()){
    pair<int,int> pos= que.front();
    que.pop();
    for(int i=0;i<4;i++){
      int x=pos.first+dx[i];
      int y=pos.second+dy[i];
      if(check(x,y) && used[x][y] == 0){
       que.push(make_pair(x,y));
       used[x][y] = used[pos.first][pos.second] + 1;
      }
      if(m[x][y]==p+'0'){
       sx=x;
       sy=y;
       return used[x][y];
      }
    }
  }
}



int main()
{
  cin>>H>>W>>N;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>m[i][j];
      if(m[i][j]=='S'){
       sx=i;
       sy=j;
      }	
    }
  }
  int res=0;
  for(int i=1;i<=N;i++){
    res+=bfs(i);
  }
  cout << res << endl;
  
}

C++: #include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int H,W,N;
vector<string> S;
struct P{
	int y,x,c;
};
const int dx [] = {0,1,0,-1};
const int dy [] = {-1,0,1,0};

bool in_range(int y,int x)
{
	return y >= 0 && y < H && x >= 0 && x < W;
}

int bfs(char s,char t)
{
	queue<P> q;
	deque<bool> vis(H * W);
	FOR(i,0,H) FOR(j,0,W){
		if(S [i] [j] == s){
			q.push(P{i,j,0});
			vis [i * W + j] = true;
		}
	}

	while(q.empty() == false){
		P f = q.front();
		q.pop();

		if(S [f.y] [f.x] == t) return f.c;
		FOR(i,0,4){
			int ny = f.y + dy [i],nx = f.x + dx [i];
			if(in_range(ny,nx) == false || S [ny] [nx] == 'X' || vis [ny * W + nx]) continue;
			vis [ny * W + nx] = true;
			q.push(P{ny,nx,f.c + 1});
		}
	}
	return -1;
}

int main()
{
	cin >> H >> W >> N;
	S.assign(H,"");
	FOR(i,0,H){
		cin >> S [i];
	}

	int ans = bfs('S','1');
	FOR(i,2,N + 1){
		ans += bfs('0' + (i - 1),'0' + i);
	}

	cout << ans << endl;

	return 0;
}

C++: #include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;



int main()
{

	queue < pair<int, int> > q;
	pair<int, int> p;



	char **m;
	char c[10] = { "123456789" };
	int **f;
	int n, k, i, i1, c1, i2, sum = 0;
	freopen("2011-yo-t5-in5.txt", "r", stdin);
	cin >> n;
	cin >> k;
	cin >> c1;

	m = new char *[n + 2];
	f = new int *[n + 2];

	for (i = 0; i < n + 2; i++){
		m[i] = new char[k + 2];
		f[i] = new int[k + 2];
	}

	for (i = 1; i <= n; i++){
		for (i1 = 1; i1 <= k; i1++){
			cin >> m[i][i1];
		}
	}

	for (i = 0; i < n + 2; i++){
		for (i1 = 0; i1 < k + 2; i1++){
			if (i == 0 || i == n + 1){
				m[i][i1] = 'X';
			}
			else if (i1 == 0 || i1 == k + 1){
				m[i][i1] = 'X';
			}
		}
	}

	for (i = 1; i <= n; i++){
		for (i1 = 1; m[i][i1] != '\0'; i1++){
			if (m[i][i1] == 'S'){
				q.push(make_pair(i, i1));
			}
		}
	}



	pair<int, int> temp;

	temp = q.front();

	for (i = 0; i < c1; i++){

		for (i1 = 0; i1 < n + 2; i1++){
			for (i2 = 0; i2 < k + 2; i2++){
				if (i1 == 0 || i1 == n + 1){
					f[i1][i2] = 1;
				}
				else if (i2 == 0 || i2 == k + 1){
					f[i1][i2] = 1;
				}
				else
					f[i1][i2] = -1;
			}
		}

		f[temp.first][temp.second] = 0;

		while (!q.empty()){
			p = q.front();
			q.pop();

			int x[4] = { -1, 1, 0, 0 }, y[4] = { 0, 0, -1, 1 };

			for (int j = 0; j < 4; j++){

				//いける場所の捜索
				if (m[p.first + x[j]][p.second + y[j]] != 'X' && f[p.first + x[j]][p.second + y[j]] < 0){
					q.push(make_pair(p.first + x[j], p.second + y[j]));
					f[p.first + x[j]][p.second + y[j]] = f[p.first][p.second] + 1;
				}
			}
			//ゴールかどうか？
			if (m[p.first][p.second] == c[i]){
				sum += f[p.first][p.second];
				temp = p;
				while (!q.empty()){
					q.pop();
				}
				q.push(p);
				break;
			}
		}
	}

	cout << sum << endl;

	return 0;
}

C++: #include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <queue>
#include <complex>
#include <climits>
#include <cstring>
#include <cstdlib>

typedef long long ll;

using namespace std;

#define INF 1000000

int H, W, N;
int sx, sy;	
int res = 0;
int d[1100][1100];
char maze[1100][1100];
pair<int, int> cheese[10];

void bfs(int HP){
	queue<pair<int, int> > que;

	sx = cheese[HP-1].first, sy = cheese[HP-1].second;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			d[i][j] = INF;
		}
	}	
	que.push(pair<int, int>(sx, sy));
	d[sx][sy] = 0;

	while(que.size()){
		pair<int, int> p = que.front(); que.pop();
		if((maze[p.first][p.second] - '0') == HP) break;
		for(int dx=-1; dx<=1; ++dx)
			for(int dy=-1; dy<=1; ++dy){
				if(abs(dx-dy) != 1) continue;
				int nx = p.first + dx, ny = p.second + dy;
				if(0 <= nx && nx < H && 0 <= ny && ny < W && maze[nx][ny] != 'X' && d[nx][ny] == INF){
					que.push(pair<int, int>(nx, ny));
					d[nx][ny] = d[p.first][p.second] + 1;
				}
			}
	}

	if(HP == N){
		res += d[cheese[HP].first][cheese[HP].second];
		return;
	}

	res += d[cheese[HP].first][cheese[HP].second];
	bfs(HP+1);
	return;
}

int main(void){
	cin >> H >> W >> N;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			cin >> maze[i][j];
			if(maze[i][j] - '0' >= 1 && maze[i][j] - '0' <= N){
				cheese[maze[i][j] - '0'] = pair<int, int>(i, j);
			} else if(maze[i][j] == 'S'){
				cheese[0] = pair<int, int>(i, j);
			}
		}
	}

	bfs(1);
	int r = res;
	cout << r << endl;
	while(1);
	return 0;
}