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 <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
char M[N][N];
bool mark[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sx, sy;
int total = 1;

void clear(queue<pair<int, int> > &q) {
    queue<pair<int, int> > empty;
    swap(empty, q);
}

void solve(int row, int col, int n) {
    memset(mark, 0, sizeof(mark));
    queue<pair<int, int> > que;
    que.push(pair<int, int>(sx, sy));
    int count = 1;
    while(que.size()) {
        int size = que.size();
        for(int k = 0; k < size; k++) {
            int nx = que.front().first;
            int ny = que.front().second;
            que.pop();
            for(int i = 0;i < 4; i++) {
                int x = nx + dx[i];
                int y = ny + dy[i];
                if(0 <= x && x < row && 0 <= y && y < col && M[x][y] != 'X' && !mark[x][y]) {
                    que.push(pair<int, int>(x, y));
                    mark[x][y] = true;
                    if(M[x][y] != '.' && M[x][y] - '0' == count) {
                        memset(mark, 0, sizeof(mark));
                        M[x][y] = '.';
                        count += 1;
                        if(count > n) {
                            printf("%d\n", total);
                            return ;
                        }
                        k = size;
                        clear(que);
                        que.push(pair<int, int>(x, y));
                        break;
                    }
                }
            }    
        }
        total += 1;
    }
    
}

int main() {
    int row, col, n;
    scanf("%d%d%d", &row, &col, &n);
    for(int i = 0; i < row; i++) {
        scanf("%s", M[i]);
        for(int j = 0; j < col; j++) {
            if(M[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
    solve(row, col, n);
}

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

#define P pair<int, int>
using namespace std;

const int INF=1<<30-1;

int h, w, n, gx, gy, times[1009][1009];
char c[1009][1009];

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

int bfs(char cur, int sx, int sy){
  int ret=0;
  queue<P> que;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      times[i][j] = INF;
    }
  }
  que.push(P(sy, sx));
  times[sy][sx] = 0;
  while(que.size()){
    P p = que.front();que.pop();
    for(int i=0;i<4;i++){
      int ny = p.first + dy[i];
      int nx = p.second + dx[i];
      if(0<=ny<=h-1&&0<=nx&&nx<=w-1&&c[ny][nx]!='X'&&times[ny][nx]==INF){
        times[ny][nx] = times[p.first][p.second]+1;
        if(c[ny][nx]==cur+1){
          ret = times[ny][nx];
          sx=nx, sy=ny;
        }
        que.push(P(ny, nx));
      }
    }
  }
  if(ret==0)return 0;
  else return ret + bfs(cur+1, sx, sy);
}

int main(){
  cin >> h >> w >> n;
  int sy,sx;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
      if(c[i][j]=='S'){
        sy=i;sx=j;
      }
    }
  }
  cout << bfs('0', sx, sy) << endl; 
}

C++: #include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<vector>
#include<cstring>
#define MAX 1100
#define INF 10000000

using namespace std;

 

int H, W, N;
int ans;
int d[MAX][MAX];
int gl[MAX][2];
char fac[MAX][MAX];
typedef pair <int, int> P;

void Bfs(int n){
	typedef pair <int, int> P;
	queue <P> que;
	int sx = gl[n][0];
	int sy = gl[n][1];
	int gx = gl[n+1][0];
	int gy = gl[n+1][1];
	int xi[4] = {-1,1,0,0};
	int yi[4] = {0,0,-1,1};
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			d[i][j] = INF;
		}		
			
	//将起点加入队列//记录距离
	que.push(P(sx, sy));
	d[sx][sy] = 0;	
	//队列不为空一直遍历
	while(!que.empty()){
		P p = que.front();
		que.pop();
		if(p.first==gx && p.second==gy)break;
		//四向遍历，加队列 
		for(int i=0; i<4; i++){
			int x = p.first + xi[i];
			int y = p.second + yi[i];
			//在迷宫内，可以经过，第一次经过 
			if(x>=0 && y>=0 && x<H && y<W && fac[x][y]!='X' && d[x][y]==INF){
				d[x][y] = d[p.first][p.second]+1;
				que.push(P(x, y));
			}
		} 
	}
}

int main(){
	cin >> H >> W >> N;
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			cin >> fac[i][j];
			if(fac[i][j] == 'S'){
				gl[0][0] = i;
				gl[0][1] = j;
			}
			if((int)fac[i][j]-48>=1 && (int)fac[i][j]-48<=N){
				gl[(int)fac[i][j]-48][0] = i;
				gl[(int)fac[i][j]-48][1] = j;
			}
		}	
	ans = 0;
	//分为N个循环，终点为起点，寻找下一个终点
	for(int i=0; i<N; i++){
		memset(d, INF, sizeof(d));
		Bfs(i);
		ans+=d[gl[i+1][0]][gl[i+1][1]];
	}
	cout << ans << endl;;
	return 0;
}

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

class DAT{
public:
  int x;
  int y;
  int total;
  bool operator<(const DAT &A)const{
    return A.total < total;
  }
};

int main(void){
  int h,w,n;
  cin>>h>>w>>n;
  vector<string> field(h);
  map<int,pair<int,int> > ps;
  int pl = 0;
  for(int i=0;i<h;++i){
    int j;
    cin>>field[i];
    if((j = field[i].find('S')) != string::npos)
      ps[0] = make_pair(j,i);
    for(char c='1';c<='9';++c)
      if((j = field[i].find(c)) != string::npos)
        ps[c-'0'] = make_pair(j,i);
    
    for(int j=0;j<w;++j){
        if(field[i][j] == '.' || field[i][i] == 'S' || ('1'<=field[i][j] && field[i][j] <= '9'))
          ++pl;
    }
  }
  int ans=0;
  for(int i=0;i<n;++i){
    int sx = ps[i].first, sy = ps[i].second;
    vector<vector<int> > dist(h);
    for(int j=0;j<h;++j){
    	dist[j]=vector<int>(w);
    	for(int k=0;k<w;++k){
    		dist[j][k]=pl;
    	}
    }
    priority_queue<DAT> Q;
    DAT start;
    start.x = sx; start.y = sy; start.total = 0;
    Q.push(start);
    int sum = 0;
    while(!Q.empty()){
      DAT dat = Q.top();Q.pop();
      if(dist[dat.y][dat.x] < dat.total) continue;
      if(dat.x == ps[i+1].first && dat.y == ps[i+1].second){sum=dat.total;break;}
      if(field[dat.y][dat.x] == '.' || field[dat.y][dat.x] == 'S' || ('1'<=field[dat.y][dat.x] && field[dat.y][dat.x] <= '9')){
        dist[dat.y][dat.x] = dat.total;
        if(dat.x>0){
          DAT nxt;
          nxt.x=dat.x-1;nxt.y=dat.y;nxt.total=dat.total+1;
          Q.push(nxt);
        }
        if(dat.y>0){
          DAT nxt;
          nxt.x=dat.x;nxt.y=dat.y-1;nxt.total=dat.total+1;
          Q.push(nxt);
        }
        if(dat.x<w-1){
          DAT nxt;
          nxt.x=dat.x+1;nxt.y=dat.y;nxt.total=dat.total+1;
          Q.push(nxt);
        }
        if(dat.y<h-1){
          DAT nxt;
          nxt.x=dat.x;nxt.y=dat.y+1;nxt.total=dat.total+1;
          Q.push(nxt);
        }
      }
    }
    ans+=sum;
  }
  cout<<ans<<endl;
  return 0;
}