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<iomanip>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<complex>
#include<set>
#include<map>
#include<list>
#include<vector>
#include<deque>
using namespace std;
typedef long long ll;
typedef vector<int>vec;
typedef vector<vec>mat;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const double eps = 1e-7;
int dirX[4] = { 1,0,-1,0 };
int dirY[4] = { 0,1,0,-1 };
struct point {
	int x; int y; 
	point() { x = y =0; }
	point(int X, int Y) { x = X; y = Y; }
	point(const point &p) { x = p.x; y = p.y;  }
	bool operator==(const point&C) {
		return{x==C.x&&y==C.y};
	}
};
struct cheese :public point {
	int hard;
	cheese() { x = y = hard = 0; }
	cheese(int X, int Y, int H) { x = X; y = Y; hard = H; }
	bool operator<(const cheese&C) {
		return hard < C.hard;
	}
};
int H, W, N;
bool a[1001][1001]; bool v[1001][1001];//here???
vector<cheese>goal;
bool isFound=0;;
void dfs(int t,point P,int curD,int maxD){
	if(v[P.x][P.y])return;
	v[P.x][P.y]=1;
	if(P==goal[t+1]){
		isFound=1;
		return;
	}
	int heu=0;
	heu=abs(goal[t+1].x-P.x)+abs(goal[t+1].y-P.y);
	if(curD<maxD&&(curD+heu<=maxD)){
		for(int i=0;i<4;i++){
			int tx = P.x + dirX[i];int ty = P.y + dirY[i];
			if (tx >= 1 && tx <= H&&ty >= 1 && ty <= W&&a[tx][ty]==0&&v[tx][ty] == 0)
						dfs(t,point(tx,ty),curD+1,maxD);
		}
	}
	v[P.x][P.y]=0;
	return;
}
int main() {
	//ifstream ifs;
	//ifs.open("D:\\documents\\programDatas\\AOJ0558.txt");
	cin >> H >> W >> N;
	memset(a, 0, sizeof(a)); memset(v, 0, sizeof(v));
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char temp;
			cin>>temp;
			if (temp == 'S')goal.push_back(cheese(i, j, 0));
			else if (temp >= '1'&&temp <= '9')goal.push_back(cheese(i, j, (int)(temp - 48)));
			else if (temp == '.')a[i][j] = 0;
			else if (temp == 'X')a[i][j] = 1;
		}
	}
	sort(goal.begin(), goal.end());
	//for debug
	/*for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cout << setw(3) << a[i][j];
		}
		cout << endl;
	}
	for (int i = 0; i <= N; i++) {
		cout << goal[i].x << " " << goal[i].y << " " << goal[i].hard << " " << endl;
	}
	cout << endl;
	*/
	//IDS
	int total = 0;//total steps
	for (int t = 0; t < N; t++) {//x for start point and x+1 for end point
		int maxD=abs(goal[t+1].x-goal[t].x)+abs(goal[t+1].y-goal[t].y);
		//heustic optimization here
		while(1){
			dfs(t,goal[t],0,maxD);
			if(isFound){
				isFound=0;//reset
				break;
			}
			maxD++;
		}
		total+=maxD;
		memset(v,0,sizeof(v));
	}
	cout << total << endl;
	return 0;
}

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

typedef pair<int,int> P;
struct State{
	int x, y, cnt;
};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
	int w, h, n;
	string m[1001];
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> m[y];
	}
	
	struct State cheese[11];
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			char c = m[y][x];
			if( c == 'S' ){
				cheese[0].x = x;
				cheese[0].y = y;
				cheese[0].cnt = 0;
			}
			if( c >= '1' && c <= '9' ){
				cheese[ c - '0' ].x = x;
				cheese[ c - '0' ].y = y;
				cheese[ c - '0' ].cnt = 0;
			}
		}
	}
	int ans = 0;
	for(int i=1 ; i <= n ; i++ ){
		struct State sp = cheese[i-1];
		struct State gp = cheese[i];
		map<P,bool> memo;
		P p_( sp.x , sp.y );
		memo[p_] = true;
		
		queue<struct State> q;
		q.push( sp );
		while( !q.empty() ){
			struct State p = q.front();
			q.pop();
			if( p.x == gp.x && p.y == gp.y ){
				ans += p.cnt;
				break;
			}
			P p_( p.x , p.y );
			memo[p_] = true;
			
			for(int i=0 ; i < 4 ; i++ ){
				int mx = p.x + dx[i];
				int my = p.y + dy[i];
				if( mx < 0 || my < 0 || mx >= w || my >> h ) continue;
				if( m[my][mx] != 'X' ){
					struct State next;
					next.x = mx;
					next.y = my;
					next.cnt = p.cnt + 1;
					P p_( mx , my );
					if( memo[p_] != true ){
						q.push( next );
					}
				}
			}
		}
	}
	cout << ans << endl;
}

C++: #include <iostream>
#include <cstdio>
#include <limits>
#include <queue>

using namespace std;

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

typedef pair<int, int> P;

int H,W,N;
char field[MAX_H][MAX_W];
int dist[MAX_H][MAX_W];

queue<P> que;

using limits = std::numeric_limits<int>;


void getStatus(int y, int x, int min_dist){
    for(int i = 0; i< H; i++) {
        for (int j = 0; j < W; j++) {
            if( i == y && j == x){
                cout << "$";
            }else {
                cout << field[i][j];
            }
        }
        cout << endl;
    }
    cout << "-------------min_dist:" << min_dist << endl;
}


int bfs(int goal){

    int gx,gy;

    while( que.size()){
        P p = que.front(); que.pop();
        int a = p.first;
        int b  = p.second;

        if( atoi(&field[p.first][p.second]) == goal ) { gy = p.first; gx = p.second; break; }

        int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

        for(int i=0; i< 4; i++){

            int ny = p.first + dy[i],
                nx = p.second+ dx[i];

            if( 0 <= nx
                && nx < W
                && 0<= ny
                && ny < H
                && field[ny][nx] != 'X'
                && dist[ny][nx] ==  limits::infinity() ){

                que.push(P(ny,nx) );
                dist[ny][nx] = dist[p.first][p.second] + 1;

            }
        }
       // getStatus(p.first,p.second,dist[p.first][p.second]);
    }

    return dist[gy][gx];
}


void init_dist(){
    for(int i=0; i< H; i++){
        for(int j=0; j<W; j++){
            dist[i][j] = limits::infinity();
        }
    }
    queue<P>().swap(que);

}


void solve(){
    int sum = 0;
    for(int i = 0; i< H; i++){
        for(int j = 0; j< W; j++){

            if( field[i][j] == 'S'){
                init_dist();
                que.push(P(i,j));
                dist[i][j] = 0;
                sum += bfs(1);
            }

            for(int k = 1; k<N; k++){
                if( atoi(&field[i][j]) == k ) {
                    init_dist();
                    que.push(P(i,j));
                    dist[i][j] = 0;
                    sum+=bfs(k+1);
                }

            }
        }
    }

    cout << sum << endl;

}



int main() {

    while(1){

        string line;
        cin >> H >> W >> N;cin.ignore();
        if( H == 0 && W == 0 ){
            break;
        }


        for(int i = 0; i< H; i++){
            getline(cin,line);
            for(int j = 0; j< W; j++){
                field[i][j] = line[j];
            }
        }

        solve();

    }

    return 0;
}

/*
10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......
 */