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]];
}
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;
    }
  }
  int res=0;
  ROP(i,G) res+=BFS(i);
  printf("%d\n",res);
  return 0;
}

C++: #include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;

char ma[1005][1005];int vis[1005][1005];
int w,h,n;

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

struct node
{
    int x,y,time;
};
node start;

void bfs(char ed)
{
    queue<node> que;
    que.push(start);
    vis[start.x][start.y]=1;
    while(!que.empty())
    {
        node no=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int x=no.x+dx[i];
            int y=no.y+dy[i];
            if(vis[x][y]||x>=w||x<0||y>=h||y<0||ma[x][y]=='X')
                continue;
            if(ma[x][y]==ed)
            {
                start.x=x;
                start.y=y;
                start.time=no.time+1;
                return ;
            }
            vis[x][y]=1;
            node no1;
            no1.x=x;no1.y=y;no1.time=no.time+1;
            que.push(no1);
        }
    }
}

int main()
{
    while(~scanf("%d %d %d", & w, & h, & n))
    {
        for(int i=0;i<w;i++)
        {
            scanf("%s",&ma[i]);
            for(int j=0;j<h;j++)
                if(ma[i][j]=='S')
                {
                    start.x=i;
                    start.y=j;
                    start.time=0;
                }

        }
            for(int i=0;i<n;i++)
            {
                memset(vis,0,sizeof(vis));
                bfs(i+'1');
            }

            printf("%d\n",start.time);


    }
}

C++: #include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"algorithm"
#include"queue"
using namespace std;
struct mmm
{
	int x,y;
}vv;
int dir[4][2] = {0,-1,-1,0,0,1,1,0};
char xx[1005][1005];
int bb[11][2];
queue <mmm> qq;
int vis[1005][1005];
int bfs(char t)
{
	int sum = 0;
	int pl = 0;
	while(!qq.empty())
	{
		vv = qq.front();
		int x0 = vv.x;
		int y0 = vv.y;
		//printf("%d %d %d\n",x0,y0,vis[x0][y0]);
		qq.pop();
		if(xx[x0][y0] == t && !pl)
		{
			sum = vis[x0][y0];
			pl = 1;
		}
		for(int i = 0;i < 4;i++)
		{
			int xt = x0 + dir[i][0];
			int yt = y0 + dir[i][1];
			if(xx[xt][yt] != '#' && xx[xt][yt] != 'X' && vis[xt][yt] == -1)
			{
				vis[xt][yt] = vis[x0][y0] + 1;
				vv.x = xt;
				vv.y = yt;
				qq.push(vv);
			}
		}
	}
	return sum;
}
int main()
{
	int a,b,c,d,x1,y1,sum;
	while(~scanf("%d %d %d",&a,&b,&c))
	{
	//	if(a == 0 && b == 0)
	//	break;
		memset(xx,'#',sizeof(xx));
		getchar();
		for(int i = 1;i <= a;i++)
		{
			for(int j = 1;j <= b;j++)
			{
				xx[i][j] = getchar();
				if(xx[i][j] == 'S')
				{
					x1 = i;
					y1 = j;
				}
				else if(xx[i][j] != 'X')
				{
					bb[xx[i][j] - '0'][0] = i;
					bb[xx[i][j] - '0'][1] = j;
				}
			}
			getchar();
		}
		bb[0][0] = x1;
		bb[0][1] = y1;
		sum = 0;
		for(int i = 1;i <= c;i++)
		{
			vv.x = bb[i-1][0];
			vv.y = bb[i-1][1];
			memset(vis,-1,sizeof(vis));
			vis[vv.x][vv.y] = 0;
			qq.push(vv);
			sum += bfs(i + '0');
		}
		printf("%d\n",sum);
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX_H = 1000;
static const int MAX_W = 1000;
static const int MAX_N = 10;
static const int INF = 1 << 30;
typedef pair<int, int> P;

int H, W, N;
char s[MAX_H][MAX_W + 1];
P p[MAX_N];
int dist[MAX_H][MAX_W];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int bfs(int n, int m){
	queue<P> qa;
	fill(dist[0], dist[H], INF);
	qa.push(p[n]);
	dist[p[n].first][p[n].second] = 0;
	while(!qa.empty()){
		P t = qa.front(); qa.pop();
		if(t == p[m]) break;
		for(int i = 0; i < 4; i++){
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];
			if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
			if(s[nx][ny] == 'X') continue;
			if(dist[nx][ny] == INF){
				qa.push(make_pair(nx, ny));
				dist[nx][ny] = dist[t.first][t.second] + 1;
			}
		}
	}
	return dist[p[m].first][p[m].second];
}

int main(){
	cin >> H >> W >> N;
	for(int i = 0; i < H; i++){
		cin >> s[i];
		for(int j = 0; j < W; j++){
			if(s[i][j] == 'S'){
				p[0] = make_pair(i, j);
			}else if(s[i][j] >= '1' && s[i][j] <= '9'){
				p[s[i][j] - '0'] = make_pair(i, j);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		ans += bfs(i, i + 1);
	}
	cout << ans << endl;
	return 0;
}

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

typedef pair<int,int> P;

const int MAX = 1000, INF = 100000000;
char map[MAX][MAX+1];
int H, W, N;
int sx, sy;
int gx, gy;
int steps;
int d[MAX][MAX];

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

int bfs(){
	for(int i = 0; i < H; i++)
		for(int j = 0; j < W; j++) d[i][j] = INF;
	
	queue<P> que;
	que.push(P(sx,sy));
	d[sx][sy] = 0;
	
	while(que.size()){
		P p = que.front(); que.pop();
		
		if(p.first == gx && p.second == gy) break;
		
		for(int i = 0; i < 4; i++){
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if(nx >= 0 && nx < H && ny >= 0 && ny < W && map[nx][ny] != 'X' 
			&& d[nx][ny] == INF){
				que.push(P(nx,ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
		
	return d[gx][gy];
}

int main(){
	cin >> H >> W >> N;
	for(int i = 0; i < H; i++)
		cin >> map[i];
	
	steps = 0;
	int n = 0;
	while(n < N){
		for(int i = 0; i < H; i++)
			for(int j = 0; j < W; j++){
				if(map[i][j] == 'S' || map[i][j] == n + '0'){
					sx = i; sy = j;
				}
				if(map[i][j] == n + 1 + '0'){
					gx = i; gy = j;
				}
			}
		
		steps += bfs();
		n++;
	}
	cout << steps << endl;
	return 0;
}