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>
#define MAX 1005
#define INF 100000000

using namespace std;

typedef struct{
    int x;
    int y;
    int state;
} Mouse;

int H,W,N;
int start_x,start_y;
char ar[MAX][MAX];
int offset_x[4] = {1,0,-1,0};
int offset_y[4] = {0,1,0,-1};
int ans[MAX][MAX];

void init(){
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            ans[i][j] = -INF;
}

int bfs(int state){

    Mouse m;
    m.x = start_x;
    m.y = start_y;
    m.state = state;

    init();

    ans[start_y][start_x] = 0;

    queue<Mouse> q;
    q.push(m);

    while(q.size()){
        Mouse m1 = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int dx = m1.x + offset_x[i];
            int dy = m1.y + offset_y[i];
            if(dx >= 0 && dx < W && dy >= 0 && dy < H && ar[dy][dx] != 'X' && ans[dy][dx] == -INF){
                Mouse m2;
                m2.x = dx;
                m2.y = dy;

                ans[dy][dx] = ans[m1.y][m1.x] + 1;

                if(m1.state == (ar[dy][dx] - '0')){
                    ar[dy][dx] == '.';
                    start_x = dx;
                    start_y = dy;
                    return ans[dy][dx];
                }else{
                    m2.state = m1.state;
                }
                q.push(m2);
            }
        }
    }




}

int main(){

    while(cin >> H >> W >> N){
        for(int i = 0; i < H; i++){
            cin >> ar[i];
            for(int j = 0; j < W; j++){
                if(ar[i][j] == 'S'){
                    start_y = i;
                    start_x = j;
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= N; i++)
            res += bfs(i);
        cout << res << endl;
    }

 return 0;
}

C++: #include<stdlib.h>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<time.h>
#include<queue>
using namespace std;
#define INF 100000
char map[1001][1001];
int h,w,n;
int d1[4]={0,1,0,-1};
int d2[4]={1,0,-1,0};
int i,j,x[10],y[10];
int bfs(int num){
	int gy=y[num+1],gx=x[num+1];
	int d[1001][1001];
	for(int i=0;i<1001;i++){
		for(int j=0;j<1001;j++){
			d[i][j]=INF;
		}
	}
	queue<int> qx;queue<int> qy; 
	qx.push(x[num]);qy.push(y[num]);
	d[y[num]][x[num]]=0;
	while(qx.size()+qy.size()!=0){
		int ny,nx;
		ny=qy.front();qy.pop();
		nx=qx.front();qx.pop();
		if(ny==gy&&nx==gx){
			break;
		}
		for(int i=0;i<4;i++){
			int mx=nx+d1[i],my=ny+d2[i];
			if(0<=mx&&mx<w&&0<=my&&my<h&&map[my][mx]!='X'&&d[my][mx]==INF){
				d[my][mx]=d[ny][nx]+1;
				qx.push(mx);
				qy.push(my);
			}
		}
	}
	return d[gy][gx];
}
int main(){
	int ans=0;
	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'){
				y[0]=i;x[0]=j;
			}else if('0'<map[i][j]&&map[i][j]<='9'){
				y[(int)(map[i][j]-'0')]=i;
				x[(int)(map[i][j]-'0')]=j;
			}
		}
	}

	for(int i=0;i<n;i++){
		ans+=bfs(i);
	}
	
	cout<<ans<<endl;
	return 0;
}

