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++: //待解，&#35843;用函数 
#include<queue>
#include<cctype>
#include<cstdio>
#define mp          make_pair
using namespace std;
typedef pair<int,int> point;
const int maxn = 1005;
int height,width;    //n代表硬度 
char maze[maxn][maxn];
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

bool visited[maxn][maxn];
int shortDistance(int sx,int sy,int ex,int ey)
{
	//初始化visted数&#32452;
	for(int i = 0;i<height;i++)
		for(int j = 0;j<width;j++)
			visited[i][j] = false;
	visited[sy][sx] = true;
	queue<pair<int,point> > q;q.push(mp(0,mp(sy,sx)));
	while(1)
	{
		pair<int,point> a = q.front();q.pop();
		int d=a.first,x=a.second.second,y=a.second.first;
		if(x==ex&&y==ey)
		{
			return d;
		}
		for(int i = 0;i<4;i++)
		{
			 int xx=x+dx[i],yy=y+dy[i];
            if(0<=xx && xx<width && 0<=yy && yy<height && maze[yy][xx]!='X' && !visited[yy][xx]){
                visited[yy][xx]=true;
                q.push(mp(d+1,mp(yy,xx)));
            }
		}
	}
}

int main()
{
	int cx[10],cy[10],n;
	freopen("I:\\0558-in2.txt","r",stdin);
	scanf("%d%d%d",&height,&width,&n);
	//&#36755;入迷&#23467; 
	for(int i = 0;i<height;i++)
	{
		scanf("%s",maze[i]);
		//&#26597;找老鼠&#24034;的位置
		for(int j = 0;j<width;j++)
		{
			if(maze[i][j]=='S')
			{
				cy[0] = i;
				cx[0] = j;
			}
			else if(isdigit(maze[i][j]))
			{
				int k = maze[i][j]-'0';
				cx[k] = j;cy[k] = i;
			}
			
		}
	}
	int cost = 0;
	
	for(int i = 0;i<n;i++)
		cost += shortDistance(cx[i],cy[i],cx[i+1],cy[i+1]);
	printf("%d\n",cost);
	return 0;
}

C++: #include<iostream>
#include<queue>
#define fi first
#define se second
using namespace std;
int dy[4]={0,0,-1,1},dx[4]={1,-1,0,0};
int X,Y,N;
char field[1000][1001];
pair<int,int> time[1000][1001];
struct point{
    int y,x,t,n;
    point(int y_,int x_,int t_,int n_){
        y=y_;x=x_;t=t_;n=n_;
    }
};
int bfs(int,int);
int main(){
    cin>>Y>>X>>N;
    int rep;
    for(int i=0;i<Y;i++)cin>>field[i];
    for(int i=0;i<Y;i++){
        for(int j=0;j<X;j++){
            time[i][j].fi=time[i][j].se=-1;
        }
    }
    for(int i=0;i<Y;i++){
        bool flag=false;
        for(int j=0;j<X;j++){
            if(field[i][j]=='S'){
                rep=bfs(i,j);
                flag=true;
                break;
            }
        }
        if(flag)break;
    }
    cout<<rep<<endl;
    return 0;

}

int bfs(int y,int x){
    point start=point(y,x,0,0);
    queue<point>Q;
    Q.push(start);
    while(Q.size()){

        point a=Q.front();
        Q.pop();
        if(a.y<0 || a.y>=Y ||a.x<0||a.x>=X)continue;

        if(field[a.y][a.x]=='X')continue;

        if(a.n+1==field[a.y][a.x]-'0')a.n++;

        if(a.n>time[a.y][a.x].se){
            time[a.y][a.x].fi=a.t;
            time[a.y][a.x].se=a.n;
        }else if(a.n==time[a.y][a.x].se&&a.t<time[a.y][a.x].fi){
            time[a.y][a.x].fi=a.t;
        }else continue;

        if(a.n==N){
            return a.t;
        }


        for(int i=0;i<4;i++){
            point next=point(a.y+dy[i],a.x+dx[i],a.t+1,a.n);
            Q.push(next);
        }


    }



}

C++: #include <bits/stdc++.h>
using namespace std;

