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<cstdio>
#include<iostream>
#include<string>
#include<queue>
#define MAX 1002
using namespace std;

char xy[MAX][MAX];
int cost[MAX][MAX];
int hp[MAX][MAX];

struct state{
  int x;
  int y;
  int co;
  int hp;
  state(){}
  state(int x,int y,int co,int hp):
    x(x),y(y),co(co),hp(hp){}
};

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

int H,W,N;

int solve(int x,int y){
  int i,j;
  queue<state> q;
  q.push( state(x,y,0,1) );
  cost[x][y]=0;
  hp[x][y]=1;

  while( !(q.empty()) ){

    state p = q.front();
    q.pop();

    x=p.x;
    y=p.y;

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

      if( x+dx[i] < 0 || x+dx[i] >= W || y+dy[i] < 0 || y+dy[i] >= H )
	continue;

      if(xy[y+dy[i]][x+dx[i]]=='X') continue;

      if(xy[y+dy[i]][x+dx[i]]-'0' == p.hp){
	
	if(p.hp >= N){
	  return p.co+1;
	}
	
	while( !(q.empty()) ){
	  q.pop();
	}

	printf("%d\n",p.hp+1);
	
	q.push( state(x+dx[i],y+dy[i],p.co+1,p.hp+1) );
	
	break;
	
      }


      if(cost[x+dx[i]][y+dy[i]]<=p.co+1){
	if(hp[x+dx[i]][y+dy[i]]>=p.hp){
	  continue;
	}
      }
      
      
      cost[x+dx[i]][y+dy[i]]=p.co;
      hp[x+dx[i]][y+dy[i]]=p.hp;

      q.push( state(x+dx[i],y+dy[i],p.co+1,p.hp) );


    }

  }

  return -1;
}

main(){
  int i,j,sx,sy;

  cin >> H >> W >> N;

  for(i=0;i<H;i++){
    scanf("%s",xy[i]);
    for(j=0;j<W;j++){
      if(xy[i][j]=='S'){
	sx=j;
	sy=i;
      }
    }
  }

  int n=solve(sx,sy);

  cout << n << endl; 
  
  return 0;
}

C++: #include<cstdio>
#include<utility>
#include<queue>

struct P {int x,y;};

using namespace std;

char map[1005][1005];
int h,w,n;

int distance(char start, char goal) {
    bool visited[1005][1005];
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            visited[i][j] = false;


    queue<pair<P,int> > q;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            if(map[i][j] == start) q.push(pair<P,int>({j,i}, 0));
    
    while(!q.empty()) {
        pair<P,int> t = q.front(); q.pop();
        struct P p = t.first;
        int d = t.second;

        if(p.x < 0 || p.y < 0 || p.x >= w || p.y >= h) continue;
        if(map[p.y][p.x] == 'X') continue;
        if(visited[p.y][p.x]) continue;
        if(map[p.y][p.x] == goal) return d;
        visited[p.y][p.x] = true;
        
        q.push(pair<P,int>({p.x+1,p.y},d+1));
        q.push(pair<P,int>({p.x,p.y+1},d+1));
        q.push(pair<P,int>({p.x-1,p.y},d+1));
        q.push(pair<P,int>({p.x,p.y-1},d+1));
    }
    return -1;
}


int main(void) {
    int res=0;

    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<h;i++)
        scanf("%s",map[i]);
    res += distance('S','1');
    for(int i=1;i<n;i++)
        res += distance('0'+i,'1'+i);

    printf("%d\n",res);

    return 0;
}

C++: #include<algorithm>
#include<iostream>
#include<queue>
#include<ctype.h>
#include<limits.h>

int h, w, n;
int sx, sy;
int gx, gy;
char map[1002][1002];
int d[1001][1001];
bool visited[1001][1001];
int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };
int ans;

void bfs()
{
	d[sx][sy] = 0;
	visited[sx][sy] = true;
	std::queue<std::pair<int,int> > q;
	q.push( std::make_pair<int,int>( sx, sy ) );
	
	while( !q.empty() ){
		std::pair<int,int> p = q.front(); q.pop();
		int x = p.first;
		int y = p.second;
		
		for( int i = 0; i < 4; i++ ){
			int ix = x + dx[i];
			int iy = y + dy[i];
			
			if( ix >= 1 && ix <= w && iy >= 1 && iy <= h && map[ix][iy] != 'X' && !visited[ix][iy] ){
			 	d[ix][iy] = d[x][y] + 1;
				q.push( std::make_pair<int,int>( ix, iy ) );
				visited[ix][iy] = true;
			}
		}	
	}

	return;
}

int main()
{
	std::cin >> h >> w >> n;
	
	for( int i = 1; i <= h; i++ ){
	 	for( int j = 1; j <= w; j++ ){
			std::cin >> map[j][i];
			if( map[j][i] == 'S' ){
			 	sx = j;
				sy = i;
			}
		}
	}
	
	for( int k = 1; k <= n; k++ ){
		for( int i = 1; i <= h; i++ ){
		 	for( int j = 1; j <= w; j++ ){
			 	d[j][i] = INT_MAX / 4;
				visited[j][i] = false;
			}
		}	
		
		bfs();
		
		for( int i = 1; i <= h; i++ ){
		 	for( int j = 1; j <= w; j++ ){
				if( map[j][i] == k + '0' ){
				 	gx = j;
					gy = i;
				}
			}
		}
		
		ans += d[gx][gy];
		
		sx = gx;
		sy = gy;
	}
	
	std::cout << ans << std::endl;

	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
 
typedef struct{
  short x,y;
  int cost;
  short ch;
}mouse;
 
 
mouse t;
short cx,cy,nx,ny,ch,nch,h,w,n;
int cost;
 
main(){
  scanf("%d%d%d ",&h,&w,&n);
  short maxch[h][w];
  char ku[h][w+1];
  
  rep(i,h)fread(ku[i],1,w+1,stdin);
 
 
  rep(i,h)rep(j,w){
    if(ku[i][j]=='S')cx=i,cy=j;
    maxch[i][j]=-1;
  }
 
  queue<mouse> Q;
 
  Q.push((mouse){cx,cy,0,0});
  maxch[cx][cy]=0;
 
  while(!Q.empty()){
    //cout<<Q.size()<<endl;
    t=Q.front();Q.pop();
    cx=t.x,cy=t.y,cost=t.cost;
    ch=t.ch;
 
    rep(i,4){
      nx=cx+dx[i],ny=cy+dy[i];
      if(nx<0 || nx>=h || ny<0 || ny>=w)continue;
      if(ku[nx][ny]=='X')continue;
      nch=ch;
      if(ku[nx][ny]<='9' && ku[nx][ny]>='1' && ku[nx][ny]-'0'==t.ch+1){
        nch=ch+1;
      }
 
      if(maxch[nx][ny]>=nch)continue;
      if(nch==n){
        printf("%d\n",cost+1);
        return 0;
      }
      maxch[nx][ny]=nch;
      Q.push((mouse){nx,ny,cost+1,nch});
    }
  }
}