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++: /*
P135
AOJ 0558 Cheese
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
*/


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <functional>
#include <string.h>
using namespace std;
/*
int W, H;
char board[110][110];
int a[10];
bool read()
{
    for(int i=0; i<10; ++i)
        scanf("%d", a+i);
}

bool isVisited[110][110];
int step;

void dfs(int x, int y, char c){
    if(x<0 || x>=H || y<0 || y>=W) return;
    if(board[x][y]!=c) return;
    if(isVisited[x][y]) return;
    isVisited[x][y] = true;
    dfs(x+1, y, c);
    dfs(x-1, y, c);
    dfs(x, y+1, c);
    dfs(x, y-1, c);
}



void solve1()
{
    int x1=0, x2=0;
    bool ans = true;
    for(int i=0; i<10; ++i)
    {
        if(x1 < x2) swap(x1, x2);
        if(x1 < a[i]) x1 = a[i];
        else if(x2 < a[i]) x2 = a[i];
        else {ans = false; break;}
    }
    if(ans) printf("YES\n");
    else printf("NO");
}



vector<int> L_bucket;
vector<int> R_bucket;

bool dfs2(int d){
    if(d == 10) return true;
    bool flag;
    if(L_bucket.size() == 0 || L_bucket.back() < a[d]){
        L_bucket.push_back(a[d]);
        flag = dfs2(d+1);
        L_bucket.pop_back();
    }
    if(flag) return true;
    if(R_bucket.size() == 0 || R_bucket.back() < a[d]){
        R_bucket.push_back((a[d]));
        flag = dfs2(d+1);
        R_bucket.pop_back();
    }
    if(flag) return true;
    return false;

}

void solve2()
{
    if(dfs2(0))
        printf("YES\n");
    else printf("NO\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        read();
        solve2();
    }
}
*/


const int MAXN = 1010;
const int inf = 1<<30;
char board[MAXN][MAXN];
int H, W, N;
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {1, 0, -1, 0, 0};

typedef pair<int,int> PAIR;

PAIR goal[10];

bool check(int x, int y)
{
    return (x>=0&&x<H && y>=0 && y<W);
}

void read()
{
    scanf("%d%d%d", &H, &W, &N);
    for(int i=0; i<H; ++i){
        scanf("%s", board[i]);
        for(int j=0; j<W; ++j){
            if(board[i][j] == 'S')
                goal[0] = make_pair(i, j);
            if(board[i][j]>='0' && board[i][j] <='9'){
                int x = board[i][j] - '0';
                goal[x] = make_pair(i, j);
            }
        }
    }
}

int step[MAXN][MAXN];

int bfs(const PAIR& st, const PAIR& ed){
    queue<PAIR> q;
    q.push(st);
    memset(step, -1, sizeof(step));
    step[st.first][st.second] = 0;

    while(!q.empty()){
        PAIR cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        int stp = step[x][y];

        for(int d=0; d<4; ++d){
            int cx = x + dx[d], cy = y + dy[d];
            if(check(cx, cy)){
                if(board[cx][cy]!='X' && step[cx][cy] == -1){
                    if(cx == ed.first && cy == ed.second) return stp + 1;
                    step[cx][cy] = stp + 1;
                    q.push(make_pair(cx, cy));
                }
            }
        }
    }
}



void solve()
{
    int ans = 0;
    for(int i=0; i<N; ++i){
        ans += bfs(goal[i], goal[i+1]);
    }
    printf("%d\n", ans);
}

int main()
{
    read();
    solve();
}

