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 <set>
#include <iostream>

const int STEP_NUM = 4;
const int STEP[STEP_NUM][STEP_NUM] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

const int MAX_SIZE = 1000;
char field[MAX_SIZE + 1][MAX_SIZE + 1];

const int MAXN = 10;
int locationsX[MAXN];
int locationsY[MAXN];
 
int H, W, N;

int get_shortest_distance(int current_HP)
{
	int sx = locationsX[current_HP-1];
	int sy = locationsY[current_HP-1];
	int ex = locationsX[current_HP];
	int ey = locationsY[current_HP];

	bool is_visit[H + 1][W + 1];
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			is_visit[i][j]=false;

	std::set<std::pair<int,int>> frontier;
	frontier.insert(std::pair<int,int>{sx,sy});
	for(int step=0;step<100000000;step++)
	{
		for(auto p:frontier)
		{
			if(p.first==ex && p.second==ey)	return step;
			is_visit[p.first][p.second] = true;
		}
		std::set<std::pair<int,int>> next_frontier;
		for(auto p:frontier)
		{
			for(int i=0;i<STEP_NUM;i++)
			{
				int nx = p.first+STEP[i][0];
				int ny = p.second+STEP[i][1];
				if(nx<0 || H<=nx) 		continue;
				if(ny<0 || W<=ny) 		continue;
				if(field[nx][ny]=='X') 	continue;
				if(is_visit[nx][ny]) 	continue;
				next_frontier.insert(std::make_pair(nx,ny));
			}
		}
		frontier = next_frontier;
	}
	return -1;
}

int solve()
{
	int total_step = 0;
	for(int i=1;i<N+1;i++)
		total_step += get_shortest_distance(i);
	return total_step;
}

int main()
{
	scanf("%d %d %d", &H, &W, &N);
	for(int i=0; i<H; i++)
		scanf("%s", field[i]);
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
		{
			int HP=-1;
			if(field[i][j]=='S')	HP=0;
			if(field[i][j]=='1')	HP=1;
			if(field[i][j]=='2')	HP=2;
			if(field[i][j]=='3')	HP=3;
			if(field[i][j]=='4')	HP=4;
			if(field[i][j]=='5')	HP=5;
			if(field[i][j]=='6')	HP=6;
			if(field[i][j]=='7')	HP=7;
			if(field[i][j]=='8')	HP=8;
			if(field[i][j]=='9')	HP=9;
			if(HP!=-1)
			{
				locationsX[HP]=i;
				locationsY[HP]=j;
			}
		}
	printf("%d\n", solve());
	return 0;
}

C++: /* competitive programming circle traP */
/* template */
#include <stdio.h>
#include <queue>
using namespace std;

int h,w,n;
int px[11];
int py[11];
int mp[1000][1000];
bool used[1000][1000];
int dy[4] = {1,0,-1,0};
int dx[4] = {0,1,0,-1};

int bfs(int sy,int sx,int gy,int gx){
  for(int i=0;i<h;i++)for(int j=0;j<w;j++){
    used[i][j] = false;
  }
  queue<int> qy,qx,qd;
  used[sy][sx] = true;
  qy.push(sy); qx.push(sx); qd.push(0);
  while(!qy.empty()){
    int y,x,d;
    y = qy.front(); qy.pop();
    x = qx.front(); qx.pop();
    d = qd.front(); qd.pop();
    if(y==gy && x==gx)return d;
    for(int i=0;i<4;i++){
      int ny = y+dy[i];
      int nx = x+dx[i];
      int nd = d+1;
      if(ny<0 || nx<0 || ny>=h || nx>=w)continue;
      if(used[ny][nx])continue;
      if(mp[ny][nx] == 1)continue;
      used[ny][nx] = true;
      qy.push(ny); qx.push(nx); qd.push(nd);
    }
  }
  return -1;
}

int main(){
  scanf("%d%d%d",&h,&w,&n);
  for(int i=0;i<h;i++){
    char s[1001];
    scanf("%s",&s);
    for(int j=0;j<w;j++){
      char c = s[j];
      if(c=='X'){
        mp[i][j] = 1;
      }else{
        mp[i][j] = 0;
        if(c=='S'){
          py[0] = i;
          px[0] = j;
        }else if(c!='.'){
          py[c-'0'] = i;
          px[c-'0'] = j;
        }
      }
    }
  }
  int ans = 0;
  for(int i=0;i<n;i++){
    ans += bfs(py[i],px[i],py[i+1],px[i+1]);
  }
  printf("%d\n",ans);
  return 0;
}

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

