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>
using namespace std;
int h,w,n;
char map[1010][1010];
class Node{
    public:
    int x,y,cost;
    Node(int x,int y,int cost):x(x),y(y),cost(cost){}
    Node(){}
};
int bfs(char s,char e)
{
    bool flag[1010][1010]={{false}};
    queue<Node> Q;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(map[i][j]==s)Q.push(Node(j,i,0));
        }
    }
    while(!Q.empty())
    {
        Node t=Q.front();Q.pop();
        if(map[t.y][t.x]==e)return t.cost;
        if(flag[t.y][t.x])continue;
        int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
        for(int i=0;i<4;++i){
            Node next=t;
            next.cost++;
            next.x+=dx[i];next.y+=dy[i];
            if(next.x>=0&next.x<w&next.y>=0&next.y<h&map[next.y][next.x]!='X')Q.push(next);
        }
        flag[t.y][t.x]=true;
    }
}
int main()
{
    cin>>h>>w>>n;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            cin>>map[i][j];
        }
    }
    int ans=0;
    char f=n+'0';
    ans+=bfs('S','1');
    for(char i='1';i<f;++i){
        ans+=bfs(i,i+1);
    }
    cout<<ans<<endl;
    return 0;
}

C++: #include<iostream>
#include<queue>
using namespace std;
struct Point{int x,y,dist;};
int main()
{
  int H,W,N;
  char vital='1';
  int i,j;
  char field[1001][1001];
  bool visited[1000][1000];
  queue<Point>q;
  int dx[4]={0,1,0,-1};
  int dy[4]={-1,0,1,0};
  Point ans;

  cin>>H>>W>>N;
  for(i=0;i<H;i++)cin>>field[i];
  for(i=0;i<H;i++){
    for(j=0;j<W;j++){
      if(field[i][j]=='S'){
	Point p={j,i,0};
	q.push(p);
      }
    }
  }
  for(i=0;i<H;i++)for(j=0;j<W;j++)visited[i][j]=false;

  while(q.size()){
    Point p=q.front();
    q.pop();
    visited[p.y][p.x]=true;
    for(i=0;i<4;i++){
      Point p2;
      p2.y=p.y+dy[i];
      p2.x=p.x+dx[i];
      p2.dist=p.dist+1;
      if(p2.y<0||H<=p2.y)continue;
      if(p2.x<0||W<=p2.x)continue;
      if(field[p2.y][p2.x]=='X')continue;
      if(visited[p2.y][p2.x])continue;
      if(field[p2.y][p2.x]==vital){
	vital++;
	while(q.size())q.pop();
	for(i=0;i<H;i++)for(j=0;j<W;j++)visited[i][j]=false;
	if(vital-'0'==N+1){
	  ans=p;
	  break;
	}
      }
      q.push(p2);
    }
  }
  cout<<ans.dist+1<<endl;
}

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

typedef pair<int, int> P;

const int MAX_H = 1000, MAX_W = 1000;
const int INF = 100000000;
int H, W, N;
char field[MAX_H][MAX_W];
int d[MAX_H][MAX_W];
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int result = 0;
P start, goal;

int bfs(P start, P goal);

int main(){
	cin >> H;
	cin >> W;
	cin >> N;
	for(int i=0; i<H; i++){
		cin >> field[i];
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			if(field[i][j] == 'S'){
				goal.first = i;
				goal.second = j;
			}
		}
	}

	for(int n=1; n<=N; n++){
		start.first = goal.first;
		start.second = goal.second;

		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++){
				if(field[i][j] == n+'0'){
					goal.first = i;
					goal.second = j;
				}
			}
		}
		result += bfs(start, goal);
	}

	cout << result << endl;

	return 0;
}

int bfs(P start, P goal){
	for(int i=0; i<MAX_H; i++)
		for(int j=0; j<MAX_W; j++) d[i][j] = INF;

	queue<P> que;
	que.push(start);
	d[start.first][start.second] = 0;

	while(que.size()){
		P p = que.front();
		que.pop();

		if(p.first==goal.first && p.second==goal.second) break;

		for(int i=0; i<4; i++){
			int xnew = p.first + dx[i];
			int ynew = p.second + dy[i];

			if(0<=xnew && xnew<H && 0<=ynew && ynew<W && field[xnew][ynew]!='X' && d[xnew][ynew]==INF){
				que.push(P(xnew, ynew));
				d[xnew][ynew] = d[p.first][p.second] + 1;
			}
		}
	}

	return d[goal.first][goal.second];
}

C++: #include <cstdio>
#include <cctype>
#include <vector>
#include <queue>

using namespace std;

char s[1000][1000];

char state[1000][1000];

int H, W, N;


int main()
{
	//freopen("in.txt", "r", stdin);

	while (scanf("%d%d%d", &H, &W, &N)==3) {
		if (H==0 && W==0) break;
		int i, j;
		char c;
		int si, sj;

		for (i=0; i<H; i++) {
			for (j=0; j<W; j++) {
				do { c=getchar();
				} while (c!='.' && c!='S' && c!='X' && !isdigit(c));
				s[i][j] = c;
				if (c=='S') {
					si = i; sj = j;
				}
			}
		}

		memset(state, 0, sizeof(state));
		state[si][sj] = 1;
		
		int step=0;
		int want=1;
		queue<int> q1, q2, *q, *nq, *qtmp;

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

		q = &q1; nq = &q2;
		q1.push((si<<16)|sj);

		while (want<=N) {
			int old_want=want;
			while (!nq->empty()) nq->pop();
			step++;
			while (!q->empty()) {
				
				int i, j, value;
				value = q->front(); q->pop();
				i = value>>16; j = value&0xffff;

				int k;
				for (k=0; k<4; k++) {
					int ti, tj;
					ti = i+dy[k]; tj = j+dx[k];
					if (ti<0 || ti>=H || tj<0 || tj>=W || s[ti][tj]=='X') continue;
					if (state[ti][tj]==want) continue;
					if (s[ti][tj]==want+'0') {
						want++; 
					}
					
					state[ti][tj] = want;
					nq->push((ti<<16)|tj);
					if (want!=old_want) break;
				}
				if (want!=old_want) break;
			}

			if (want!=old_want) {
				while (nq->size()>1) nq->pop();
			}

			qtmp = q; q = nq; nq = qtmp;



		}

		printf("%d\n", step);

	}

	return 0;
}