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>
using namespace std;
 
struct cordinate{
    int x;
    int y;
};
 
int map[1005][1005], memo[1005][1005], counter[1005][1005];
int result = 0, mouselevel = 1;
queue<cordinate> q;
cordinate def;
 
int vx[4] = {0, 1, 0, -1};
int vy[4] = {1, 0, -1, 0};
 
void serch(cordinate s, int H, int W){
    def = s;
    for(int i = 0; i < 4; i++){
        if(i == 0 && s.y + 1 == H) continue;
        if(i == 1 && s.x + 1 == W) continue;
        if(i == 2 && s.y + 1 == 0) continue; 
        if(i == 3 && s.x + 1 == 0) continue;
 
        s = def;
        s.x += vx[i];
        s.y += vy[i];
        if(map[s.y][s.x] > -2 && memo[s.y][s.x] == 1){
            q.push(s);
            memo[s.y][s.x] = 0;
            counter[s.y][s.x] = counter[def.y][def.x] + 1;
            if(map[s.y][s.x] == mouselevel){
                result += counter[s.y][s.x];
                mouselevel++;
                map[s.y][s.x] = 0;
                for(int i = 0; i < H; i++){
                    for(int j = 0; j < W; j++){
                        counter[i][j] = 0;
                        memo[i][j] = 1;
                    }
                }
                while(true){
                    if(q.size() == 1){
                        break;
                    }
                    q.pop();
                }
                return;
            }
        }
    }
}
 
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}
 
int main(){
    int H, W, N;
    char a;
    cordinate s;
    cin >> H >> W >> N;
 
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> a;
            memo[i][j] = 1;
            if(a == '.'){
                map[i][j] = 0;
                counter[i][j] = 0;
            }else if(a == 'X'){
                map[i][j] = -2;
            }else if(a == 'S'){
                map[i][j] = -1;
                s.y = i;
                s.x = j;
                q.push(s);
            }else{
                map[i][j] = ctoi(a);
            }
        }
    }
 
    memo[s.y][s.x] = 0;
 
    for(int i = 0; i < N; i++){
        while(true){            
            s = q.front(); 
            q.pop();
            serch(s, H, W);
            if(mouselevel == i + 2){
                break; 
            }
        }
 
    }
    cout << result << endl;
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>
#include <queue>

using namespace std;

int H, W, N;
char c[1010][1010];
int d[1010][1010];
bool check = false;
using P = pair<int, int>;

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

int main(){
    cin >> H >> W >> N;

    vector<int> sy(N+1);
    vector<int> sx(N+1);
    for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j){
        cin >> c[i][j];
        if(c[i][j] == 'S'){
            sx[0] = j;
            sy[0] = i;
        }
        if('0' <= c[i][j] && c[i][j] <= '9'){
            int po = int(c[i][j] - '0');
            sx[po] = j;
            sy[po] = i;
        }
    }

    int ans = 0;
    for(int k = 0; k < N; ++k){
        for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j){
            d[i][j] = 0;
        }

        queue<P> que;
        que.push(P(sx[k], sy[k]));
        while(!que.empty()){
            P p = que.front();
            que.pop();

            for(int i = 0; i < 4; ++i){
                int nx = p.first + dx[i];
                int ny = p.second + dy[i];
                if(0 <= nx && nx < W && 0 <= ny && ny < H && c[ny][nx] != 'X' && d[ny][nx] == 0){
                    d[ny][nx] = d[p.second][p.first] + 1;
                    que.push(P(nx, ny));
                }
                if(nx == sx[k+1] && ny == sy[k+1]){
                    break;
                }
            }
        }
        ans += d[sy[k+1]][sx[k+1]];
    }
    cout << ans << endl;
}

C++: #include<iostream>
#include<queue>
using namespace std;
struct Point{int x,y,dist;};
int main()
{
  int H,W,N;
  int vital;
  int i,j;
  string field[1000];
  int dx[4]={0,1,0,-1};
  int dy[4]={-1,0,1,0};
  int sx,sy,ans;
  bool b;

  cin>>H>>W>>N;
  for(i=0;i<H;i++)cin>>field[i];
  b=1;
  for(i=0;b&&i<H;i++){
    for(j=0;b&&j<W;j++){
      if(field[i][j]=='S'){
	sy=i;
	sx=j;
	ans=0;
	b=0;
      }
    }
  }

  for(vital=1;vital<=N;vital++){
    queue<Point>q;
    bool visited[1000][1000]={0};
    bool f=1;

    Point p={sx,sy,0};
    q.push(p);
    while(f){
      Point p=q.front();
      q.pop();
      visited[p.y][p.x]=true;

      for(i=0;f&i<4;i++){
	Point p2;
	p2.y=p.y+dy[i];
	p2.x=p.x+dx[i];
	p2.dist=p.dist+1;
	if(p2.y<0||H<=p2.y)continue;
	if(p2.x<0||W<=p2.x)continue;
	if(field[p2.y][p2.x]=='X')continue;
	if(visited[p2.y][p2.x])continue;
	if(field[p2.y][p2.x]==(vital+'0')){
	  sy=p2.y;
	  sx=p2.x;
	  ans+=p2.dist;
	  f=0;
	}
	q.push(p2);
      }
    }
  }
  cout<<ans<<endl;
}

C++: #include <iostream>
#include<queue>
using namespace std;
int H,W,N,sx,sy;
char map[1001][1001];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct Point
{
    int x,y,num,energy,step;
} ;
int BFS()
{
    int ans=1000000;
    queue<Point> q;
    Point p1,p2;
    p1.x=sx;p1.y=sy;p1.num=0;p1.energy=1;p1.step=0;
    q.push(p1);
    while(!q.empty())
    {
       p1=q.front();
       q.pop();
//cout<<p1.x<<" "<<p1.y<<" "<<p1.num<<" "<<p1.step<<" "<<p1.energy<<endl;
       if(p1.num==N&&ans>p1.step)
       {
           ans=p1.step;
           break;
       }

       for(int i=0;i<4;i++)
       {
         p2.x=p1.x+dir[i][0];
         p2.y=p1.y+dir[i][1];
         p2.num=p1.num;
         p2.energy=p1.energy;
         p2.step=p1.step+1;
         if(p2.x<0||p2.x>=H||p2.y<0||p2.y>=W)continue;
         if(map[p2.x][p2.y]=='X') continue;
         else if(map[p2.x][p2.y]=='.')
            {
                q.push(p2);
               // cout<<p2.x<<" "<<p2.y<<endl;
            }
         else if(p2.energy>=(map[p2.x][p2.y]-48))
         {
             p2.num++;p2.energy++;
             map[p2.x][p2.y]='.';
             q.push(p2);
            // cout<<p2.x<<" "<<p2.y<<endl;
         }
       }
    }
return ans;
}
int main()
{
    while(cin>>H>>W>>N)
   {
    for(int i=0;i<H;i++)
     for(int j=0;j<W;j++)
     {
         cin>>map[i][j];
         if(map[i][j]=='S')
         {
             sx=i;sy=j;
         }
     }
    cout<<BFS()<<endl;
  }
}