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<vector>
#include<map>
#include<utility>
#include<queue>
using namespace std;
 
char f[1001][1001];
int d[1001][1001];
int h , w , n , x , y , ans;
typedef pair<int,int> P;
int dx[] = {1,0,-1,0} , dy[] = {0,-1,0,1};
 
int bfs(int to){
  for( int i = 0 ; i < h ; i++)
    for( int j = 0 ; j < w ; j++)
      d[i][j] = 0;
  queue<P> q;
  q.push(make_pair(x,y));
  d[y][x]=1;
  while(!q.empty()){
    P p = q.front();
    q.pop();
    if(f[p.second][p.first] - '0' == to){
      x = p.first;
      y = p.second;
      break;
    }
    for(int i = 0 ; i < 4 ; i ++){
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if(nx >= 0 && nx < w && ny < h && ny >=0 && d[ny][nx] == 0 && f[ny][nx] != 'X'){
        d[ny][nx] = d[p.second][p.first] + 1;
        q.push(make_pair(nx,ny));
        
      }
    }
  }
  return d[y][x] - 1;
} 
 
int main(){
  while(cin >> h >> w >> n){
    ans = 0;
    for( int i = 0 ; i < h ; i++)
      cin >> f[i];
    for( int i = 0 ; i < h ; i++)
      { 
      for( int j = 0 ; j < w ; j++)
        {
          if(f[i][j]=='S')
            {
          x = j;
          y = i;
            }
        }       
      }
    for( int i = 1 ; i <= n ; i++ ) ans +=bfs(i) ; 
    cout << ans << endl;
  }     
}

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

using namespace std;

struct State {
    int step;
    int x;
    int y;

    State() {
        step = 0;
        x = 0;
        y = 0;
    }

    State(int step, int x, int y): step(step), x(x), y(y) {}
};

const int MAX_N = 1000;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};
char board[MAX_N][MAX_N];
int W, H, N;
State pos[10];

void init();
void input();
void solve();
int bfs(State from, State to);
void findPossition();

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    init();
    input();
    solve();
    return 0;
}

void init() {
}

void input() {
    scanf("%d %d %d", &H, &W, &N);

    for(int i = 0; i < H; i++) {
        scanf("%s", board[i]);
    }
}


void solve() {
    int moves = 0;
    findPossition();

    for(int i = 0; i < N; i++) {
        moves += bfs(pos[i], pos[i + 1]);
    }

    printf("%d\n", moves);
}

int bfs(State from, State to) {
    queue<State> que;
    bool visit[H][W];
    State cur = from;

    for(int i = 0; i < H; i++) {
        memset(visit[i], false, sizeof(visit[i]));
    }

    que.push(cur);

    while(!que.empty()) {
        cur = que.front();
        que.pop();

        if(visit[cur.x][cur.y]) {
            continue;
        }
        
        visit[cur.x][cur.y] = true;

        if(cur.x == to.x && cur.y == to.y) {
            break;
        }

        for(int i = 0; i < 4; i++) {
            int x = cur.x + dir[i][0];
            int y = cur.y + dir[i][1];

            if(x < 0 || x >= H || y < 0 || y >= W || visit[x][y] || 'X' == board[x][y]) {
                continue;
            }

            que.push(State(cur.step + 1, x, y));
        }
    }

    return cur.step;
}

void findPossition() {
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            int c = board[i][j];

            if('S' == c) {
                pos[0] = State(0, i, j);
            }

            if(isdigit(c)) {
                pos[c - '0'] = State(0, i, j);
            }
        }
    }
}

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

struct data_Node{
	int x,y,time;
};

char dataSet[1001][1001];
bool visited[1001][1001];
int H,W,N;

int total_time,total_storage,cnt_storage,cnt_time;
int start_row,start_cell;
int control_x[4] = {0,0,-1,1};
int control_y[4] = {-1,1,0,0};



void Find_Short_Path (int x,int y)
{
	memset(visited,false,sizeof(visited));
	data_Node temp_data;
	temp_data.x = x;
	temp_data.y = y;
	temp_data.time = 0;
	visited[x][y] = true;
	cnt_time = 0;
	queue<data_Node> temp_queue;
	temp_queue.push(temp_data);
	while (temp_queue.empty() != true)
	{
		data_Node u = temp_queue.front();
		temp_queue.pop();
		if ((int)(dataSet[u.x][u.y] - '0') == total_storage)
		{
			start_row = u.x;
			start_cell = u.y;
			cnt_time = u.time;
			break;
		}
		for (int i=0;i<4;i++)
		{
			int dx = u.x + control_x[i];
			int dy = u.y + control_y[i];
			if (dataSet[dx][dy] != 'X' && dx >= 0 && dx< H && dy >= 0 && dy < W)
			{
				data_Node v;
				v.x = dx;
				v.y = dy;	
				v.time = u.time + 1;//此?有坑
				if (visited[dx][dy] == false)
				{
					visited[dx][dy] = true;
					temp_queue.push(v);
				}
			}
		}
	}
}

int main ()
{

		cin>>H>>W>>N;
		memset(dataSet,'X',sizeof(dataSet));
		total_storage = 1;
		total_time = 0;
		for (int i=0;i<H;i++)
		{
			for (int j=0;j<W;j++)
			{
				cin>>dataSet[i][j];
				if (dataSet[i][j] == 'S')
				{
					start_row = i;
					start_cell = j;
				}
			}
		}
		int ans = 0;
		for (int i=1;i<=N;i++)
		{
			total_storage = i;
			Find_Short_Path(start_row,start_cell);
			ans += cnt_time;
		}
		cout<<ans<<endl;

	return 0;
}

C++: #include <iostream>
#include <queue>
#include <string.h>
using namespace std;
typedef pair<int, int> P;
int sx,sy,H,W,N;
char map1[1002][1002];
int step[1002][1002];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
void find1(int g){
for(int i = 0; i < W; i++)
    for(int k = 0; k < H; k++)
        if(map1[i][k] == 'S' || map1[i][k] == (g+48)){
        if(map1[i][k] == 'S') map1[i][k] ='.';
        sx = i; sy = k;
        return ;
    }
}

int bfs(int n)
{
    memset(step,-1,sizeof(step));
    queue <P> que;
    que.push(P (sx,sy));
    step[sx][sy] = 0;
    while(que.size()){
        int x = que.front().first, y = que.front().second;
        que.pop();
        for(int i = 0; i < 4; i++){
            int xn = x + dx[i], yn = y + dy[i];
            if(xn >= 0 && xn < W && yn >= 0 && yn < H && map1[xn][yn] != 'X' && step[xn][yn] == -1)
                {
                    step[xn][yn] = step[x][y] + 1;
                    if(map1[xn][yn] == (n+48))
                        {
                            return step[xn][yn];
                        }
                    que.push(P(xn, yn));
                }
        }
    }
return 0;
}

int main()
{
    cin >> W >> H >> N;
    for(int i = 0; i < W; i++)
        for(int k = 0; k < H; k++)
        cin >> map1[i][k];
    int step = 0;
    find1(0);
    step += bfs(1);
    for(int i = 1; i < N; i++)
    {

        find1(i);
        step += bfs(i+1);
    }
    cout << step << endl;
    return 0;
}