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++: #pragma once

#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
string S[1001];
long result=0;
int H,W,N;
long mintime[1000][1000];
queue<int> qx,qy,time;
int sx,sy,gx,gy;
int step = 0;

int main(){
	scanf("%d%d%d",&H,&W,&N);

	for(int i=0;i<H;i++){
		cin>>S[i];
		for(int j=0;j<W;j++){
			mintime[i][j]=1000000;
			if(S[i][j]=='S'){
				sx=j;
				sy=i;
				qx.push(j);
				qy.push(i);
				time.push(0);
			}

			if(S[i][j]-'0'==N){
				gx=j;
				gy=i;
			}

		}
	}



for(int acc=0;acc<N;acc++){
	step++;
	while(step<=N){
		
		if(qx.front()>0){
		if(time.front()<mintime[qy.front()][qx.front()-1]-1  && S[qy.front()][qx.front()-1] !='X'){
			if(S[qy.front()][qx.front()-1]-'0' ==step){
			result += time.front()+1;
			sx=qx.front()-1;
			sy=qy.front();
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				time.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			time.push(0);
			break;
		}
				qx.push(qx.front()-1);
				qy.push(qy.front());
				time.push(time.front()+1);
				mintime[qy.front()][qx.front()-1]=time.front()+1;
		}

	}
		//

	if( qx.front()<W-1 ){
		if(time.front()<mintime[qy.front()][qx.front()+1]-1 && S[qy.front()][qx.front()+1] !='X'){

		if(S[qy.front()][qx.front()+1]-'0' ==step){
			result += time.front()+1;
			sx=qx.front()+1;
			sy=qy.front();
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				time.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			time.push(0);
			break;
		}

				qx.push(qx.front()+1);
				qy.push(qy.front());
				time.push(time.front()+1);
				mintime[qy.front()][qx.front()+1]=time.front()+1;
		}
	}

		//

	if( qy.front()>0){
		if(time.front()<mintime[qy.front()-1][qx.front()]-1  && S[qy.front()-1][qx.front()] !='X'){

			if(S[qy.front()-1][qx.front()]-'0' ==step){
			result += time.front()+1;
			sx=qx.front();
			sy=qy.front()-1;
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				time.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			time.push(0);
			break;
		}

				qx.push(qx.front());
				qy.push(qy.front()-1);
				time.push(time.front()+1);
				mintime[qy.front()-1][qx.front()]=time.front()+1;
		}
	}

		//

	if(qy.front()<H-1){
		if(time.front()<mintime[qy.front()+1][qx.front()]-1  && S[qy.front()+1][qx.front()] !='X'){

				if(S[qy.front()+1][qx.front()]-'0' ==step){
			result += time.front()+1;
			sx=qx.front();
			sy=qy.front()+1;
			while(qx.empty()== false){
				qx.pop();
				qy.pop();
				time.pop();
			}
			
			qx.push(sx);
			qy.push(sy);
			time.push(0);
			break;
		}

				qx.push(qx.front());
				qy.push(qy.front()+1);
				time.push(time.front()+1);
				mintime[qy.front()+1][qx.front()]=time.front()+1;
		}
	}


		qx.pop();
		qy.pop();
		time.pop();
	



	}

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			mintime[i][j]=1000000;
		}
	}

}

printf("%d\n",result);
return 0;

}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
using namespace std;
const int N=1000;
char maze[N][N];
int h,w,n;
int sx,sy,gx,gy;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int d[N][N];
const int INF=INT_MAX;
int ans;
struct node
{
    node(int xx=0,int yy=0,int tt=0,char ss=0):x(xx),y(yy),t(tt),s(ss){}
    int x;
    int y;
    int t;
    char s;
};
bool read()
{
    memset(maze,0,sizeof(maze));
    scanf("%d%d%d",&h,&w,&n);
    getchar();
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            scanf("%c",&maze[i][j]);
            if(maze[i][j]=='S') sx=j,sy=i;
            if(maze[i][j]=='0'+n) gy=i,gx=j;
        }
        getchar();
    }
    for(int i=0;i<h;i++)
       for(int j=0;j<w;j++) d[i][j]=INF;
    return 1;
}
void show()
{
    //printf("h:%d w:%d\n",h,w);
    //printf("maze[%d][%d]=%d\n",0,2,maze[0][2]);
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(d[i][j]!=INF) printf("%d ",d[i][j]);
            else printf("- ");
        }
        printf("\n");
    }
    //printf("sy:%d sx:%d\n",sy,sx);
}
void init(int h,int w)
{
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++) d[i][j]=INF;
}
int bfs()
{
   queue<node> que;
   que.push(node(sx,sy,0,'1'));
   d[sy][sx]=0;
   while(!que.empty())
   {

       node t=que.front();que.pop();
       //printf("%c\n",t.s);
       for(int i=0;i<4;i++)
       {
           int nx=t.x+dir[i][0];
           int ny=t.y+dir[i][1];
           if(0<=nx&&nx<w&&0<=ny&&ny<h&&d[ny][nx]==INF&&maze[ny][nx]!='X'/*(maze[ny][nx]=='.'||maze[ny][nx]==t.s)*/)
           {
               if(maze[ny][nx]=='0'+n&&maze[ny][nx]==t.s)
               {
                   //printf("%c in return",maze[ny][nx]);
                   return ans+=d[t.y][t.x]+1;
               }
               if(maze[ny][nx]==t.s)
               {
                   //printf("%c d\n",maze[ny][nx]);
                   maze[ny][nx]='.';
                    d[ny][nx]=d[t.y][t.x]+1;
                    ans+=d[ny][nx];
                    //show();
                    while(!que.empty()) que.pop();
                    init(h,w);
                    d[ny][nx]=0;
                   que.push(node(nx,ny,0,t.s+1));
                   break;
               }
               else
               {
                   que.push(node(nx,ny,0,t.s));
                    d[ny][nx]=d[t.y][t.x]+1;
               }
           }
       }
       //int size=que.size();
        //printf("size:%d\n",size);
   }
   return 1/*d[gy][gx]*/;
}
int main()
{
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        getchar();
        memset(maze,0,sizeof(maze));
        ans=0;
        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                scanf("%c",&maze[i][j]);
                if(maze[i][j]=='S') sx=j,sy=i;
                if(maze[i][j]=='0'+n) gy=i,gx=j;
            }
            getchar();
        }
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++) d[i][j]=INF;
        bfs();
        printf("%d\n",ans);
    }
    return 0;
}