struct P{
    int x;
    int y;
    int dist;
    P(){}
    ~P(){}
    P(const P& r) : x(r.x), y(r.y), dist(r.dist) {}
    P(int a, int b, int c) : x(a), y(b), dist(c) {}
};


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

int H, W, N;
char field[1000][1010];
char poyo[1000][1010];
queue<P> que;

int main(){
    while(scanf("%d%d%d", &H, &W, &N) != EOF){
        for(int x = 0; x < H; x++){
            scanf(" %s", field[x]);
        }
        P path[10];
        for(int x = 0; x < H; x++){
            for(int y = 0; y < W; y++){
                if(field[x][y] == 'S'){
                    path[0] = P(x, y, 0);
                }
                if('1' <= field[x][y] && field[x][y] <= '9'){
                    path[field[x][y]-'0'] = P(x, y, 0);
                }
            }
        }
        int ans = 0;
        for(int x = 0; x < N; x++){
            while(!que.empty()) que.pop();
            for(int w = 0; w < H; w++){
                for(int z = 0; z < W; z++){
                    poyo[w][z] = field[w][z];
                }
            }
            que.push(P(path[x].x, path[x].y, 0));
            bool found = false;
            while(!found && !que.empty()){
                P p = que.front();
                que.pop();
                for(int z = 0; z < 4; z++){
                    int nx = p.x + dx[z];
                    int ny = p.y + dy[z];
                    if(0 > nx || nx >= H || 
                            0 > ny || ny >= W ||
                            poyo[nx][ny] == 'X') continue;
                    if(poyo[nx][ny] == '0'+x+1){
                        ans += p.dist+1;
                        found = true;
                        break;
                    }
                    que.push(P(nx, ny, p.dist+1));
                }
                poyo[p.x][p.y] = 'X';
            }
        }
        printf("%d\n", ans);
        break;
    }
    return 0;
}

C++: #include <iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
	int h, w, n; int sx, sy;//x<h,y<w
	cin >> h >> w >> n;
	vector<int> zer(w, 0);
	vector<vector<int> > syo(h, zer);
	vector<int> chx(n);
	vector<int> chy(n);
	for (int i = 0; i < h; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < w; j++) {
			char t = s[j];
			if (t == 'S') {
				sx = i;
				sy = j;
			}
			else if (t == 'X') {
				syo[i][j] = 1;
			}
			else if (t != '.') {
				int x = '1';
				int y = t - x;
				chx[y] = i;
				chy[y] = j;
			}
		}
	}
	int ans = 0;
	int bax = sx; int bay = sy;
	for (int i = 0; i < n; i++) {
		int x = chx[i];
		int y = chy[i];
		vector<vector<int> > c(h, zer);
		c[bax][bay] = 1;
		vector<int> nex(h*w);
		vector<int> ney(h*w);
		nex[0] = bax;
		ney[0] = bay;
		int st = 0;
		int end = 1;
		while (c[x][y] == 0) {
			int th = end;
			for (int i = st; i < end; i++) {
				int ax = nex[i];
				int ay = ney[i];
				if (ax > 0) {
					if (c[ax - 1][ay] == 0 and syo[ax - 1][ay] == 0) {
						c[ax - 1][ay] = 1;
						nex[th] = ax - 1;
						ney[th] = ay;
						th++;
					}
				}
				if (ay > 0) {
					if (c[ax][ay - 1] == 0 and syo[ax][ay - 1] == 0) {
						c[ax][ay - 1] = 1;
						nex[th] = ax;
						ney[th] = ay-1;
						th++;
					}
				}
				if (ax < h - 1) {
					if (c[ax + 1][ay] == 0 and syo[ax + 1][ay] == 0) {
						c[ax + 1][ay] = 1;
						nex[th] = ax + 1;
						ney[th] = ay;
						th++;
					}
				}
				if (ay < w - 1) {
					if (c[ax][ay + 1] == 0 and syo[ax][ay + 1] == 0) {
						c[ax][ay + 1] = 1;
						nex[th] = ax;
						ney[th] = ay + 1;
						th++;
					}
				}
			}
			st = end;
			end = th;
			ans++;
		}
		bax = x;
		bay = y;
	}
	cout << ans << endl;
}