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<stdio.h>
#include<iostream>
using namespace std;
#include<queue>
int map[1002][1002]={0},r[1002][1002]={0};
struct A{
int t,h,x,y;
};
int main(){
int h,w,n,i,j,m=0,g[2],k=0,b;
g[0]=1;
g[1]=-1;
char s[1001];
A a;
queue<A> q;
cin>>h>>w>>n;
for(i=0;i<=h+1;i++){
map[i][0]=-1;
map[i][w+1]=-1;
}
for(i=0;i<=w+1;i++){
map[0][i]=-1;
map[h+1][i]=-1;
}
for(i=1;i<=h;i++){
	scanf("%s",s);
	for(j=0;j<=w;j++){
		b=s[j];
		if(b>48&&b<58)
			map[i][j+1]=b-48;
		else if(s[j]=='S'){
			a.x=i;
			a.y=j+1;
			a.t=0;
			a.h=1;
			q.push(a);
		}
		else if(s[j]=='X')
			map[i][j+1]=-1;
	}
}
while(!q.empty()){
	a=q.front();
	q.pop();
	if(map[a.x][a.y]==a.h){
		a.h++;
		k=0;
		while(!q.empty()){
			q.pop();
		}
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				r[i][j]=0;
			}
		}
	}
	k++;
	r[a.x][a.y]=k;
	if(a.h==n+1){
		m=a.t;
		break;
	}
	a.t++;
	for(i=0;i<2;i++){
		if(map[a.x+g[i]][a.y]!=-1&&r[a.x+g[i]][a.y]==0){
			a.x+=g[i];
			q.push(a);
			a.x-=g[i];
		}
		if(map[a.x][a.y+g[i]]!=-1&&r[a.x][a.y+g[i]]==0){
			a.y+=g[i];
			q.push(a);
			a.y-=g[i];
		}
	}
}
cout<<m<<endl;
return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int n,m,l,cnt,mx,my;
char a[1019][1019];
int vis[1019][1019];
pair<int,int> p[10],st;
int mov[4][2] = {1,0,0,-1,-1,0,0,1};
struct status
{
    int x,y;
    int ord;
    int fx;
    status(int a,int b,int c,int s)
    {
        x = a, y = b, ord = c, fx = s;
    }
    bool operator < (struct status t) const
    {
        if(ord != t.ord) return ord > t.ord;
        else return fx > t.fx;
    }
}tt[4];

