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 <algorithm>
using namespace std;
const int INF = 100000000;
typedef pair<int,int> P;

struct something{
	int x;
	int y;
}	ord[12];
char maze[1005][1005];
int h,w,n;


int d[1005][1005];

int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
int bfs(something s,something g){
	queue<P> que;
	for (int i=1;i<=h;i++)
		for (int j=0;j<=w;j++) d[i][j] = INF;
		que.push(P(s.x,s.y));
		d[s.x][s.y] = 0;
		while (que.size()){
			P p=que.front();que.pop();
			if (p.first == g.x && p.second == g.y) break;
			for (int i=0;i<4;i++){
				int nx=p.first + dx[i],ny=p.second + dy[i];
				if (1<=nx && nx<=h && 1<=ny && ny<=w && maze[nx][ny]!='X' && d[nx][ny] == INF){
					que.push(P(nx,ny));
					d[nx][ny] = d[p.first][p.second] + 1;
				}
			}
		}
	return d[g.x][g.y];
}

int main(){
	cin>>h>>w>>n;
	int ans = 0;
	for (int i=1;i<=h;i++)
		for (int j=1;j<=w;j++)	{
			cin>>maze[i][j];
			if (maze[i][j] - 48>= 1 && maze[i][j] - 48 <= 9 ){
				ord[maze[i][j] - 48].x = i;
				ord[maze[i][j] - 48].y = j;
			}else if (maze[i][j] == 'S'){
			 	ord[0].x = i;
			 	ord[0].y = j;
			}
		}
	for (int i=0;i<n;i++){
		ans += bfs(ord[i],ord[i+1]);
	}
	cout<<ans<<endl;
	return 0;
}

C++: #include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <array>
#include <stack>
#include <queue>
#include <chrono>
#include <numeric>

#pragma warning(disable:4996)
#define REP(i,n) for(int i = 0 ; i < n ; ++i)
typedef long long Int;

using namespace std;

struct point{
	Int j, i,step;
	point(Int i_, Int j_,Int s) :i(i_), j(j_),step(s){}
};

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };

queue<point> que;
char tile[1001][1001];
int H, W;
bool ed[1001][1001];

point solve(char target)
{
	while (!que.empty()){
		point now(que.front());
		//ed[now.i][now.j] = true;
		que.pop();
		REP(i, 4){
			int x = now.j + dx[i];
			int y = now.i + dy[i];

			if (x < 0 || y < 0 || x > W || y > H || ed[y][x])
				continue;

			if (tile[y][x] == target){
				return point(y, x,now.step+1);
			}

			if (tile[y][x] != 'X'){
				que.push(point(y, x, now.step + 1));
				ed[y][x] = true;
			}
		}
	}
}

int main()
{
	cin.tie(0); ios::sync_with_stdio(false);
	//fstream fs("input.txt");
	////////////ここから開始///////////
	int n(0);
	cin >> H >> W >> n;

	REP(i, 1001)REP(j, 1001){ tile[i][j] = 'X'; ed[i][j] = false; }

	REP(i, H)REP(j, W)cin >> tile[i][j];

	REP(i, H)REP(j, W){ if (tile[i][j] == 'S')que.emplace(i, j, 0); }

	int ans(0);
	for (int i = 0; i < n; ++i){
		REP(i_1, H + 1)REP(j_1, W + 1){ ed[i_1][j_1] = false; }
		point t = solve('1' + i);
		que = {};
		que.emplace(t);
		ans = que.front().step;
	}

	cout << ans << endl;

	return 0;
}

C++: //情報オリンピック2011 予選問題5「イルミネーション」C++ver
#include<iostream>
#include<queue>
using namespace std;

//yが奇数
int dx[6] = {1, 1, 0,-1, 0, 1};
int dy[6] = {0,-1,-1, 0, 1, 1};
//ｙが偶数
int dx2[6] = {1, 0,-1,-1,-1, 0};
int dy2[6] = {0,-1,-1, 0, 1, 1};

