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<utility>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 999999;
const int max_n = 1010;
typedef pair<int, int> P;


char grp[max_n][max_n];
int d[max_n][max_n];
int m, n, k;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
	
	
	int bfs(P, P);
	P search(int );
	
	cin >> m >> n >> k;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			char c;
			cin >> c;
			grp[i][j] = c;		
		}
	}
	
	P prev = search(0);
	int total = 0;
	for(int i = 1; i <= k; i++){
		P next = search(i);
		total += bfs(prev, next);
		prev = next;
	}
	
	cout << total << endl; 
	
	return 0;
} 

P search(int i){
	char c;
	if(i == 0)
		c = 'S';
	else
		c = i + '0';
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(grp[i][j] == c){
				P p(i, j);
				return p;
			}
		}
	}
	// 找不到的情况 
}

int bfs(P p1, P p2){
	fill(d[0], d[0] + max_n * max_n, inf);
	d[p1.first][p1.second] = 0;
	queue<P> qu;
	qu.push(p1);
	while(!qu.empty()){
		P tp = qu.front();
		if(tp == p2) break;
		qu.pop();
		for(int i = 0; i < 4; i++){
			int nx = tp.first + dx[i];
			int ny = tp.second + dy[i];
			if(nx >= 0 && ny >= 0 && nx < m && ny < n){
				if(grp[nx][ny] != 'X' && d[nx][ny] == inf){
					d[nx][ny] = d[tp.first][tp.second] + 1;
					P np(nx, ny);
					qu.push(np); 
				}
			}
		}
	}
	return d[p2.first][p2.second];
}

C++: #include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define MAX_N 1002
using namespace std;
struct node{int x,y;};
char _map[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int ox[]={0,0,1,-1};
int oy[]={1,-1,0,0};
int S_x,S_y;
int h,w,cnt;

node make_node(int x,int y){
	node t;
	t.x=x,t.y=y;
	return t;
}
void solve(){
	queue<node> que;
	int step=0;
	
	for(int i=1;i<=cnt;i++){
		que.push(make_node(S_x,S_y));
		_map[S_x][S_y]='.';
		memset(dp,-1,sizeof(dp));
		dp[S_x][S_y]=step;
		while(!que.empty()){
			node t=que.front();que.pop();
			if(_map[t.x][t.y]=='0'+i){
				step=dp[t.x][t.y];
				S_x=t.x,S_y=t.y;
				break;
			}
			for(int j=0;j<4;j++){
				int x=t.x+ox[j];
				int y=t.y+oy[j];
				if(0<=x&&x<h&&0<=y&&y<w&&_map[x][y]!='X'&&dp[x][y]==-1){
					que.push(make_node(x,y));
					dp[x][y]=dp[t.x][t.y]+1;
				}
			}
		}
		while(!que.empty()) que.pop();
	}
	
	printf("%d\n",step);
}

int main()
{
	while(scanf("%d%d%d",&h,&w,&cnt)!=EOF){
		for(int i=0;i<h;i++)
			scanf("%s",_map[i]);
		for(int j=0;j<h;j++)
			for(int k=0;k<w;k++)
				if(_map[j][k]=='S')
					S_x=j,S_y=k,j=h,k=w;
		solve();
	}
	return 0;
}

C++: #include <cstdio>
#include <queue>
#include <cctype>

using namespace std;

struct Position {
    int h, w, time, strength;
    Position (int h, int w, int t, int s): h(h), w(w), time(t), strength(s) {}
};

const int max_h = 1005;
const int max_w = 1005;
int g_h, g_w, g_max_strength, si, sj;
char mat[max_h][max_w];
char mat2[max_h][max_w];
int dh[] = {0, 1, 0, -1};
int dw[] = {1, 0, -1, 0};

int main() {
    scanf("%d%d%d", &g_h, &g_w, &g_max_strength);
    for (int i = 0; i < g_h; i++) {
        getchar();
        for (int j = 0; j < g_w; j++) {
            mat[i][j] = getchar();
            if (mat[i][j] == 'S') {
                si = i;
                sj = j;
            }
            if (mat[i][j] == 'X') {
                mat2[i][j] = 'X';
            } else {
                mat2[i][j] = '.';
            }
        }
    }
    queue<Position> q;
    q.push(Position(si, sj, 0, '0'));
    int result = -1;
    while (!q.empty()) {
        Position p = q.front();
        q.pop();
        char c = mat[p.h][p.w];
        if (isdigit(c)) {
            if (p.strength+1 == c) {
                if (p.strength+1 == g_max_strength+'0') {
                    result = p.time;
                    break;
                }
                p.strength++;
            }
        }
        mat2[p.h][p.w] = p.strength;
        for (int i = 0; i < 4; i++) {
            int w = p.w + dw[i];
            int h = p.h + dh[i];
            if (w >= 0 && w < g_w && h >= 0 && h < g_h &&
                    (mat2[h][w] == '.' || (isdigit(mat2[h][w]) && p.strength > mat2[h][w]))) {
                q.push(Position(h, w, p.time+1, p.strength));
            }
        }
    }
    printf("%d", result);
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector < vector<int> > hyou(1002, vector<int>(1002, -1));
int dh[] = {0, 1, 0, -1};
int dw[] = {1, 0, -1, 0};

typedef pair<int, int> P;
typedef pair<int, P> Q;

int search(int h, int w, int n) {
	int counter = 0;
	queue<Q> que;
	Q p;
	(p.second).first = h;
	(p.second).second = w;
	p.first = 0;
	que.push(p);
	while (!que.empty()) {
		Q pp = que.front();
		que.pop();
		if (hyou[(pp.second).first][(pp.second).second] == n) {
			counter = pp.first;
			break;
		} else {
			if (hyou[(pp.second).first][(pp.second).second] == 0) {
				hyou[(pp.second).first][(pp.second).second] = -2;
			}
			for (int i = 0; i < 4; i++) {
				if (hyou[(pp.second).first+dh[i]][(pp.second).second+dw[i]] != -1 && hyou[(pp.second).first+dh[i]][(pp.second).second+dw[i]] != -2) {
					Q pq;
					(pq.second).first = (pp.second).first+dh[i];
					(pq.second).second = (pp.second).second+dw[i];
					pq.first = pp.first+1;
					que.push(pq);
				}
			}
		}
	}
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			if (hyou[i][j] == -2) {
				hyou[i][j] = 0;
			}
		}
	}
	return counter;
}

int main() {
	int h, w, n;
	cin >> h >> w >> n;
	char c;
	int sh, sw;
	int data[10][2];
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> c;
			if (c == '.') {
				hyou[i][j] = 0;
			} else if (c == 'S') {
				hyou[i][j] = 0;
				sh = i;
				sw = j;
			} else if (c == 'X') {
				hyou[i][j] = -1;
			} else {
				int d = c - '0';
				hyou[i][j] = d;
				data[d-1][0] = i;
				data[d-1][1] = j;
			}
		}
	}
	int counter = 0;
	for (int i = 0; i < n; i++) {
		counter += search(sh, sw, i+1);
		sh = data[i][0];
		sw = data[i][1];
	}
	cout << counter << endl;
	return 0;
}