struct node {
	int i;
	int j;
	char val;
};

int H, W, N;//H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)
char m[1001][1001];
queue<node> q;

bool flag = 0;
int t1 = 0;
char flag_m[1001][1001];
void search(int i, int j, char val)
{
	if (flag_m[i][j]<val) {
		if (m[i][j] == 'X')
		{
			return;
		}
		if (m[i][j] == '.' || m[i][j] != val)
		{
			q.push({ i,j,val });
			//flag_m[i][j] = true;
			t1++;
		}
		if (m[i][j] == val)
		{
			if (val == ('0' + N))
			{
				flag = 1;
			}
			else
			{
				q.push({ i,j,val + 1 });
				//flag_m[i][j] = true;
				m[i][j] = '.';
				t1++;
			}
		}
	}
	return;
}
int main()
{
	int si, sj;
	scanf("%d %d %d",&H,&W,&N);
	for (int i = 1;i <= H; i++)
	{
		getchar();
		for (int j = 1; j <= W; j++)
		{
			scanf("%c",&(m[i][j]));
			if (m[i][j] == 'S')
			{
				si = i;
				sj = j;
			}
		}
	}

	//
	
	q.push({si,sj,'1'});
	memset(flag_m,'0',sizeof(flag_m));
	int t = 1;
	int time=0;
	
	while (!q.empty() &&(!flag))
	{
		time++;
		t1 = 0;
		while (t-- &&(!flag))
		{
			node n1 = q.front(); q.pop();
			si = n1.i; sj = n1.j;
			flag_m[si][sj] = n1.val;
			if (si > 1)
			{
				search(si-1,sj,n1.val);
			}
			if (si < H)
			{
				search(si + 1, sj, n1.val);
			}
			if (sj > 1)
			{
				search(si, sj-1, n1.val);
			}
			if (sj < W)
			{
				search(si, sj+1, n1.val);
			}

		}
		t = t1;
	}
	printf("%d\n",time);
	return 1;
}

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

typedef struct{
 int x;
 int y;
}P;//表示坐标

char graph[1000][1000];
P aim[10];
P s,g;//s起点，g终点
int N,W,H;
int vis[1000][1000]; //用来存储距离
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int bfs(P s,P g);

int main(){
    int i,j,t,step=0;
    cin>>H>>W>>N;
    
    for(i=0;i<H;i++)
    for(j=0;j<W;j++){
        cin>>graph[i][j];
      if(graph[i][j]<='9'&&graph[i][j]>='1'){ 
         t=graph[i][j]-'0';
         aim[t].x=i;
         aim[t].y=j;
      } //把1-N的坐标保存在 aim数组中 
      else if(graph[i][j]=='S'){
          s.x=i;
          s.y=j;
          graph[i][j]='.';
      }//得到最初的起点 
    }
    
    for(i=1;i<=N;i++){
       g.x=aim[i].x;
       g.y=aim[i].y;//1-N ，从小到大，每次把一个 作为终点 
       step+=bfs(s,g);
       s.x=g.x;
       s.y=g.y;//到达这个终点后变终点为起点 
       graph[g.x][g.y]='.';
    }
   
    cout<<step<<endl;
}

int bfs(P s,P g){
    queue<P> que;
      P n;
    
    for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
     vis[i][j]=-1;
     
     que.push(s);
     vis[s.x][s.y]=0;
     
     while(que.size()){
         
       P p=que.front();
         que.pop();
       if(p.x==g.x&&p.y==g.y)
       break;
       
       for(int i=0;i<4;i++){
           n.x=p.x+dx[i];
           n.y=p.y+dy[i];//向四方漫射 
        if(0<=n.x&&n.x<H&&0<=n.y&&n.y<W&&graph[n.x][n.y]!='X'&&vis[n.x][n.y]==-1){
               que.push(n);
               vis[n.x][n.y]=vis[p.x][p.y]+1;
           }
       }
   }
     return vis[g.x][g.y];
}