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 <iostream>
using namespace std;
int ans = 0;
int gh=0, gw=0;
char c[1000][1000];
int d[1000][1000];
int mh[4] = { 1,0,-1,0 };
int mw[4] = { 0,1,0,-1 };
char hijou[9] = { '1','2','3','4','5','6','7','8','9' };
int  judge(int h, int w,int g) {
	if (c[h][w] ==hijou[g])
	{ 	
		gh = h;
	gw = w; 
	return d[h][w];
	}
	for (int i = 0; i < 4; i++) {
		int nh = h + mh[i];
		int nw = w + mw[i];
		if (nh >= 0 && nh < 1000 && nw>=0 && nh < 1000 && d[nh][nw] == 500000&&c[nh][nw] != 'X') {
			d[nh][nw] = d[h][w] + 1;
			judge(nh, nw,g);
		}
	}
}
int main() {
	int h, w, n,sh,sw;
	for (int i = 0; i < 1000;i++){
		for (int j = 0; j < 1000; j++)
		{
			c[i][j] = 'X'; 
		}
	}
	cin >> h >> w >> n;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w;j++){
			cin >> c[i][j];
			if (c[i][j] == 'S') { sh = i; sw = j; }
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 1000; j++) {
			for (int k = 0; k < 1000; k++)
				d[j][k] = 500000;
		}
	
		d[sh][sw] = 0;
		ans+=judge(sh, sw, i);
		sh = gh; sw = gw;
}
	cout << ans << endl;

 	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;
typedef pair<int,int>P;
char field[1000][1001];
P time[1000][1001];//first->time,second->cheese
typedef struct point{
    int y,x,t,n;
}point;
int bfs(int,int);
int main(){
    cin>>Y>>X>>N;
    int rep=0;
    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={y,x,0,0};
    queue<point>Q;
    Q.push(start);
    while(Q.size()){

        point a;
        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={a.y+dy[i],a.x+dx[i],a.t+1,a.n};
            Q.push(next);
        }


    }



}

C++: #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
struct as
{
    int x,y;
}pos[10]; //用来存储每次的起点和终点
struct node
{
    int x,y;
    int step;
};
bool vis[1010][1010];
char maze[1050][1050];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int H,W,N;

bool check(int x,int y)
{
    if (x<=0 || x>H) return 1;
    if (y<=0 || y>W) return 1;
    if (vis[x][y]) return 1;
    if (maze[x][y] =='X')return 1;
    return 0;
}
int bfs(int m,int n)
{
    memset(vis,0,sizeof vis);
    int sx = pos[m].x, sy = pos[m].y;
    int gx = pos[n].x, gy = pos[n].y;
   // printf("%d %d\n",sx,sy);
   // printf("%d %d\n",gx,gy);
    queue<node> Q;
    node a,next;
    a.step = 0;
    a.x = sx, a.y =sy;
    Q.push(a);
    while(!Q.empty())
    {
        a = Q.front();
        Q.pop();
        if (a.x == gx && a.y == gy)
            return a.step;
        for(int i = 0; i < 4 ;i++)
        {
            int nx = a.x + dx[i];
            int ny = a.y + dy[i];
            if(check(nx,ny))
                continue;
            else
            {
                vis[nx][ny] =1;
                next.x = nx,next.y = ny,next.step = a.step+1;
                Q.push(next);
            }
        }
    }
    return 999999;
}

int main()
{
   // freopen("in.txt","r",stdin);
    while(cin>>H>>W>>N)
    {
        int sx,sy;
        for(int i = 1;i<=H;i++)
        {
            for(int j = 1; j <= W;j++)
            {
                cin>>maze[i][j];
                if (maze[i][j] >='1' && maze[i][j]<='9')
                {
                    pos[maze[i][j]-'0'].x = i;
                    pos[maze[i][j]-'0'].y = j;
                }
                if (maze[i][j]=='S')
                    sx=i,sy = j;
            }
        }

        pos[0].x = sx,pos[0].y = sy;
        int ans = 0;
        for(int i = 0;i<N;i++)
            ans += bfs(i,i+1);
        cout<<ans<<endl;
    }
    return 0;
}

C++: #include <stdio.h>
#include <stdlib.h>

#include <queue>

using namespace std;

typedef struct State_Def {
	int y;
	int x;
	State_Def(int _y, int _x) {y = _y; x = _x;}
} S;

const int INF = 1e+8;
int h, w, n;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char **data;
int **dist;
int *cX;
int *cY;

int bfs(int fI, int fJ, int tI, int tJ) {
	int i, j;
	queue<S> q;

	for (i=0; i<h; i++)
		for (j=0; j<w; j++)
			dist[i][j] = INF;
	dist[fI][fJ] = 0;

	S s = S(fI, fJ);
	q.push(s);

	while (!q.empty()) {
		S t = q.front();
		q.pop();

		if (t.y == tI && t.x == tJ) break;

		for (i=0; i<4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (0<=nx && nx<w && 0<=ny && ny<h && data[ny][nx] != 'X' && dist[ny][nx] == INF) {
				dist[ny][nx] = dist[t.y][t.x] + 1;
				q.push(S(ny, nx));
			}
		}	
	}

	return dist[tI][tJ];
}

int main() {
	int i, j;
	int res;

	scanf("%d%d%d ", &h, &w, &n);
	data = (char **)calloc(h, sizeof(char *));
	dist = (int  **)calloc(h, sizeof(char *));
	for (i=0; i<h; i++) {
		data[i] = (char *)calloc(w, sizeof(char));
		dist[i] = (int  *)calloc(w, sizeof(int));
	}

	cX = (int *)calloc(n+1, sizeof(int));
	cY = (int *)calloc(n+1, sizeof(int));

	for (i=0; i<h; i++)
		for (j=0; j<w; j++)
			scanf("%c ", &(data[i][j]));
	
	for (i=0; i<h; i++)
		for (j=0; j<w; j++) {

			int cn = data[i][j] - '0';

			if (data[i][j] == 'S')  {
				cX[0] = j;
				cY[0] = i;
			} else if (0<cn && cn<=n) {
				cX[cn] = j;
				cY[cn] = i;
			}
		}

/*
	printf("(h, w, h) = (%d, %d, %d)\n", h, w, n);
	
	puts("data");
	for (i=0; i<h; i++) {
		for (j=0; j<w; j++)
			printf("%c", data[i][j]);
		puts("");
	}

	puts("dist");
	for (i=0; i<h; i++) {
		for (j=0; j<w; j++)
			printf("%d ", dist[i][j]);
		puts("");
	}

	for (i=0; i<=n; i++) 
		printf("(cX[%d], cY[%d]) = (%d, %d)\n", i, i, cX[i], cY[i]);
*/

	res = 0;
	for (i=0; i<n; i++)
		res += bfs(cY[i], cX[i], cY[i+1], cX[i+1]);
	
	printf("%d\n", res);
	
	for (i=0; i<h; i++) {
		free(data[i]);
		free(dist[i]);
	}
	free(data);
	free(dist);
	
	free(cX);
	free(cY);

	return 0;
}