C++: #include<iostream>
#include<cstring>
#include<queue>
using namespace std ;
struct ST
{
	int x ;
	int y ;
	int cnt = 0 ;
} ;
bool came[ 1000 ][ 1000 ] = {{ 0 }} ;
char map[ 1000 ][ 1000 ] ;
int main()
{
	ST m ,s ;
	queue< ST > que ;
	int n ;
	int w ,h ;
	int kyori = 0 ;
	int mx[ 4 ] = { 0 ,0 ,1 ,-1 } ;
	int my[ 4 ] = { 1 ,-1 ,0 ,0 } ;
	cin >> h >> w >> n ;
	int cheesuu = n ;
	int fx ,fy ;
	char c ;
	bool a = true ;	
	for( int i = 0 ; i < h ; i++ )
	{
		cin >> map[ i ] ;
		for( int j = 0 ; j < w ; j++ && a )
		{
			if( map[ i ][ j ] == 'S' )
			{
				m.x = j ;
				m.y = i ;
				a = false ;
			}
		}
	}
	que.push( m ) ;
	while( n )
	{
		n-- ;
		c = ( cheesuu - n ) + 48 ;
		while( !que.empty() )
		{
			m = que.front() ;
			que.pop() ;
			came[ m.y ][ m.x ] = 1 ;
			if( map[ m.y ][ m.x ] == c )
			{
				kyori += m.cnt ;
				while( ! que.empty() )
				{
					que.pop() ;
				}
				goto ONE_MORE ;
			}
			for( int i = 0 ; i < 4 ; i++ )
			{
				if( m.x + mx[ i ] > -1 && m.x + mx[ i ] < w && m.y +  my[ i ] > -1 && m.y + my[ i ] < h )
				{
					s = m ;
					s.x += mx[ i ] ;
					s.y += my[ i ] ;
					s.cnt++ ;
					if( map[ s.y ][ s.x ] != 'X' && came[ s.y ][ s.x ] == 0 )
					{
						que.push( s ) ;
					}
				}
			}
		}
		ONE_MORE :
		memset( came ,0 ,sizeof( came ) ) ;
		m.cnt = 0 ;
		que.push( m ) ;
	}
	cout << kyori << endl ;
	return 0 ;
}

C++: #include <cstdio>
#include <map>
#include <queue>
#include <string>

using namespace std;

const int INF = 100000000;
const int MAX_H = 1000;
const int MAX_W = 1000;
const int MAX_N = 9;

int H, W, N;
char field[MAX_H][MAX_W];
int d[MAX_H][MAX_W]; // ?????????????????\??´?????§??????????????°, 1~N??§?????????????????§????????°??????+1
int step[MAX_N+1]; // ?????????????????\??´?????§??????????????°, 1~N??§?????????????????§????????°??????+1
int sx, sy, gx, gy;
int power = 1; // ??????????????????
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

typedef pair<int, int> P;

void put_i(int i) {
  printf("%d\n", i);
}
void put_c(char c) {
  printf("%c\n", c);
}
void put_s(string s){
  printf("%s\n", s.c_str());
}

void reset_d() {
  for (int i = 0; i < H; i++)
    for(int j = 0; j < W; j++) d[i][j] = INF;
}

int bfs(int sx, int sy, int c) {
  queue<P> que;
  reset_d();
  d[sx][sy] = c;
  que.push(P(sx, sy));
  while(que.size()) {
    P p = que.front(); que.pop();
    if (field[p.first][p.second] - '0' == N && step[N] != 0) break;
    for (int i = 0; i < 4; i++) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if ( 0 <= nx && nx <= H && 0 <= ny && ny <= W && field[nx][ny] != 'X' && d[nx][ny] == INF) {
        d[nx][ny] = d[p.first][p.second] + 1;
        que.push(P(nx, ny));
        if (field[nx][ny] - '0' == power) {
          step[power] = d[nx][ny];
          power++;
          return bfs(nx, ny, d[nx][ny]);
        }
      }
    }
  }
  return step[N];
}

void solve(int sx, int sy) {
  int res = bfs(sx, sy, 0);
  printf("%d\n", res);
}


int main() {
  scanf("%d %d %d", &H, &W, &N);
  for (int i = 0; i < H; i++) {
    scanf("%s", field[i]);
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (field[i][j] == 'S') {
        sx = i;
        sy = j;
      }
      if (field[i][j] == 'G') {
        gx = i;
        gy = j;
      }
    }
  }
  solve(sx, sy);
  return 0;
}