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

using namespace std;

char s[1005][1005]= {'\0'};

int n, m, num;
int a[10][2]= {0};

int mov1[4]= {-1,0,1,0};
int mov2[4]= {0,1,0,-1};

struct node
{
    int x;
    int y;
    int ans;
    node()
    {
        x=0;
        y=0;
        ans=0;
    }
    node(int a,int b,int c)
    {
        x=a;
        y=b;
        ans=c;
    }
};

queue<node>q;

node t;

void bfs(node temp,int type)
{
    if(type>num)return;
    if(a[type][0]==temp.x&&a[type][1]==temp.y)
    {
        //printf("*****\n");
            //printf("type is %d\n",type);
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    if(s[i][j]=='*')
                        s[i][j]='.';
            while(!q.empty())q.pop();
            bfs(temp,type+1);
    }
    else
    {
        q.push(temp);
        while(!q.empty())
        {
            t=q.front();
            q.pop();
            if(a[type][0]==t.x&&a[type][1]==t.y)
            {
                bfs(t,type);
                break;
            }
            s[t.x][t.y]='*';
            for(int i=0;i<4;i++)
            {
                int tx=t.x+mov1[i];
                int ty=t.y+mov2[i];
                if(tx<1||ty<1||tx>n||ty>m||s[tx][ty]=='X'||s[tx][ty]=='*')continue;
                node p(tx,ty,t.ans+1);
                s[tx][ty]='*';
                //printf("jiezhi %d %d %d\n",tx,ty,t.ans+1);
                q.push(p);
            }
        }

    }
}

int main()
{
    //freopen("in.in","r",stdin);
    while(scanf("%d%d%d",&n,&m,&num)!=EOF)
    {
        char c=getchar();
        memset(s,'\0',sizeof(s));
        memset(a,0,sizeof(a));
        int x=0, y=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%c",&s[i][j]);
                if(s[i][j]=='S')
                {
                    x=i;
                    y=j;
                }
                if(s[i][j]>='0'&&s[i][j]<='9')
                {
                    a[s[i][j]-'0'][0]=i;
                    a[s[i][j]-'0'][1]=j;
                }
            }
            c=getchar();
        }
        //for(int i=1;i<=num;i++)
        //    printf("%d %d\n",a[i][0],a[i][1]);
        while(!q.empty())q.pop();
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("%c",s[i][j]);
            printf("\n");
        }*/
        node temp;
        temp.x=x;
        temp.y=y;
        bfs(temp,1);
        printf("%d\n",t.ans);
    }
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); ++i)
 
typedef pair<int, int> XY;
typedef pair<int, XY > P;

int H, W, N;
char m[1001][1001];
char checked[1001][1001];
void dfs(int i, int j) {
    char c = m[i][j];
    m[i][j] = '.';
    if(j+1<W && m[i][j+1]==c) dfs(i, j+1);
    if(j>0 && m[i][j-1]==c) dfs(i, j-1);
    if(i+1<H && m[i+1][j]==c) dfs(i+1, j);
    if(i>0 && m[i-1][j]==c) dfs(i-1, j);
}
int main() {
    cin >> H >> W >> N;
    int x, y;
    rep(i, H) {
        rep(j, W) {
            cin >> m[i][j];
            if(m[i][j]=='S') {
                x = j;
                y = i;
            }
        }
    }

    int HP = 1;
    int time = 0;
    while(HP <= N) {
        rep(i, H) {
            rep(j, W) {
                checked[i][j] = 0;
            }
        }
        queue<P> q;
        q.push(P(time, XY(x, y)));
        while(q.size()>0) {
            P p = q.front(); q.pop();
            int cx = p.second.first;
            int cy = p.second.second;
            checked[cy][cx] = 1;
            if(m[cy][cx]=='0'+HP) {
                x = cx;
                y = cy;
                time = p.first;
                HP++;
                break;
            } else {
                if(cy>0 && m[cy-1][cx]!='X' && checked[cy-1][cx]==0) q.push(P(p.first+1, XY(cx, cy-1)));
                if(cx>0 && m[cy][cx-1]!='X' && checked[cy][cx-1]==0) q.push(P(p.first+1, XY(cx-1, cy)));
                if(cy<H-1 && m[cy+1][cx]!='X' && checked[cy+1][cx]==0) q.push(P(p.first+1, XY(cx, cy+1)));
                if(cx<W-1 && m[cy][cx+1]!='X' && checked[cy][cx+1]==0) q.push(P(p.first+1, XY(cx+1, cy)));
            }
        }
    }
    cout << time << endl;
    return 0;
}

C++: # include <stdio.h>
# include <string.h>
# include <queue>
# include <algorithm>
using namespace std ;

typedef struct Node
{
	int x ;
	int y ;
}NODE ;


int w, h, m ;
NODE N, NN, NNN ;
queue <NODE> que ;
int flag[1010][1010] ;
char route[1010][1010] ;
int direction[4][2] = {0, 1, 0, -1, 1, 0, -1, 0} ;

bool bounds(NODE p)
{
	if(p.x < 0 || p.y < 0 || p.x >= w || p.y >= h)
		return false ;
	return true ;
}

void bfs(char c)
{
	memset(flag, 0, sizeof(flag)) ;
	flag[N.x][N.y] = 1 ;
	que.push(N) ;
	while(!que.empty())
	{
		NN = que.front() ;
		que.pop() ;
		for(int i = 0; i < 4; i ++)
		{
			NNN.x = NN.x + direction[i][0] ;
			NNN.y = NN.y + direction[i][1] ;
			if(bounds(NNN) && route[NNN.x][NNN.y] != 'X' && flag[NNN.x][NNN.y] == 0)
			{ 
				flag[NNN.x][NNN.y] = flag[NN.x][NN.y] + 1 ;
				que.push(NNN) ;
				if(route[NNN.x][NNN.y] == c)
					N = NNN ;
			}
			
		}
	}
}
int main ()
{
	while(scanf("%d%d%d%*c", &w, &h, &m) != EOF)
	{
		for(int i = 0; i < w; i ++)
			gets(route[i]) ;
		for(int i = 0; i < w; i ++)
		{
			for(int j = 0; j < h; j ++)
			{
				if(route[i][j] == 'S')
				{
					N.x = i ;
					N.y = j ;
				}
			}
		}
		int sum = 0 ;
		for(int i = 1; i <= m; i ++)
		{
			bfs(i + '0') ;
			sum += flag[N.x][N.y] - 1 ;	
		}
		printf("%d\n", sum) ;
	}

	return 0 ;
}