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<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int h,w,n;
  cin>>h>>w>>n;
  string Map[h];
  queue<pair<pair<int,int>,int> >que;
  for(int i=0;i<h;i++){
    cin>>Map[i];
    for(int j=0;j<w;j++){
      if(Map[i][j]=='S')
	que.push(mp(mp(i,j),0));
    }
  }
  ll ans=0;
  int hp=1;
  int vx[4]={1,0,-1,0};
  int vy[4]={0,1,0,-1};
  bool used[h+10][w+10]={};
  while(!que.empty()){
    pair<int,int>now=que.front().F;
    int score=que.front().S;
    que.pop();
    //cout<<now.F<<" "<<now.S<<" "<<score<<endl;
    for(int i=0;i<4;i++){
      int x=now.F+vx[i],y=now.S+vy[i];
      if(x>=0&&x<h&&y>=0&&y<w&&!used[x][y]&&Map[x][y]!='X'){
	if('0'<=Map[x][y]&&Map[x][y]<=hp+'0'){
	  memset(used,0,sizeof(used));
	  while(!que.empty())que.pop();
	  que.push(mp(mp(x,y),0));
	  ans+=score+1;
	  hp++;
	  Map[x][y]='.';
	  used[x][y]=true;
	  break;
	}else if(Map[x][y]!='X'){
	  used[x][y]=true;
	  que.push(mp(mp(x,y),score+1));
	}
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
int m[1002][1002]={0},p[1002][1002]={0};
struct r{
int g,l,g2,l2;
};
int main(){
int h,w,n,i,j,a,b[2];
b[0]=1;
b[1]=-1;
char c[2001];
r gl;
queue<r> q;
cin>>h>>w>>n;
for(i=0;i<=h+1;i++){
m[i][0]=-1;
m[i][w+1]=-1;
}
for(i=0;i<=w+1;i++){
m[0][i]=-1;
m[h+1][i]=-1;
}
for(i=1;i<=h;i++){
	scanf("%s",c);
	for(j=1;j<=w;j++){
		a=c[j-1];
		if(a>=49&&a<=57){m[i][j]=a-48;}
		if(c[j-1]=='X'){m[i][j]=-1;}
		if(c[j-1]=='S'){
		gl.g=i;
		gl.g2=j;
		gl.l=0;
		gl.l2=1;
		q.push(gl);
		}
	}
}
while(!q.empty()){
	gl=q.front();
	q.pop();
	if(m[gl.g][gl.g2]==gl.l2){
		gl.l2++;
		if(gl.l2==n+1){
			break;
		}
	}
	p[gl.g][gl.g2]=gl.l2;
gl.l++;
	for(i=0;i<2;i++){
		if(m[gl.g+b[i]][gl.g2]!=-1 && p[gl.g+b[i]][gl.g2]!=gl.l2){
			gl.g+=b[i];
			q.push(gl);
			gl.g-=b[i];
		}
		if(m[gl.g][gl.g2+b[i]]!=-1 && p[gl.g][gl.g2+b[i]]!=gl.l2){
			gl.g2+=b[i];
			q.push(gl);
			gl.g2-=b[i];
		}
	}
}
cout<<gl.l<<endl;
return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
typedef pair<unsigned short,unsigned short> P;
typedef pair<unsigned char,int> T;
typedef pair<T,P> PP;
#define rep(i,n) for(i=0;i<n;i++)
#define MAX 1000
char F[MAX][MAX];
char Dx[]={1,0,-1,0},Dy[]={0,1,0,-1};
unsigned short h,w,n,x,y,nx,ny;
P dist[10];
int bfs()
{
  bool used[9][MAX][MAX]={};
  int c,res=0,u=0;
  unsigned char t,i;
  PP p;
  queue<PP> q;
  rep(i,9)
    q.push(PP(T(i+'1',0),dist[i]));
  while(!q.empty()){
    p=q.front();
    q.pop();
    t=p.first.first;
    if(u&(1<<(t-'1')))continue;
    c=p.first.second;
    x=p.second.first;
    y=p.second.second;
    c++;
    rep(i,4){
      nx=x+Dx[i]; ny=y+Dy[i];
      if(nx<w&&ny<h&&F[ny][nx]!='X'&&!used[t-'1'][ny][nx]){
        used[t-'1'][ny][nx]=true;
        if(F[ny][nx]==t){
          u|=(1<<(t-'1'));
          res+=c;
        }
        else{
          q.push(PP(T(t,c),P(nx,ny)));          
        }
      }
    }
  }
  return res;
}
int main(void)
{
  unsigned short i,j;
  int res;
  scanf("%hd%hd%hd",&h,&w,&n);
  rep(i,h) rep(j,w){
    scanf(" %c",F[i]+j);
    if(F[i][j]=='S')
      dist[0]=P(j,i);
    else if(F[i][j]!='X'&&F[i][j]!='.')
      dist[F[i][j]-'0']=P(j,i);
  }
  res=bfs();
  printf("%d\n",res);
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <string>

#define rep(i, b) for(int i = 0; i < b; i++)

using namespace std;

typedef pair<int,int> P;

int main(){
    int h, w, n;
    cin >> h >> w >> n;

    int area[1001][1001] = {0};
    vector<string> field(h);

    rep(i,h) cin >> field[i];
   
    int ans = 0;
    int x, y;

    rep(i,h) rep(j,w) if(field[i][j] == 'S'){
        x = i;
        y = j;
        break;
    }

    rep(i,n){
        char ob = i + '0' + 1;
        rep(a,h) rep(b,w) area[a][b] = 0;
        queue<P> bfs;
        bfs.push(P(x,y));
        while(1){
            int u = bfs.front().first;
            int v = bfs.front().second;
            bfs.pop();
            if(field[u][v] == ob){
                ans += area[u][v];
                x = u;
                y = v;
                break;
            }
            if(u>0 && !area[u-1][v] && field[u-1][v] != 'X'){
                bfs.push(P(u-1,v));
                area[u-1][v] = area[u][v]+1;
            }
            if(v>0 && !area[u][v-1] && field[u][v-1] != 'X'){
                bfs.push(P(u,v-1));
                area[u][v-1] = area[u][v]+1;
            }
            if(u<h-1 && !area[u+1][v] && field[u+1][v] != 'X'){
                bfs.push(P(u+1,v));
                area[u+1][v] = area[u][v]+1;
            }
            if(v<w-1 && !area[u][v+1] && field[u][v+1] != 'X'){
                bfs.push(P(u,v+1));
                area[u][v+1] = area[u][v]+1;
            }
        }
    }
    cout << ans << endl;
}