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 <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

const int N = 1000;
const int INF = 0x3f3f3f3f;

int n, m, f;
char map[N][N+1];

bool legal(int x, int y, int k)
{
    return x >= 0 && x < n && y >= 0 && y < m
        && map[x][y] != 'X';
}

void input()
{
    cin >> n >> m >> f;
    for (int i = 0; i < n; i ++) {
        scanf("%s", map[i]);
    }
}

int BFS(int k)
{
    int i, j;
    int d[N][N];
    typedef pair<int, int> P;
    queue <P> q;
    for (i = 0; i < n; i ++) {
        for (j = 0; j < m; j ++) {
            d[i][j] = INF;
            if ((k == 0 && map[i][j] == 'S') || map[i][j] == '0'+k) {
                q.push(P(i, j));
                d[i][j] = 0;
                map[i][j] = '.';
            }
        }
    }

    while( q.size() ) {
        P p = q.front();
        q.pop();
        int x = p.first;
        int y = p.second;

        if (map[x][y] == INF)
            return d[x][y];

        int pos[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (i = 0; i < 4; i ++) {
            int nx = x + pos[i][0];
            int ny = y + pos[i][1];
            if (legal(nx, ny, k) && d[nx][ny] == INF) {
                q.push(P(nx, ny));
                d[nx][ny] = d[x][y]+1;
                if (map[nx][ny] == '0'+k+1) {
                    return d[nx][ny];
                }
            }
        }
    }

    return INF;
}

void solve()
{
    int res = 0;
    for (int i = 0; i < f; i ++) {
        res += BFS(i);
    }
    printf("%d\n", res);
}

int main(void)
{
    input();

    solve();

    return 0;
}

C++: #include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
struct T{
	ll first,second,third;
};
typedef double db;
string c[1001];
const ll INF = 0xffffffffff;
P s[10],g[10];
ll vx[4]={1,0,-1,0};
ll vy[4]={0,1,0,-1};
ll n,h,w;
bool visited[1001][1001];

ll bfs(ll sx,ll sy,ll gx,ll gy){
	queue<T> q;
	q.push((T){sx,sy,0});
	while(1){
		T t=q.front();
		q.pop();
		visited[t.second][t.first]=1;
		if(t.first==gx&&t.second==gy) return t.third;
		for(ll i=0;i<4;i++){
			ll nx=t.first+vx[i];
			ll ny=t.second+vy[i];
			if(0<=nx&&nx<w&&0<=ny&&ny<h&&c[ny][nx]=='.'&&!visited[ny][nx]) q.push((T){nx,ny,t.third+1});
		}
	}
}


int main()
{
	scanf("%lld%lld%lld",&h,&w,&n);
	for(ll i=0;i<h;i++) cin>>c[i];
	for(ll i=0;i<h;i++) for(ll j=0;j<w;j++){
		if(c[i][j]=='S'){
			s[0]=P(i,j);// y x
			c[i][j]='.';
		}
		if('1'<=c[i][j]&&c[i][j]<='9'){
			s[c[i][j]-'0']=P(i,j);
			g[c[i][j]-'1']=P(i,j);
			c[i][j]='.';
		}
	}
	ll ans=0;
	for(ll i=0;i<n;i++){
		fill(visited[0],visited[1000],0);
		ans+=bfs(s[i].second,s[i].first,g[i].second,g[i].first);
	}
	printf("%lld\n",ans);
}

C++: #include<iostream>
#include<queue>
using namespace std;
int W,H,N,A[10][2];
static char s[1000+2][1000+2];
const int INF=1000000000;
int muki[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int f(int x){
	queue<int> que;
	static int cost[1000+2][1000+2];
	for(int i=0;i<1002;i++)for(int j=0;j<1002;j++)cost[i][j]=INF;
	cost[A[x][0]][A[x][1]]=0;
	que.push(A[x][0]*1002+A[x][1]);
	while(cost[A[x+1][0]][A[x+1][1]]==INF){
		int c=que.front();
		int nY=c%1002,nX=(c-nY)/1002;
		for(int i=0;i<4;i++){
			if(s[nX+muki[i][0]][nY+muki[i][1]-1]!='X'&&cost[nX+muki[i][0]][nY+muki[i][1]]==INF){
				cost[nX+muki[i][0]][nY+muki[i][1]]=cost[nX][nY]+1;
				que.push((nX+muki[i][0])*1002+nY+muki[i][1]);
			}
		}
		que.pop();
	}
	return cost[A[x+1][0]][A[x+1][1]];
}

int main(){
	for(int i=0;i<1002;i++)for(int j=0;j<1002;j++)s[i][j]='X';
	scanf("%d%d%d",&W,&H,&N);
	for(int i=1;i<W+1;i++){
		scanf("%s",&s[i]);
		for(int j=0;j<H;j++){
			if(s[i][j]=='S'){A[0][0]=i; A[0][1]=j+1;}
			for(int k=1;k<N+1;k++){
				if(s[i][j]==k+48){A[k][0]=i; A[k][1]=j+1;}
			}
		}
	}
	int ans=0;
	for(int i=0;i<N;i++){
		ans+=f(i);
	}
	printf("%d\n",ans);
}

C++: #include <iostream>
#include <queue>
#include <cstdlib>
#define INF 1000000
using namespace std;
typedef pair<int,int> P;
int H,W,N;
char field[1000][1000];
int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
int d[1000][1000];
int ans=0;

void bfs(int sx,int sy,int n) {
  int x,y;
  queue<P> que;
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++) {
      d[i][j] = INF;
    }
  }
  que.push(P(sx,sy));
  d[sx][sy] = 0;

  while(!que.empty()) {
    P p = que.front();que.pop();
    x = p.first;y = p.second;
    if(field[x][y] == n+'1') break; //???
    for(int i=0;i<4;i++) {
      int nx = x+dx[i],ny = y+dy[i];
      if(0 <= nx && nx < H && 0 <= ny && ny < W && field[nx][ny] != 'X' && d[nx][ny] == INF) {
	que.push(P(nx,ny));
	d[nx][ny] = d[x][y]+1;
      }
    }
  }

  ans += d[x][y];
  if(n < 8)
    bfs(x,y,n+1);
  else
    return;
}

