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 <cstdio>
#include <iostream>
#include <queue>
#define ROP(i,n) for(int i=0;i<n;i++)
#define ROPP(i,n) for(int i=1;i<=n;i++)
#define NIL -1
using namespace std;
typedef pair<int,int> P;
int N,M,G,gx[10],gy[10];
char MAP[1005][1005];
int DX[4]={1,0,-1,0},DY[4]={0,1,0,-1},FAR[1005][1005];
int BFS(int u){
  queue<P> que;
  ROPP(i,N){ROPP(j,M) FAR[j][i]=NIL;}
  que.push(P(gx[u],gy[u]));
  FAR[gx[u]][gy[u]]=0;
  while(que.size()){
    P p=que.front();que.pop();
    if(p.first==gx[u+1]&&p.second==gy[u+1]) break;
    ROP(i,4){
      int nx=p.first+DX[i],ny=p.second+DY[i];
      if(1<=nx&&nx<=M&&1<=ny&&ny<=N
        &&MAP[nx][ny]!='X'&&FAR[nx][ny]==NIL){
        que.push(P(nx,ny));
        FAR[nx][ny]=FAR[p.first][p.second]+1;
      }
    }
  }
  return FAR[gx[u+1]][gy[u+1]];
}
void solve(){
  int res=0;
  ROP(i,G) res+=BFS(i);
  printf("%d\n",res);
}
int main(){
  scanf("%d %d %d",&N,&M,&G);
  ROPP(i,N){
    ROP(j,M+1){
      scanf("%c",&MAP[j][i]);
      if(MAP[j][i]=='S') gx[0]=j,gy[0]=i;
      if(MAP[j][i]=='1') gx[1]=j,gy[1]=i;
      if(MAP[j][i]=='2') gx[2]=j,gy[2]=i;
      if(MAP[j][i]=='3') gx[3]=j,gy[3]=i;
      if(MAP[j][i]=='4') gx[4]=j,gy[4]=i;
      if(MAP[j][i]=='5') gx[5]=j,gy[5]=i;
      if(MAP[j][i]=='6') gx[6]=j,gy[6]=i;
      if(MAP[j][i]=='7') gx[7]=j,gy[7]=i;
      if(MAP[j][i]=='8') gx[8]=j,gy[8]=i;
      if(MAP[j][i]=='9') gx[9]=j,gy[9]=i;
    }
  }
  solve();
  return 0;
}

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

int h,w,n;
const int MAX_N=1005;
char map[MAX_N][MAX_N];
struct point{
    int x,y;
    int step;
    point(){
        x=0; y=0; step=0;
    }
    point(int xx, int yy, int ss){
        x=xx;
        y=yy;
        step=ss;
    }
};
struct point p[16];

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

int ok(int x, int y){
    if(x>=0 && x<h && y>=0 && y<w) return 1;
    return 0;
}

int bfs(int next){
    int nextcheese = next +1; 
    
    queue<point> q;
    point cur(p[next].x, p[next].y,0);
    q.push(cur);
    while(q.size()){
        cur = q.front(); q.pop(); 
        int x=cur.x, y=cur.y;
        int nx, ny;
        for(int i=0; i<4; i++){
            nx = x+dx[i]; ny=y+dy[i];
            if(ok(nx, ny)){
                if((map[nx][ny]-'0')==nextcheese) return ++cur.step;
                if(map[nx][ny]=='.'){
                    point temp(nx, ny, cur.step+1);
                    q.push(temp);
                }
            }
        }
    }
}

void solve(){
    cin>>h>>w>>n;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>map[i][j];
        }
    }
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char ch=map[i][j];
            switch(ch){
                case '.': break;
                case 'X': break;
                case 'S': p[0].x = i; p[0].y = j; map[i][j]='.';break;
                default:
                int t=(ch-'0');
                p[t].x = i; p[t].y = j;
            }
        }
    }
    int step=0;
    for(int i=0; i<n; i++){
        step+=bfs(i);
    }
    printf("%d\n", step);
}