void bfs(int x,int y,int color)
{
    queue <struct status> q;
    struct status temp(x,y,0,fabs(x-p[color].first) + fabs(y - p[color].second));
    q.push(temp);
    int flag = 0;
    while(!q.empty())
    {
        struct status nw = q.top();
        q.pop();
        if(nw.x == p[color].first && nw.y == p[color].second)
        {
            cnt += nw.ord;
            break;
        }
        vis[nw.x][nw.y] = 1;
        for(int i=0;i<4;i++)
        {
            int tx = mov[i][0] + nw.x, ty = nw.y + mov[i][1];
            if(tx>=0 && tx< n && ty>=0 && ty< m && !vis[tx][ty] && a[tx][ty] != 'X')
            {
                struct status tmp(tx,ty,nw.ord+1,fabs(tx-p[color].first) + fabs(ty - p[color].second));
                tt[i] = tmp;
                vis[tx][ty] = 1;
            }
        }
        sort(tt,tt+4);
        for(int i=0;i<4;i++) q.push(tt[i]);
    }
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&l))
    {
        getchar();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j]>='0' && a[i][j]<='9')
                    p[a[i][j]-'0'].first = i, p[a[i][j]-'0'].second = j;
                if(a[i][j] == 'S') st.first = i, st.second = j;
            }
            getchar();
        }

        int sx = st.first, sy = st.second;
        cnt = 0;
        for(int i=1;i<=l;i++)
        {
            memset(vis,0,sizeof(vis));
            bfs(sx,sy,i);
            sx = p[i].first, sy = p[i].second;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

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

#define rep(i, a, b) for(int i = (a); (i) < (b); (i)++)
#define ft first
#define sd second

using namespace std;

char m[1000][1000];
int dis[1000][1000];
queue<pair<int, int> > state;

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

  cin >> h >> w >> n;

  int sx, sy;
  rep(i, 0, h) {
    rep(j, 0, w) {
      cin >> m[j][i];
      if(m[j][i] == 'S') {
	sx = j;
	sy = i;
      }
    }
  }

  pair<int, int> p;
  p.ft = sx;
  p.sd = sy;

  rep(i, 0, h) {
    rep(j, 0, w) {
      dis[j][i] = -1;
    }
  }
  dis[sx][sy] = 0;
  state.push(p);

  int dx[4] = {-1,   0,  1, 0};
  int dy[4] = { 0,  -1,  0, 1};
  int map2[1000][1000];
  for(int lp = 1; lp <= n; lp ++) {
    rep(i, 0, h) {
      rep(j, 0, w) {
	map2[j][i] = 0;
      }
    }

    map2[sx][sy] = 1;
    while(state.size()) {
      pair<int, int> now = state.front();
      state.pop();
      if(m[now.ft][now.sd] - '0' == lp) {
	sx = now.ft;
	sy = now.sd;
	break;
      }
      
      rep(lp2, 0, 4) {
	int x = now.ft+dx[lp2];
	int y = now.sd+dy[lp2];
	
	if(x < 0 || w <= x || y < 0 || h <= y) continue;
	if(map2[x][y] == 0 && m[x][y] != 'X') {
	  state.push(make_pair(x, y));
	  dis[x][y] = dis[now.ft][now.sd] + 1;
	  map2[now.ft][now.sd] = 1;
	}
      }
    }
    while(state.size()) state.pop();

    state.push(make_pair(sx, sy));
  }

  cout << dis[sx][sy] << endl;
  return 0;
}

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

void zero();

struct p{
	int x, y, cnt;
};
int H, W, N;
int tizu[1001][1001];
bool flag[1001][1001] = { false };
int main(){
	queue<p> que;
	char a;
	char h[10] = "123456789";
	cin >> H >> W >> N;
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			cin >> a;
			if (a == 'S'){
				tizu[i][j] = 0;
				p temp;
				temp.x = j;
				temp.y = i;
				temp.cnt = 0;
				que.push(temp);
			}
			else if (a == 'X'){
				tizu[i][j] = -1;
			}
			else if (a == '.'){
				tizu[i][j] = 0;
			}
			else {
				for (int k = 0; k < 9; k++){
					if (h[k] == a){
						tizu[i][j] = k + 1;
					}
				}

			}
			//cout << tizu[i][j];
		}
		//cout << endl;
	}
	int max = 1;
	int step = 0;
	while (!que.empty()){
		p temp = que.front();
		que.pop();
		if (tizu[temp.y][temp.x] == max){
			max++;
			while (!que.empty()) que.pop();
			if (max - 1 == N) {
				max = temp.cnt;
				break;
			}
			zero();
		}
		if (flag[temp.y][temp.x] == true) continue;
		flag[temp.y][temp.x] = true;
		for (int i = 0; i < 4; i++){
			int dx[4] = { 1, -1, 0, 0 };
			int dy[4] = { 0, 0, 1, -1 };
			int yy = temp.y + dy[i];
			int xx = temp.x + dx[i];
			if (yy > -1 && xx > -1 && yy < H && xx < W && tizu[yy][xx] != -1 && flag[temp.y][temp.x] != true){
				p tt;
				tt.y = yy;
				tt.x = xx;
				tt.cnt = temp.cnt + 1;
				que.push(tt);
			}
		}
	}
	cout << max << endl;
	return 0;
}
void zero(){
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			flag[i][j] = false;
		}
	}
}