int bfs(int, int, int **);
typedef pair<int, int> P;

int main()
{
	int **map, f1, f2, h, w;

	while(cin >> w >> h && w > 0){
	w += 2; h += 2;

	map = new int *[h];
	for(f1 = 0; f1 < h; f1++)
		map[f1] = new int [w];

	for(f1 = 0; f1 < h; f1++){
		for(f2 = 0; f2 < w; f2++){
			if(f1 == 0 || f1 == h - 1 || f2 == 0 || f2 == w - 1)
				map[f1][f2] = 0;
			else
				cin >> map[f1][f2];
		}
	}

	cout << bfs(w, h, map) << endl;
	}

	return 0;
}

int bfs(int w, int h, int **map)
{
	int f1, nx, ny, cnt = 0;

	queue<P> Q;
	Q.push( P(0, 0) );

	while( !Q.empty() ){
		P p = Q.front(); Q.pop();
		for(f1 = 0; f1 < 6; f1++){

			ny = (p.first % 2 != 0) ? p.first + dy[f1] : p.first + dy2[f1];
			nx = (p.first % 2 != 0) ? p.second + dx[f1] : p.second + dx2[f1];

			if(nx >= 0 && nx < w && ny >= 0 && ny < h){
				if(map[ny][nx] == 0){
					map[ny][nx] = -1;
					Q.push( P(ny, nx) );
				}
				else if(map[ny][nx] == 1)
					cnt++;
			}
		}
	}
	return cnt;
}

C++: #include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define SC(x) scanf("%d",&x);
#define pr(x)  cout << x << endl;
#define mem(arr,v) memset(arr,v,sizeof arr);
#define bug(x) cout << "#x = " << x <<endl;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
typedef long long ll;
using namespace std;
char Mz[maxn][maxn],c;
bool vis[maxn][maxn];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
//int d[maxn][maxn];
int M,N,C;
int px[10],py[10];
int ans;
struct Node{
	int x,y,step;
};
//void dfs(int des,int x,int y,int step) {		// des - destination
//
//	for(int i = 0 ; i < 4 ; i++) {
//		int dx = x + dir[i][0];
//		int dy = y + dir[i][1];
//		if(Mz[dx][dy] == des + '0')			// find the des
//			ans = min(ans,step + 1);
//		if(Mz[dx][dy] != 'X' && Mz[dx][dy] != -1 && !vis[dx][dy]) {
//			vis[dx][dy] = 1;
//			dfs(des,dx,dy,step + 1);
//			vis[dx][dy] = 0;
//		}
//	}
//}

int bfs(int des,int sx,int sy){
	Node node;
	node = {sx,sy,0};
	queue<Node> q;
	q.push(node);
	while(!q.empty()){
		node =  q.front();	q.pop();
		int x = node.x, y = node.y;
		vis[x][y] = 1;
		int step =  node.step;
		for(int i =0 ; i < 4 ; i++){
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if(Mz[dx][dy] == 'X' || Mz[dx][dy] == -1 || vis[dx][dy])	continue;
			if(Mz[dx][dy] == des + '0')
				return step + 1;
			node = {dx,dy,step + 1};
			q.push(node);			
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
//	freopen("in.txt","r",stdin);
	while(cin >> N >> M >> C) {
		mem(Mz,-1)
		mem(px,0)  mem(py,0)

		for(int i = 1 ; i <= N ; i++)
			for(int j = 1; j <= M ; j++) {
				cin >> c;
				Mz[i][j] = c;
				if(c == '.' || c == 'X')	continue;
				if(c == 'S') px[0] = i, py[0] = j;
				else
					px[c - '0'] = i , py[c - '0'] = j;
			}
		int res = 0;
		for(int i = 0 ; i < C ; i++) {
			if(px[i] && py[i]) {
				mem(vis,0);
				vis[px[i]][py[i]] = 1;
//				dfs(i + 1,px[i],py[i],0);
				res += bfs(i + 1,px[i],py[i]);
			}
		}
		pr(res)
	}
}