C++: #include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn=1005;
int n,m,k,dx[]={-1,1,0,0},dy[]={0,0,1,-1},vis[maxn][maxn];
char map[maxn][maxn];
struct maze
{
    maze(int xx=0,int yy=0,int tt=0):x(xx),y(yy),time(tt){}
	int x,y,time;
};
maze bfs(int bx,int by,char ch)
{
	memset(vis,0,sizeof(vis));
	queue<maze> q;
	maze st(bx,by,0);
	q.push(st);vis[bx][by]=1;
	while(!q.empty())
	{
		st=q.front();q.pop();
		if(map[st.x][st.y]==ch)
		{
			return st;
		}
		for(int i=0;i<4;++i)
		{
			int tx=st.x+dx[i],ty=st.y+dy[i];
			if(tx<0||tx>=n||ty<0||ty>=m||map[tx][ty]=='X')//越界和?
			{
				continue;
			}
			maze tp(tx,ty,st.time+1);
			if(!vis[tx][ty])
			{
				vis[tx][ty]=1;
				q.push(tp);
			}
		}
	}
}
int main()
{

	while(~scanf("%d%d%d",&n,&m,&k))
	{
		int bx,by;
		for(int i=0;i<n;++i)
		{
			scanf("%s",map[i]);
			for(int j=0;j<m;++j)
			{
				if(map[i][j]=='S')
				{
					bx=i;by=j;
					
					map[i][j]='0'; //第0个起点
				}
			}
		}
		int ans=0;
		for(int i=0;i<k;++i)
		{
			maze tp=bfs(bx,by,map[bx][by]+1);
			ans+=tp.time;
			bx=tp.x;by=tp.y;
		}
		printf("%d\n",ans);
	}
	return 0;
}

C++: #include <iostream>
#include <queue>
#include <climits>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

typedef pair<int,int> pii;

int main()
{
  int H, W, N;
  const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
  cin >> H >> W >> N;
  char map[H][W];
  int d[N][H][W], hp = 1, ans = 0;
  fill(d[0][0],d[N][0],INT_MAX);
  queue<pii> q;
  REP(i,H){
    REP(j,W){
      cin >> map[i][j];
      if(map[i][j] == 'S'){
        q.push({i,j});
        d[hp-1][i][j] = 0;
      }
    }
  }
  while(1){
    pii p = q.front();
    q.pop();
    if(hp == map[p.first][p.second]-'0'){
      ans += d[hp-1][p.first][p.second];
      hp++;
      d[hp-1][p.first][p.second] = 0;
      while(!q.empty()) q.pop();
    }
    if(hp == N+1){
      cout << ans << endl;
      return 0;
    }
    REP(i,4){
      pii next_p = {p.first+dx[i],p.second+dy[i]};
      if(next_p.first < 0 || next_p.first >= H || next_p.second < 0 || next_p.second >= W || map[next_p.first][next_p.second] == 'X') continue;
      if(d[hp-1][next_p.first][next_p.second] > d[hp-1][p.first][p.second]+1){
        d[hp-1][next_p.first][next_p.second] = d[hp-1][p.first][p.second]+1;
        q.push(next_p);
      }
    }
  }
}

C++: /*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1000;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct QUEUE{
	int x,y,dep;
	QUEUE(){}
	QUEUE(int _x,int _y,int _dep){x=_x;y=_y;dep=_dep;}
};
int r,c,n;
int goal[10][2];
bool vis[MAXN+5][MAXN+5];
char maz[MAXN+5][MAXN+5];
int BFS(int *beg,int cnt){
	memset(vis,false,sizeof vis);
	queue<QUEUE> que;
	que.push(QUEUE(beg[0],beg[1],0));
	while(!que.empty())
	{
		QUEUE pre=que.front();que.pop();
		for(int i=0;i<4;i++)
		{
			int X=pre.x+dir[i][0],Y=pre.y+dir[i][1],depth=pre.dep+1;
			if(X<1 || X>r || Y<1 || Y>c || maz[X][Y]=='X' || vis[X][Y]) continue;
			vis[X][Y]=true;
			if(X==goal[cnt][0] && Y==goal[cnt][1])
				return depth;
			que.push(QUEUE(X,Y,depth));
		}
	}
	return -1;
}
int main(){
	scanf("%d%d%d",&r,&c,&n);
	for(int i=1;i<=r;i++)
	{
		scanf("%s",maz[i]+1);
		for(int j=1;j<=c;j++)
		{
			if('1'<=maz[i][j] && maz[i][j]<='9')
				goal[maz[i][j]-'0'][0]=i,
				goal[maz[i][j]-'0'][1]=j,
				maz[i][j]='.';
			if(maz[i][j]=='S')
				goal[0][0]=i,
				goal[0][1]=j,
				maz[i][j]='.';
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=BFS(goal[i-1],i);
	printf("%d\n",ans);
	return 0;
}//