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 <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define INF 0x7f7f7f7f
#define PI acos(-1.0)

#define L(x)    (x) << 1
#define R(x)    (x) << 1 | 1
#define lowbit(x)   (x)&(-x)
#define Mid(l, r)   (l + r) >> 1
#define Min(x, y)   (x) < (y) ? (x) : (y)
#define Max(x, y)   (x) < (y) ? (y) : (x)
#define iabs(x)     (x) < 0 ? -(x) : (x)
#define CLR(arr, val)    memset(arr, val, sizeof(arr))

using namespace std;

char map[1024][1024];
bool vis[1024][1024];
int cur, h, w;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

struct node {
	int x, y, step;
} sta, now;

bool check(int x, int y) {
	if (x >= 0 && x < h && y >= 0 && y < w && !vis[x][y] && map[x][y] != 'X')	return true;
	return false;
}



void bfs(node s) {
	memset(vis, 0, sizeof(vis));

	queue<node> que;
	s.step = 0;
	que.push(s);
	node next;
	while (!que.empty()) {
//		cout << "h\n";
		s = que.front();
//		cout << s.x << ' ' << s.y << ' ' << cur << endl;
		que.pop();
		if (map[s.x][s.y] == cur + '0')	{
			sta = s;
			return ;
//			s.step;
		}

//		cout << "a\n";
		for (int i = 0; i < 4; i++) {
//			cout << i << endl;
			next.x = s.x + dir[i][0];
			next.y = s.y + dir[i][1];
			next.step = s.step + 1;
			if (check(next.x, next.y)) {
				vis[next.x][next.y] = true;
				que.push(next);
			}

		}
	}
}

int main() {
	int n;
	while (cin >> h >> w >> n) {
//		memset(map, 0, sizeof(map));
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				if (map[i][j] == 'S')	sta.x = i, sta.y = j, map[i][j] = '.';
			}
		}
		sta.step = 0;
		int ans = 0;
		for (cur = 1; cur <= n; cur++) {
			bfs(sta);
			ans += sta.step;
			//cout << ans << endl;
		}
		cout << ans << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <utility>
#include <queue>
using namespace std;

const int limit = 1000;
char grid[limit+1][limit+1];
int h, w, n;

class state{
public:
  int x, y, t;
  state(int x, int y, int t):
    x(x), y(y), t(t){}
};

int solve();
int bfs(int, int, int, int);

int main(){

  cout << solve() << endl;

  return 0;
}

int solve(){
  cin >> h >> w >> n;
  //スタート地点を取って来る
  int sx[n], sy[n];
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++) {
      cin >> grid[i][j];
      if(grid[i][j]=='.' || grid[i][j]=='X') continue;

      else if(grid[i][j]=='S'){
        sx[0] = j; sy[0] = i;
      }

      else{ //grid[i][j] == int
        int num = grid[i][j]-'0';
        sx[num] = j; sy[num] = i;
      }
    }
  }

  int ans=0;

  for(int i=0; i<n; i++){
    ans += bfs(sx[i], sy[i], sx[i+1], sy[i+1]);
  }

  return ans;
}

int bfs(int sx, int sy, int gx, int gy){
  bool visited[h][w];
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++) visited[i][j] = false;
  }

  queue<state> q;
  q.push(state(sx, sy, 0));
  visited[sy][sx] = true;

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

  int ans;
  while(!q.empty()){
    state now = q.front(); q.pop();
    if(now.x==gx && now.y==gy){
      ans = now.t;
      break;
    }

    for(int i=0; i<4; i++){
      int nx = now.x+dx[i], ny = now.y+dy[i];
      if(!visited[ny][nx] && 0<=nx && nx<w && 0<=ny && ny<h && grid[ny][nx] != 'X'){
        visited[ny][nx] = true;
        q.push(state(nx, ny, now.t+1));
      }
    }
  }

  return ans;
}

C++: #include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct ST{
	int a;
	int b;
	int c;
	int d;
};
int map[1001][1001];
int check[1001][1001];
int q[4]={1,0,-1,0};
int p[4]={0,-1,0,1};
int main(){
	queue <ST> Q;
	ST x;
	ST y;
	int h,w,n;
	int i,j,m;
	char s;
	memset(map,0,sizeof(map));
	memset(check,0,sizeof(check));
	char num[10]={'0','1','2','3','4','5','6','7','8','9'};
	cin>>h>>w>>n;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>s;
			if(s=='S'){
				x.a=i;
				x.b=j;
				x.c=0;
				x.d=1;
				Q.push(x);
			}
			else if(s=='X'){
				map[i][j]=-1;
			}
			else{
				for(m=1;m<10;m++){
					if(s==num[m]){
						map[i][j]=m;
					}
				}
			}
		}
	}
	/*for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cout<<map[i][j];
		}
		cout<<endl;
	}*/
	while(!Q.empty()){
		y=Q.front();
		Q.pop();
		if(check[y.a][y.b]==1)continue;
		check[y.a][y.b]=1;
		if(y.d==map[y.a][y.b]){
			if(n==y.d){
				cout<<y.c<<endl;
				break;
			}
			while(!Q.empty()){
				Q.pop();
			}
			y.d++;
			x=y;
			Q.push(x);
			memset(check,0,sizeof(check));
			continue;
		}
		for(i=0;i<4;i++){
			if(y.a+q[i]>=0&&y.b+p[i]>=0&&y.a+q[i]<h&&y.b+p[i]<w&&map[y.a+q[i]][y.b+p[i]]!=-1&&check[y.a+q[i]][y.b+p[i]]==0){
				x.a=y.a+q[i];
				x.b=y.b+p[i];
				x.c=y.c+1;
				Q.push(x);
			}
		}
	}
	return 0;
}

C++: #include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int h,w,n;
char factory[1005][1005];
int vis[1005][1005];
int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

int bfs(int sx,int sy,int n)
{
    memset(vis,0,sizeof(vis));
    queue<pair<int, int> > q;
    queue<int> qstep;
    q.push(make_pair(sx,sy));
    qstep.push(0);
    char target = '1';
    while(!q.empty()){
        pair<int,int> p = q.front(); q.pop();
        int step = qstep.front(); qstep.pop();
        int x = p.first;
        int y = p.second;
        //cout<<x<<":"<<y<<endl;
        for(int i=0;i<4;++i){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx<0||xx>=h||yy<0||yy>=w) continue;
            if(factory[xx][yy] == target){
                if(target == ('0'+n)) return step + 1;
                while(!q.empty()) q.pop();
                while(!qstep.empty()) qstep.pop();
                q.push(make_pair(xx,yy));
                qstep.push(step+1);
                //cout<<target<<endl;
                target += 1;
                memset(vis,0,sizeof(vis));
                vis[xx][yy]=1;
                break;
            }else if(factory[xx][yy] != 'X'){
                if(vis[xx][yy]) continue;
                vis[xx][yy] = 1;
                q.push(make_pair(xx,yy));
                qstep.push(step+1);
            }
        }
    }
}

int main()
{
    //freopen("input.in","r",stdin);
    while(cin>>h>>w>>n){
        int sx,sy;
        for(int i=0;i<h;++i){
            for(int j=0;j<w;++j){
                cin>>factory[i][j];
                if(factory[i][j]=='S'){
                    sx = i;
                    sy = j;
                }
            }
        }
        cout<<bfs(sx,sy,n)<<endl;
    }
    return 0;
}