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<queue>
#include<vector>
using namespace  std;
int h, w, n;
int sy = 0, sx = 0;
int dy[] = {0,0,1,-1};
int dx[] = {1,-1,0,0};
char field[1000][1000];
int main()
{
	cin >> h >> w >> n;
	for (int i = 0; i < h; i++)
	{
		cin >> field[i];
		for (int j = 0; j < w; j++)
		{
			if (field[i][j] == 'S')
			{
				sy = i;
				sx = j;
			}
		}
	}
	int ans = 0;
	for (int m = 1; m <= n; m++)
	{
		bool used[1000][1000];
		queue<pair<pair<int, int>, int> > q;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				used[i][j] = false;
			}
		}
		q.push(make_pair(make_pair(sy,sx), 0));
		used[sy][sx] = true;
		while (q.size() > 0)
		{
			pair<pair<int, int>, int> p = q.front(); q.pop();
			int y = p.first.first;
			int x = p.first.second;
			int c = p.second;

			if (field[y][x] == '0' + m)
			{
				sy = y;
				sx = x;
				ans += c;
				break;
			}

			for (int i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= h || nx >= w)continue;
				if (field[ny][nx] == 'X')continue;
				if (used[ny][nx])continue;
				used[ny][nx] = true;
				pair<pair<int, int>, int> next = make_pair(make_pair(ny,nx), c + 1);
				q.push(next);
			}
		}
	}

	cout << ans << endl;
	return 0;
}

C++: #include<iostream>
#include<queue>
#include<stdlib.h>
#include<utility>
#include<memory>
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
const int INF=-1;
char plat[1005][1005];
int d[1005][1005];
typedef pair<int,int> p;
int H,W,N;
queue<p> cheese;
int bfs(int& sx,int& sy,char energy)
{
    d[sx][sy]=0;
    cheese.push(p(sx,sy));
    while(cheese.size()){
        p test=cheese.front();
        cheese.pop();
        if(plat[test.first][test.second]==energy){
            sx=test.first;sy=test.second;
            return d[test.first][test.second];
        }
        for(int i=0;i<4;++i){
            int nx=test.first+dx[i];int ny=test.second+dy[i];
            if(nx>=0&&nx<W&&ny>=0&&ny<H&&plat[nx][ny]!='X'&&d[nx][ny]==INF){
                cheese.push(p(nx,ny));
                d[nx][ny]=d[test.first][test.second]+1;
            }
        }

    }
}

int main()
{

    cin>>W>>H>>N;
    int sx,sy;
    for(int i=0;i<W;++i){
        for(int j=0;j<H;++j){
            char u;
            cin>>u;
            if(u=='S'){
                sx=i;sy=j;
            }
            plat[i][j]=u;
        }
    }
    char e='1';
    int ans=0;
    while(N--){
        memset(d,-1,sizeof(d));
        ans+=bfs(sx,sy,e++);
        while(cheese.size())cheese.pop();

    }
    cout<<ans<<endl;

}

C++: #include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

typedef long long ll;

const ll INF = 999999;

int W, H, N;
queue<pair<ll, ll> > que; // ??§?¨? ???????????¢
vector<string> vs;
ll d[1010][1010];
ll st, gl, goal[10];

ll Z(int y, int x){
    return 1010 * y + x;
}

int main(){
    cin >> H >> W >> N;
    vs.resize(H);
    FOR(i,0,H) cin >> vs[i];
    FOR(y,0,H){
        FOR(x,0,W){
            if(vs[y][x]=='S') st = Z(y,x);
            if(vs[y][x]>='1' && vs[y][x]<='9') goal[vs[y][x]-'0'] = Z(y,x);
        }
    }

    // ?????????

    int vx[4] = {0,1,0,-1};
    int vy[4] = {-1,0,1,0};

    int n = 1;
    int ans = 0;
    while(n<=N){
        st = n==1?st:goal[n-1];
        gl = goal[n];

        FOR(i,0,H) FOR(j,0,W) d[i][j] = INF;
        while(!que.empty()) que.pop();
        que.push(make_pair(st, 0));
        d[st/1010][st%1010] = 0;
        while(!que.empty()){
            int nowy = que.front().first / 1010;
            int nowx = que.front().first % 1010;
            int nowd = que.front().second;
            que.pop();
            if(d[nowy][nowx] < nowd) continue;
            FOR(i,0,4){
                int nexty = nowy + vy[i];
                int nextx = nowx + vx[i];
                if(nexty < 0 || nexty >= H || nextx < 0 || nextx >= W) continue;
                if(vs[nexty][nextx]=='X') continue;
                int nextd = nowd + 1;

                if(d[nexty][nextx] > nextd){
                    d[nexty][nextx] = nextd;
                    que.push(make_pair(Z(nexty,nextx), nextd));
                }
            }
        }

        ans += d[gl/1010][gl%1010];
        n++;
    }
    cout << ans << endl;
    return 0;
}

C++: #include <ctype.h>
#include <stdio.h>
#include <string.h>

#include <queue>

using namespace std;

char map[1000][1000];
bool visited[1000][1000];
int W, H, N;
int startR, startC;
int targetR[10];
int targetC[10];

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int getMinTime() {
  int time = 0;
  int curR = startR;
  int curC = startC;
  for (int i = 0; i < N; ++i) {
    memset(visited, false, sizeof(visited));
    queue<int> q;
    q.push((curR << 16) | curC);
    visited[curR][curC] = true;
    while (!visited[targetR[i]][targetC[i]]) {
      time++;
      int count = q.size();
      while (count-- > 0) {
        int node = q.front();
        q.pop();
        int r = node >> 16;
        int c = node & 0xffff;
        for (int j = 0; j < 4; ++j) {
          int nr = r + dr[j];
          int nc = c + dc[j];
          if (nr >= 0 && nr < H && nc >= 0 && nc < W && !visited[nr][nc] && map[nr][nc] != 'X') {
            visited[nr][nc] = true;
            q.push((nr << 16) | nc);
          }
        }
      }
    }
    curR = targetR[i];
    curC = targetC[i];
  }
  return time;
}

int main() {
  //freopen("Cheese.in", "r", stdin);
  while (scanf("%d%d%d", &H, &W, &N) == 3 && W != 0 && H != 0 && N != 0) {
    for (int r = 0; r < H; ++r) {
      for (int c = 0; c < W; ++c) {
        char ch;
        do {
          ch = getchar();
        } while (isspace(ch));
        if (ch == 'S') {
          startR = r;
          startC = c;
        } else if (isdigit(ch)) {
          int index = ch - '0' - 1;
          targetR[index] = r;
          targetC[index] = c;
        }
        map[r][c] = ch;
      }
    }
    int result = getMinTime();
    printf("%d\n", result);
  }
  return 0;
}