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>
#define N 1005
#define INFINITY 2000000000
using namespace std;
void bfs();
int h,w,n,num[N][N],d[N*N],M[N][N],u,m;
string color[N*N],in[N*N];
int main(){
  int i,j,k;
  cin >> h >> w >> n;
  for(i=0;i<h+2;i++)
    for(j=0;j<w+2;j++)
      num[i][j]=-1;
  for(i=1;i<=h;i++) cin >> in[i],in[i]='X'+in[i];
  k=0;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(in[i][j]!='X') num[i][j]=k,k++;
    }
  }
  m=max(h,w);
  for(i=0;i<=m;i++)
    for(j=0;j<=m;j++)
      M[i][j]=0;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      if(num[i][j]!=-1&&num[i+1][j]!=-1)
	M[num[i][j]][num[i+1][j]]=M[num[i+1][j]][num[i][j]]=1;
      if(num[i][j]!=-1&&num[i][j+1]!=-1)
	M[num[i][j]][num[i][j+1]]=M[num[i][j+1]][num[i][j]]=1;
    }
  }
  bfs();
  return 0;
}
void bfs(){
  int i,j,p=1,t=0,flag=0,x=1;
  char start='S',goal='1';
  queue<int> q;
  while(1){
    if(flag==1) start=x+'0',goal=x+'0'+1,x++;
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	color[num[i][j]]="WHITE",d[num[i][j]]=INFINITY;
      }
    }
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(in[i][j]==start) color[num[i][j]]="GLAY",d[num[i][j]]=0,q.push(num[i][j]);
      }
    }
    while(q.empty()!=1){
      u=q.front();
      q.pop();
      for(i=1;i<=h;i++){
	for(j=1;j<=w;j++){
	  if(M[u][num[i][j]]&&color[num[i][j]]=="WHITE"){
	    color[num[i][j]]="GLAY";
	    d[num[i][j]]=d[u]+1;
	    q.push(num[i][j]);
	  }
	}
      }
      color[u]="BLACK";
    }
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(in[i][j]==goal) t+=d[num[i][j]];
      }
    }
    flag=1;
    if(x>n) break;
  }
  cout << t << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;

int h, w, n, maze[MAX][MAX];
int b[15];
int r[] = {1, -1, 0, 0};
int z[] = {0, 0, -1, 1};
int d[MAX][MAX];
int ans = 0;

int readchar() {
    for(;;) {
        int ch = getchar();
        if(ch != '\n' && ch != '\r') return ch;
    }
}

int bfs(int x, int y, int x2, int y2)
{
    //cout << x << y << x2 << y2 << endl;

    queue<int> q;
    q.push(x * 10000 + y);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int x1 = v / 10000 + r[i];
            int y1 = v % 10000 + z[i];
            if(x1 == x2 && y1 == y2) {
                d[x1][y1] = d[v / 10000][v % 10000] + 1;
                return 0;
            }
            if(x1 >= 0 && y1 >= 0 && x1 < h && y1 < w && maze[x1][y1] != 'X' && d[x1][y1] == -1) {
                 d[x1][y1] = d[v / 10000][v % 10000] + 1;
                 q.push(x1 * 10000 + y1);
            }
        }
    }
    return 0;
}
int main()
{
    cin >> h >> w >> n;
    for(int i = 0; i < h; ++i)
        for(int j = 0; j < w; ++j) {
             maze[i][j] = readchar();
        if(maze[i][j] == 'S') {
            b[0] = i * 10000 + j;
        }
        if(maze[i][j] != 'S' && maze[i][j] != 'X' && maze[i][j] != '.') {
            b[maze[i][j] - '0'] = i * 10000 + j;
        }
    }
    for(int i = 0; i < n; ++i) {
        memset(d, -1, sizeof(d));
        d[b[i] / 10000][b[i] % 10000] = 0;
        bfs(b[i] / 10000, b[i] % 10000, b[i + 1] / 10000, b[i + 1] % 10000);
        ans += d[b[i + 1] / 10000][ b[i + 1] % 10000];
    }
    cout << ans << endl;
    return 0;
}

C++: #include<iostream>
#include<queue>
using namespace std;
struct Point{int x,y,dist;};
int main()
{
  int H,W,N;
  char vital='1';
  int i,j;
  string field[1000];
  queue<Point>q;
  int dx[4]={0,1,0,-1};
  int dy[4]={-1,0,1,0};
  Point ans;

  cin>>H>>W>>N;
  for(i=0;i<H;i++)cin>>field[i];
  for(i=0;i<H;i++){
    for(j=0;j<W;j++){
      if(field[i][j]=='S'){
	Point p={j,i,0};
	q.push(p);
      }
    }
  }

  while(q.size()){
    Point p=q.front();
    q.pop();
    if(field[p.y][p.x]==vital){
      if(vital-'0'==N){
	ans=p;
	break;
      }
      vital++;
      while(q.size())q.pop();
    }
    for(i=0;i<4;i++){
      Point p2;
      p2.y=p.y+dy[i];
      p2.x=p.x+dx[i];
      p2.dist=p.dist+1;
      if(p2.y<0||H<=p2.y)continue;
      if(p2.x<0||W<=p2.x)continue;
      if(field[p2.y][p2.x]=='X')continue;
      q.push(p2);
    }
  }
  cout<<ans.dist<<endl;
}

C++: #include<iostream>
#include<queue>
#include<string.h>
#include<limits.h>
#include<cstdio>
using namespace std;
const int MAXH = 1100;
const int INF = INT_MAX;
typedef pair<int, int> P;
int H,W,N;
char B[MAXH][MAXH];
int d[MAXH][MAXH];
int sx, sy;
int gx, gy;
int res;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};

void bfs()
{
	queue<P> que;
	que.push(P(sx,sy));
	d[sx][sy] = 0;
	
	while(que.size())
	{
		P p = que.front(); que.pop();
		
		if(p.first== gx && p.second == gy)break;
		for(int i = 0; i<4;i++)
		{
			int nx = p.first+ dx[i], ny = p.second + dy[i];

			if(B[nx][ny] != 'X' && d[nx][ny] ==INF)
				{
				que.push(P(nx,ny));
				d[nx][ny] = d[p.first][p.second] + 1;

				}
		}	
	}
	res+= d[gx][gy];
}

void rest()
{
	for(int i = 1; i<= W;i++)
		for(int j = 1; j<= H; j++)
			d[i][j] = INF;
}
void solve()
{
	for(int che = 1; che <= N; che++)
		for(int i = 1 ; i<= W;i++)
			for(int j = 1; j <= H; j++)
			{
				if(B[i][j] - '0' == che)
				{
					rest();
					gx = i; gy = j;
					bfs();
					sx = gx; sy = gy;
				}
			}	
	cout << res << endl;
}

int main()
{
	
	cin >>H>>W>>N;
	memset(B,'X',sizeof(B));
	for(int j = 1 ; j<= H;j++)
	{
		for(int i = 1; i <= W; i++)
		{
			cin >> B[i][j];
			if(B[i][j] == 'S')
				{sx = i; sy = j;}
		}	
		getchar();
	}

	res = 0;	
	solve();
	
}