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++: //31
#include<iostream>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

int main(){
  int h,w,n;
  cin>>h>>w>>n;
  char g[1000][1000];
  int y,x;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>g[i][j];
      if(g[i][j]=='S'){
	y=i;
	x=j;
      }
    }
  }
  int el=0;
  for(int i=1;i<=n;i++){
    static int t[1000][1000];
    fill_n(t[0],1000000,-1);
    t[y][x]=0;
    queue<pair<int,int> > que;
    que.push(make_pair(y,x));
    for(;;){
      int by=que.front().first;
      int bx=que.front().second;
      que.pop();
      for(int j=0;j<4;j++){
	int d[]={0,1,0,-1,0};
	int ny=by+d[j];
	int nx=bx+d[j+1];
	if(0<=ny&&ny<h&&0<=nx&&nx<w&&g[ny][nx]!='X'){
	  if(t[ny][nx]==-1){
	    t[ny][nx]=t[by][bx]+1;
	    if(g[ny][nx]=='0'+i){
	      el+=t[ny][nx];
	      y=ny;
	      x=nx;
	      goto next;
	    }
	    que.push(make_pair(ny,nx));
	  }
	}
      }
    }
  next:
    ;
  }
  cout<<el<<endl;
  return 0;
}

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

using namespace std;
typedef pair<int,int> P;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
const int INF=10000000;

int main(){ 
    stringstream ss;
    int H,W,N;
    P start;
    cin>>H>>W>>N;
    char field[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>field[i][j];
            if(field[i][j]=='S') start=P(i,j);
        }       
    }
    
    int step=0; 
    char goal='1';
    int taugh=1;
    while(taugh<=N){
        queue<P> que;
        que.push(start);
        int d[H][W];
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++) d[i][j]=INF;
        }       
        d[start.first][start.second]=0;

        while(que.size()){
            P p=que.front(); que.pop();
            if(field[p.first][p.second]==goal){
                step+=d[p.first][p.second];
                start=P(p.first,p.second);
                taugh++;
                ss<<taugh;
                ss>>goal;
                break;  
            }       
        
            for(int i=0;i<4;i++){
                int nx=p.first+dx[i]; int ny=p.second+dy[i];
                if(0<=nx&&nx<H&&0<=ny&&ny<W&&d[nx][ny]==INF&&field[nx][ny]!='X'){
                    que.push(P(nx,ny));
                    d[nx][ny]=d[p.first][p.second]+1;
                }       
            }       
        }       
    }

    cout<<step<<endl;
    return 0;
}

C++: // チーズ
//
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int H,W,N;
    cin >> H >>W >> N;
    char maze[H][W];
    for(int i=0;i<H;i++){
        cin >> maze[i];
    }

    vector<pair<int, int> > target(N+1);// スタートとチーズの位置情報の読取、スタートの位置をpair target[0]に、1番目のチーズをpairでtarget[1]に・・・
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            int temp=maze[i][j]-0x30;// char型から0x30を引くと、char型の0がintの0に
            if(0<temp && temp<10){target[temp] = make_pair(i,j);}
            else if(maze[i][j]=='S'){target[0] = make_pair(i,j);}
        }
    }
    
    int totalstep=0;
    for(int k=0;k<N;k++){
        int step[H][W];//歩数の記録用データ
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                step[i][j]=-1;//マップ上の歩数データをすべて-1で初期化する
            }
        }
        step[target[k].first][target[k].second]=0;//スタート地点の歩数を 0 に設定
        queue<pair<int, int> >q;// キュー q を定義
        q.push(target[k]);//スタート地点をqにプッシュ
        int answer=0;
        while(q.empty()==false){
            pair<int, int> cursor=q.front(); //　現在地をcursorに読み込む
            q.pop();
            int gyo=cursor.first;
            int retsu=cursor.second;
            if(gyo==target[k+1].first && retsu==target[k+1].second){answer=step[gyo][retsu];break;}//ゴール地点ならその地点に記録した歩数をanswerに代入
            //今の地点の四方を見て、Xでなく、なおかつまだ歩数が設定されていないなら、今の地点＋１の歩数を代入する
            if(gyo>0 && maze[gyo-1][retsu]!='X' && step[gyo-1][retsu]==-1){step[gyo-1][retsu]=step[gyo][retsu]+1;q.push(make_pair(gyo-1,retsu));}
            if(gyo<H-1 && maze[gyo+1][retsu]!='X' && step[gyo+1][retsu]==-1){step[gyo+1][retsu]=step[gyo][retsu]+1;q.push(make_pair(gyo+1,retsu));}
            if(retsu>0 && maze[gyo][retsu-1]!='X' && step[gyo][retsu-1]==-1){step[gyo][retsu-1]=step[gyo][retsu]+1;q.push(make_pair(gyo,retsu-1));}
            if(retsu<W-1 && maze[gyo][retsu+1]!='X' && step[gyo][retsu+1]==-1){step[gyo][retsu+1]=step[gyo][retsu]+1;q.push(make_pair(gyo,retsu+1));}
        }
        totalstep+=answer;
    }
    cout << totalstep << endl;
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;

const int INF = 1<<10;

int H, W, N;
char field[1010][1010];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
int vt[1010][1010];
int sx, sy;
int cnt = 0;

int bfs() {
  for (int i = 1; i <= N; i++) {
    queue<P> q;
    for (int y = 0; y < H; y++)
      for (int x = 0; x < W; x++) vt[y][x] = INF;
    q.push(P(sx, sy));
    vt[sy][sx] = 0;
    bool flag = false;

    while (!q.empty() && !flag) {
      int x = q.front().first;
      int y = q.front().second;
      int c = vt[y][x];
      q.pop();
      for (int j = 0; j < 4; j++) {
        int nx = x + dx[j], ny = y + dy[j];
        if (nx < 0 || nx >= W || ny < 0 || ny >= H || vt[ny][nx] != INF ||
            field[ny][nx] == 'X') continue;
        if (field[ny][nx] == '0' + i) {
          sx = nx; sy = ny;
          cnt += c + 1;
          flag = true;
          break;
        }
        q.push(P(nx, ny));
        vt[ny][nx] = c + 1;
      }
    }
  }
}

int main() {
  cin >> H >> W >> N;
  for (int y = 0; y < H; y++) {
    cin >> field[y];
    for (int x = 0; x < W; x++) {
      if (field[y][x] == 'S') {
        sx = x; sy = y;
      }
    }
  }

  bfs();
  cout << cnt << endl;

  return 0;
}