int main(){
    solve();
}

C++: #include <iostream>
#include <math.h>
#include <queue>
using namespace std;
const int INF=100000000;
typedef pair<int,int> P;
char**maze; 
int H,W,N; 
int*y; int *x;
int**d;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int bfs(int sy,int sx,int gy,int gx){
  queue<P> que;
  for(int h=0; h<H; h++)
    for(int w=0; w<W; w++) d[h][w]=INF;
   que.push(P(sy,sx));
   d[sy][sx]=0;
  while(que.size()){
    P p = que.front(); que.pop();
    if(p.first==gy&&p.second==gx) break;
    for(int i=0; i<4; i++){
      int ny=p.first+dy[i],nx=p.second+dx[i];
      if(0<=nx&&nx<W&&0<=ny&&ny<H&&
      maze[ny][nx]!='X'&&d[ny][nx]==INF){
        que.push(P(ny,nx));
        d[ny][nx]=d[p.first][p.second]+1;
        }
    }
  }
  return d[gy][gx];
}
int main() {
    cin>>H>>W>>N;
    y=new int[N+1]; x=new int[N+1];
    maze = new char*[H];
 for (int h = 0; h <H; h++) {
        maze[h] = new char[W];
    }
 for (int h = 0; h < H; h++) {
  for (int w = 0; w < W; w++) {
	  cin >> maze[h][w]; 
    if(maze[h][w]!='.'&&maze[h][w]!='X'&&
    maze[h][w]!='S'){
      int p=(int)maze[h][w]-(int)'0';
      y[p]=h;
      x[p]=w;
    }else if(maze[h][w]=='S'){
      y[0]=h; x[0]=w;
    }
  }
 }
          d = new int*[H];
   for (int h = 0; h <H; h++) {
       d[h] = new int[W];
    }
  int res=0;
  for(int i=0; i<=N-1; i++){
    res+=bfs(y[i],x[i],y[i+1],x[i+1]);
    }
   cout<<res<<endl;
 return 0;
}

C++: #include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define pr(x) cout<<#x<<" "<<x;
#define pl(x) cout<<#x<<" "<<x<<endl;
#include<math.h>
#include<algorithm>
using namespace std;
char maze[1005][1005];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int d[1005][1005];
const int INF = 0x7f7f7f7f;
typedef pair <int ,int > p;
queue <p> que;
int h,w;
void chushihua(){
    for(int i = 0;i<1005;i++){
        for(int j = 0;j<1005;j++){
            d[i][j] = INF;
        }
    }
}
int bfs(int x,int y,int gx,int gy){
    chushihua();
    d[x][y] = 0;
    que.push(p(x,y));
    while(que.size()){
        p cp = que.front();
        que.pop();
        if(cp.first==gx&&cp.second==gy){break;}
        for(int i = 0;i<4;i++){
            int nx = cp.first + dx[i];
            int ny = cp.second + dy[i];
            pl(nx);
            pl(ny);
            if(nx>=0&&nx<h&&ny>=0&&ny<w&&maze[nx][ny]!='X'&&d[nx][ny]==INF){
               que.push(p(nx,ny));
               d[nx][ny] = d[cp.first][cp.second] + 1;
               pl(d[nx][ny]);
            }
        }
    }
    return d[gx][gy];


}
int main(){
    int n;
    cin>>h>>w>>n;
    int indexmap[n+5][4];
    getchar();
    for(int i = 0;i<h;i++){
        scanf("%s",&maze[i]);
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            if(maze[i][j]=='S'){
                indexmap[0][0] = i;
                indexmap[0][1] = j;

            }
            else if((int)maze[i][j]>=49&&(int)maze[i][j]<=57){
                int index = maze[i][j]-'0';
                indexmap[index][0] = i;
                indexmap[index][1] = j;


            }
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        ans += bfs(indexmap[i][0],indexmap[i][1],indexmap[i+1][0],indexmap[i+1][1]);
    }
    cout<<ans<<endl;

}