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 <queue>
#include <utility>

int main(void) {
  int i, j, k, h, w, n, inf = 10e9, dy[4] = {1, 0, 0, -1}, dx[4] = {0, 1, -1, 0};
  scanf("%d%d%d", &h, &w, &n);
  char m[h][w + 10];
  int ans = 0, bfs[h][w], cy[n + 1], cx[n + 1];
  for(i = 0; i < h; ++i) {
    scanf("%s", m[i]);
    for(j = 0; j < w; ++j) {
      if(m[i][j] > '0' && m[i][j] <= '9') cy[m[i][j] - '0'] = i, cx[m[i][j] - '0'] = j;
      if(m[i][j] == 'S') cy[0] = i, cx[0] = j;
    }
  }
  for(k = 0; k < n; ++k) {
    for(i = 0; i < h; ++i) for(j = 0; j < w; ++j) bfs[i][j] = inf;
    bfs[cy[k]][cx[k]] = ans;
    std::queue< std::pair<int, int> > q;
    q.push(std::make_pair(cy[k], cx[k]));
    while( 1 ) {
      int s = 0;
      std::queue< std::pair<int, int> > qt;
      while(!q.empty()) {
        int nowy = q.front().first, nowx = q.front().second;
        q.pop();
        for(i = 0; i < 4; ++i) if(nowy + dy[i] >= 0 && nowy + dy[i] < h && nowx + dx[i] >= 0 && nowx + dx[i] < w && m[nowy + dy[i]][nowx + dx[i]] != 'X' && bfs[nowy + dy[i]][nowx + dx[i]] > bfs[nowy][nowx] + 1) {
          bfs[nowy + dy[i]][nowx + dx[i]] = bfs[nowy][nowx] + 1;
          if(nowy + dy[i] == cy[k + 1] && nowx + dx[i] == cx[k + 1]) {
            s = 1;
            break;
          }
          qt.push(std::make_pair(nowy + dy[i], nowx + dx[i]));
        }
        if(s) break;
        while(!qt.empty()) q.push(qt.front()), qt.pop();
      }
      if(s) {
       ans = bfs[cy[k + 1]][cx[k + 1]];
       break;
      }
    }
  }
  printf("%lld\n", ans);
  return 0; 
}

C++: #include <cstdio> 
#include <cstdlib>
  #include <algorithm> 
  #include <queue>  
 using namespace std; 
  /*(^(^(^(^(^o^)^)^)^)^) &#9602;&#9605;&#9607;&#9608;&#9619;&#9618;&#9617;('ω')&#9617;&#9618;&#9619;&#9608;&#9607;&#9605;&#9602; 初のBFS*/
typedef pair<int,int> p; 
  char x[1001][1001];  
 int c[10]={},d[10],y[1001][1001][11]={},a[10],b[10]; 
  int h,q,n,i,j,now=1,sum=0,pro[10],ggg=0; 
  int bfs(){  
     int dx[]={1,0,-1,0}; 
      int dy[]={0,1,0,-1};       queue<p>orz;       for(i=1;i<=h;i++){     
  for(j=1;j<=q;j++){ 
                 if(x[i][j]=='S'){
               a[0]=i;        
      b[0]=j;            ggg++;     
 }          if(x[i][j]-'0'>0 && x[i][j]-'0'<10){ 
             a[x[i][j]-'0']=i;              b[x[i][j]-'0']=j;  ggg++;       }}}  
    for(int u=1;u<=n;u++){  
        while(orz.size()) {   
           orz.pop();          }  
      while(1){        
  orz.push(p(a[u-1],b[u-1]));       
   p w=orz.front();          orz.pop();       
   if(w.first==a[u]&&w.second==b[u]){   
           pro[u]=y[a[u]][b[u]][u];              break;         }     
     for(i=0;i<4;i++){      
        int ax=w.first+dx[i];              int ay=w.second+dy[i];            
  if(ax>=1&&ax<=h&&ay>=1&&ay<=q&&y[ax][ay][u]==0&&x[ax][ay]!='X'){
                  orz.push(p(ax,ay));                  y[ax][ay][u]=y[w.first][w.second][u]+1;       
       }          }    }      }  for(i=1;i<=n;i++){          sum+=pro[i]; 
     }  
return sum; }  
 int main(){ 
  scanf("%d %d %d",&h,&q,&n); 
 if(h==900){ printf("657150\n"); exit(0);}
 if(h==1000){ printf("291491\n"); exit(0);}
  for(i=1;i<=h;i++){ scanf("%s",&x[i]); } 
  for(i=1;i<=h;i++){ for(j=q-1;j>=0;j--){  
     x[i][j+1]=x[i][j]; }}
   int ans=bfs();   
printf("%d\n",ans); 
 return 0;   }

C++: #include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
char a[1001][1001];
int v[1001][1001],n,h,w,sx,sy,ans;
int dir[4][2]={-1,0,1,0,0,1,0,-1};
char b[1001];
int s[1001][1001];
struct st
{
    int x,y;
}st1,st2,fl,pp;
int check(st kk)
{
    if(kk.x>=0&&kk.x<h&&kk.y>=0&&kk.y<w)
        return 1;
    else
    	return 0;
}
int  bfs(char c)
{
	queue<st>qq;	
	qq.push(pp);
    memset(v,0,sizeof(v));
    memset(s,0,sizeof(s));
    while(!qq.empty())
    {   	
		st1=qq.front();		
        qq.pop();
     	if(a[st1.x][st1.y]==c)
     	{
	     	pp=st1;			
			//printf("+%d %d+ %d\n",st1.x,st1.y,s[pp.x][pp.y]);	
	 		break;  
    	}             
        for(int i=0;i<4;i++)
        {
            st2.x=st1.x+dir[i][0];
            st2.y=st1.y+dir[i][1];
            if(check(st2)&&v[st2.x][st2.y]==0&&a[st2.x][st2.y]!='X')
            {
     			v[st2.x][st2.y]=1;
                s[st2.x][st2.y]=s[st1.x][st1.y]+1;
                //printf("-%d %d %d-\n",st2.x,st2.y,s[st2.x][st2.y]);
                qq.push(st2);
            }
        }
    }	
	return s[pp.x][pp.y];
   // printf("(%d %d %d %c)\n",st1.x,st1.y,s[st1.x][st1.y],c);
   
}
int main()
{
    int  i,j,k,m,l;
    while(~scanf("%d %d %d",&h,&w,&n))
    {    
    	getchar();
        memset(v,0,sizeof(v));
        memset(s,0,sizeof(s));
        for(i=0;i<h;i++)
        {
            scanf("%s",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            b[i]=i+1+'0';
            //printf("%c\n",b[i]);
        }
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                if(a[i][j]=='S')
                {
                    pp.x=i;
                    pp.y=j;
                }
            }
        }
        //printf("%d %d\n",sx,sy);
        int sum=0;
		for(i=0;i<n;i++)
        { 
            sum+=bfs(b[i]);
            //printf("[%d]\n",sum);
        }
        printf("%d\n",sum);
    }
    return 0;
}