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 <algorithm>
#include <queue>
#include <map>

using namespace std;

int h, w, n;
int sx, sy;
char input[1002][1002];
char stage[1002][1002];

typedef pair<int, int> P;

int dir[] = { 0, 1, 0, -1, 0 };
map<int, P> chs;


int solve(int xs, int ys, int cur)
{
	if(cur > n) return 0;
	queue<P> que;
	queue<int> count;
	for (int i = 0; i < 1002; i++)
	{
		for (int j = 0; j < 1002; j++)
		{
			stage[i][j] = input[i][j];
		}
	}
	que.push(P(xs, ys));
	count.push(0);
	while (!que.empty())
	{
		P now = que.front(); que.pop();
		int c = count.front(); count.pop();
		for (int i = 0; i < 4; i++)
		{
			P next = P(now.first + dir[i], now.second + dir[i + 1]);
			if(stage[next.second][next.first] == 'X') continue;
			if(next == chs[cur])
			{
				return solve(next.first, next.second, cur + 1) + c + 1;
			}
			stage[next.second][next.first] = 'X';
			que.push(next);
			count.push(c + 1);
		}
	}
	return 0;
}

int main()
{
	fill(input[0], input[0] + sizeof(input), 'X');
	cin >> h >> w >> n;
	for (int i = 1; i < h + 1; i++)
	{
		for (int j = 1; j < w + 1; j++)
		{
			cin >> input[i][j];
			if(input[i][j] == 'S')
			{
				sy = i; sx = j;
			}
			char c = input[i][j] - '0';
			if(c < 10 && c > 0)
			{
				chs[c] = P(j, i);
			}
		}
	}
	cout << solve(sx, sy, 1) << endl;
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

char ma[1001][1001];
bool visited[1001][1001];
int h,w,n;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int sx,sy;
vector<pair<int,int> >vec(10);
queue<pair<pair<int,int>,int> >que;
int bfs(int d){
    while(que.size()){
        pair<pair<int,int>,int>q=que.front();
        que.pop();
        int x=q.first.first;
        int y=q.first.second;
        if(ma[y][x]-'0'==d){
            return q.second;
        }
        visited[y][x]=1;
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&nx<w&&ny>=0&&ny<h&&ma[ny][nx]!='X'&&!visited[ny][nx]){
                que.push(make_pair(make_pair(nx, ny),q.second+1));
            }
        }
    }
    return 0;
}

int main(){
    cin>>h>>w>>n;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>ma[i][j];
            if(ma[i][j]>'0'&&ma[i][j]<='9'){
                vec[ma[i][j]-'0']=make_pair(j, i);
            }
            if(ma[i][j]=='S'){
                vec[0]=make_pair(j, i);
            }
        }
    }
    int c=0;
    for(int i=1;i<=n;i++){
        while(que.size())que.pop();
        memset(visited,0,sizeof(visited));
        que.push(make_pair(make_pair(vec[i-1].first,vec[i-1].second),0));
        c+=bfs(i);
    }
    cout<<c<<endl;
}

C++: #include <iostream>
#include <queue>
#include <map>
#define INF 10000000
using namespace std;

typedef pair<int, int> P;

int H, W, N;
int d[1000][1000];
char cell[1000][1000];
int si, sj, sum = 0;

void bfs(P start, int search){
	int vi[4] = {0, 0, -1, 1}, vj[4] = {-1, 1, 0, 0};
	int gi, gj;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			d[i][j] = INF;
			if(cell[i][j] == search + '0'){
				gi = i;
				gj = j;
			}
		}
	}
	d[start.first][start.second] = 0;
	queue<P> que;
	que.push(start);
	while(!que.empty()){
		P p = que.front();
		que.pop();
		if(p.first == gi && p.second == gj) break;
		int ni, nj;
		for(int i=0;i<4;i++){
			ni = p.first + vi[i];
			nj = p.second + vj[i];
			if(ni >= 0 && ni < H && nj >= 0 && nj < W && cell[ni][nj] != 'X' && d[ni][nj] == INF){
				que.push(P(ni, nj));
				d[ni][nj] = d[p.first][p.second] + 1;
			}
		}
	}
	sum += d[gi][gj];
	if(search != N) bfs(P(gi, gj), search+1);
}

int main(){
	cin >> H >> W >> N;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin >> cell[i][j];
			if(cell[i][j] == 'S'){
				si = i;
				sj = j;
			}
		}
	}
	bfs(P(si, sj), 1);
	cout << sum << endl;
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

struct State {
  int i, j, v;
};
string m[1002];
int H, W, N;
bool visit[1002][1002];
const int di[4] = {0,0,-1,1};
const int dj[4] = {1,-1,0,0};

int solve() {
  int srcI, srcJ;
  // search source
  for (int i = 0; i < H; ++i)
    for (int j = 0; j < W; ++j)
      if (m[i][j] == 'S')
	srcI = i, srcJ = j;
  // bfs
  int ret = 0;
  for (int destValue = 1; destValue <= N; ++destValue) {
    queue<State> Q;
    memset(visit, 0, sizeof visit);
    Q.push((State){srcI, srcJ, 0});
    while(!Q.empty()) {
      State s = Q.front(); Q.pop();
      if (visit[s.i][s.j]) continue;
      visit[s.i][s.j] = true;
      // is goal
      if (m[s.i][s.j]-'0' == destValue) {
	srcI = s.i, srcJ = s.j;
	ret += s.v;
	break;
      }
      for (int i = 0; i < 4; ++i) {
	const int ni = s.i + di[i], nj = s.j + dj[i];
	if (ni < 0 || nj < 0 || H <= ni || W <= nj) continue;
	if (visit[ni][nj] || m[ni][nj] == 'X') continue;
	Q.push((State){ni, nj, s.v + 1});
      }
    }
  }
  return ret;
}

int main() {
  while (cin >> H >> W >> N) {
    for (int i = 0; i < H; ++i)
      cin >> m[i];
    cout << solve() << endl;
  }
  return 0;
}

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

using namespace std;

class point {
public:
    int x;
    int y;
    int cnt;
    point(int a, int b, int c) {
        x = a;
        y = b;
        cnt = c;
    }
};

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
int h, w, n;

int main()
{
    cin >> h >> w >> n;
    vector<string> map(h);

    for (int i = 0; i < h; i++)
        cin >> map[i];

    int ans = 0;
    int sx, sy;

    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (map[i][j] == 'S') {
                map[i][j] == '.';
                sy = i;
                sx = j;
                break;
            }

    for (int i = 1; i <= n; i++) {
        point p(sx, sy, 0);
        queue<point> q;
        vector<vector<bool> > memo(h, vector<bool>(w, false));

        q.push(p);
        memo[sy][sx] = true;

        while (!q.empty()) {
            point now = q.front();
            q.pop();

            if (map[now.y][now.x] == i + '0') {
                ans += now.cnt;
                sy = now.y;
                sx = now.x;
                break;
            }

            for (int j = 0; j < 4; j++) {
                int nx = now.x + dx[j];
                int ny = now.y + dy[j];
                if (nx < 0 || nx >= w || ny < 0 || ny >= h || 
                    map[ny][nx] == 'X' || memo[ny][nx])
                    continue;

                q.push(point(nx, ny, now.cnt + 1));
                memo[ny][nx] = true;
            }
        }
    }

    cout << ans << endl;

    return 0;
}