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 <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
const int dx[] ={1,0,-1,0};
const int dy[] ={0,-1,0,1};
typedef pair<int,int> P;
const int INF =1e+9;
int H,W,N;
int d[1010][1010];
char board[1010][1010];
int sx,sy;
int gx,gy;
int ans;
void bfs(int y,int x,int k){
  for(int i = 1;i <=H;i++){
    for(int j = 1;j <=W;j++){
      d[i][j] =INF;
      if(board[i][j] == k+'0'){
	gx = j;
	gy = i;
      }
    }
  }
  d[y][x] = 0;
  queue<P> que;
  que.push(P(y,x));
  while(!que.empty()){
    P p = que.front();
    que.pop();

    if(p.first ==gy&&p.second ==gx)
      break;
    for(int i = 0;i < 4;i++){
      int nx = p.second+dx[i];
      int ny = p.first+dy[i];
      if(nx >=1&&nx <=W&&ny >=1&&ny <=H&&board[ny][nx] !='X'&&d[ny][nx] >d[p.first][p.second]){
	que.push(P(ny,nx));
	d[ny][nx] =d[p.first][p.second]+1;
      }
    }
  }
  ans += d[gy][gx];
  if(k !=N)
    bfs(gy,gx,k+1);
}

int main()
{
  cin>>H>>W>>N;
  for(int i = 1;i <=H;i++){
    for(int j = 1;j <=W;j++){
      cin>>board[i][j];
    }
  }
  for(int i = 1;i <=H;i++){
    for(int j = 1;j <=W;j++){
      if(board[i][j] =='S'){
	sx = j;
	sy = i;
      }
    }
  }
  bfs(sy,sx,1);
  cout <<ans<<endl;
  return 0;
}

C++: #include <iostream>
#include <queue>
#include <cstdio>
#include <string.h>
#define MAX 1005
using namespace std;
char map[MAX][MAX];
int w, h, n, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, vis[MAX][MAX];
struct maze {
	int x;
	int y;
	int time;
};
maze bfs(int bx, int by, char ch) {
	memset(vis, 0, sizeof(vis));
	queue<maze> que;
	maze emp = { bx,by,0 };
	que.push(emp);
	vis[bx][by] = 1;
	while (!que.empty()) {
		emp = que.front();
		que.pop();
		if (map[emp.x][emp.y] == ch) {
			return emp;
		}
		for (int i = 0; i < 4; i++) {
			int nx =emp.x + dx[i];
			int ny = emp.y + dy[i];
			if (nx >= 0 && nx < w&&ny >= 0 && ny < h&&map[nx][ny] != 'X' && !vis[nx][ny]) {
				maze ex = { nx,ny,emp.time + 1 };
				vis[nx][ny] = 1;
				que.push(ex);
			}
		}
	}
}
int main()
{
	while (~scanf("%d %d %d", &w, &h, &n)) {
		int bx, by;
		for (int i = 0; i < w; i++) {
			scanf("%s", map[i] + 1);
			for (int j = 0; j < h; j++) {
				if (map[i][j] == 'S') {
					bx = i;
					by = j;
					map[i][j] = '0';
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			maze ex = bfs(bx, by, map[bx][by] + 1);
			ans += ex.time;
			bx = ex.x;
			by = ex.y;
		}
		cout << ans << endl;
	}
}

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

using namespace std;

typedef pair<int, int> p;

int w, h, n, result, steps, ripple[1000][1000];
char map[1000][1000], omap[1000][1000];
bool visited[1000][1000];
p start, last_start, goal, cur;
queue<p> myqueue;

void init(int in){
    start = last_start;

    while(!myqueue.empty()) myqueue.pop();

    for(int i=0; i<w; ++i){
        for(int j=0; j<h; ++j){
            map[i][j] = omap[i][j];
            ripple[i][j] = -1;
            if(map[i][j] == 'X'){
                visited[i][j] = true;
            }else if(map[i][j] == '0'+in){
                goal = make_pair(i, j);
                visited[i][j] = false;
            }else{
                visited[i][j] = false;
            }
        }
    }
    ripple[start.first][start.second] = 0;
    return ;
}

int main(){
    cin >> w >> h >> n;

    for(int i=0; i<w; ++i){
        for(int j=0; j<h; ++j){
            cin >> omap[i][j];
            if(omap[i][j] == 'S')
                last_start = make_pair(i, j);
        }
    }

    result = 0;
    for(int i=1; i<=n; ++i){
        init(i);
        myqueue.push(start);

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

            if(cur == goal){
                //cout << "goal\n";
                break;
            }

            visited[cur.first][cur.second] = true;

            int x = cur.first, y = cur.second;
            if(x-1 >= 0 && !visited[x-1][y]){
                myqueue.push(make_pair(x-1, y));
                ripple[x-1][y] = ripple[cur.first][cur.second]+1;
            }
            if(y-1 >= 0 && !visited[x][y-1]){
                myqueue.push(make_pair(x, y-1));
                ripple[x][y-1] = ripple[cur.first][cur.second]+1;
            }
            if(x+1 < w && !visited[x+1][y]){
                myqueue.push(make_pair(x+1, y));
                ripple[x+1][y] = ripple[cur.first][cur.second]+1;
            }
            if(y+1 < h && !visited[x][y+1]){
                myqueue.push(make_pair(x, y+1));
                ripple[x][y+1] = ripple[cur.first][cur.second]+1;
            }
        }


        /*cout << "round[" << i << "] : " << ripple[goal.first][goal.second] << endl;
        for(int j=0; j<w; ++j){
            for(int k=0; k<h; ++k){
                cout << ripple[j][k] << " ";
            }
            cout<< endl << endl;
        }*/
        result += ripple[goal.first][goal.second];
        last_start = goal;
    }
    cout << result << endl;
    return 0;
}