void solve() {
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++) {
      if(field[i][j] == 'S') {
	bfs(i,j,0);
	cout << ans << endl;
	return;
      }
    }
  }
}

int main() {
  string str;
  cin >> H >> W >> N;
  getline(cin,str);
  for(int i=0;i<H;i++) {
    getline(cin,str);
    for(int j=0;j<W;j++) {
      field[i][j] = *str.substr(j,1).c_str();
    }
  }
  solve();
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define maxx 1005
#define inf 0x7fffffff

struct Node {
	int x, y, s;
	Node() {}
	Node(int x, int y, int s) : x(x), y(y), s(s) {};
};

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

int h,w,n;
int ix, iy;
int ans;
char m[maxx][maxx];
bool a[maxx][maxx];

int bfs(char c) {
	int res;
	for(int i=0;i<h;i++) {
		for(int j=0;j<w;j++) a[i][j]=true;
	}
	queue<Node> q;
	q.push(Node(ix, iy, 0));

	while(!q.empty()) {
		Node p=q.front();
		q.pop();
		for(int i=0; i<4; i++) {
			int nx=p.x+dx[i], ny=p.y+dy[i];
			if(nx<0 || nx>=h || ny<0 || ny>=w || m[nx][ny]=='X' || a[nx][ny]==false) continue;//判断出界/碰壁
			else if(m[nx][ny]==c) {//结束条件
				ix=nx, iy=ny;
				res=p.s+1;
				return res;
			} else {
				q.push(Node(nx, ny, p.s+1));
				a[nx][ny]=false;
			}
		}
	}
}

int main() {
	scanf("%d %d %d",&h,&w,&n);
	for(int i=0; i<h; i++) {
		for(int j=0; j<w; j++) {
			cin>>m[i][j];
			if(m[i][j]=='S') ix=i, iy=j;
		}
	}
	ans=0;
	for(int i=1; i<=n; i++) {
		ans+=bfs('0'+i);
	}
	printf("%d\n",ans);

	return 0;
}