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<stdio.h>
#include<queue>
using namespace std;
char sz[1001][1001];
int a,b,c;
struct node{
  int x,y;	
};
typedef struct node Node;
queue<Node>Q;
int bfs(struct node T,int k){
	int cnt=0,flag=1,Flag=1;
	Node vb;
	while(!Q.empty()){
		flag=Flag;
		Flag=0;
	for(int i=0;i<flag;i++){
	for(int dr=-1;dr<=1;dr++){
		for(int dc=-1;dc<=1;dc++){
			if((dc!=0||dr!=0)&&dr*dc==0){
			int xx=Q.front().x+dr;
			int yy=Q.front().y+dc;
			if(xx>=0&&xx<a&&yy>=0&&yy<b){
			if(sz[xx][yy]=='.'||sz[xx][yy]!=k+'0'&&sz[xx][yy]!='X'){
				vb.x =xx;
				vb.y =yy;
				Q.push(vb);
				Flag++;
				sz[xx][yy]=k+'0';
			}
		   if(xx==T.x&&yy==T.y){
		   	while(!Q.empty())Q.pop();
		   	return cnt+1;
		   }
		}
			}
		}
	}
	Q.pop();
}
cnt++;
}
return cnt;
}
int main(){
	
	struct node st[10];
	while(scanf("%d%d%d",&a,&b,&c)){
		getchar();
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				scanf("%c",&sz[i][j]);
				if(sz[i][j]=='S'){ st[0].x=i;st[0].y=j;sz[i][j]='0';}
				if(sz[i][j]>'0'&&sz[i][j]<='9'){st[sz[i][j]-'0'].x=i;st[sz[i][j]-'0'].y =j;}
			}
			getchar();
		}
		int count=0;
		for(int i=1;i<=c;i++){
			Q.push(st[i-1]);
			count+=bfs(st[i],i-1);
		}
		printf("%d\n",count);
	}
	
}

C++: //AOJ-0558
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

char map[1010][1010];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int vis[1010][1010];
int m, n, N;
struct node{
	int x, y, t;
};

node bfs(int x, int y, int k)
{
	memset(vis, 0, sizeof(vis));
	queue<node> q;
	vis[x][y] = 1;
	node s; s.x = x; s.y = y; s.t = 0;
	q.push(s);
	while(!q.empty())
	{
		node p = q.front(); q.pop();
		vis[p.x][p.y] = 1;
		node e;
		if(map[p.x][p.y] == k + '0') return p;
		for(int i = 0; i < 4; i++)
		{
			e.x = p.x + dx[i];
			e.y = p.y + dy[i];
			if(map[e.x][e.y] == 'X' || vis[e.x][e.y] == 1) continue;
			e.t = p.t + 1;
			q.push(e);
		}
	}
	s.x = s.y = s.t = -1;
	return s;
}
void clear(){
	for(int i = 0; i < 1010; i++)
	  for(int j = 0; j < 1010; j++)
	    map[i][j] = 'X';
}
int main()
{
	while(scanf("%d %d %d", &n, &m, &N) != EOF)
	{
		clear();
		node s;
		for(int i = 1; i <= n; i++){
			getchar();
			for(int j = 1; j <= m; j++){
			   map[i][j] = getchar();
			   if(map[i][j] == 'S'){
			   	 map[i][j] = '.';
			   	 s.x = i; s.y = j; s.t = 0;
			   }
			}	
		}
		int ans = 0;
		for(int i = 1; i <= N; i++)
		{
			s = bfs(s.x, s.y, i);
			map[s.x][s.y] = '.';
			ans += s.t;
		}
		printf("%d\n", ans);
	}
	return 0; 
}

C++: #include <iostream>
#include <queue>
#include <string>

using namespace std;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int First = 1000;
int w,h,n;
int ans = 0;
int d[1001][1001];
typedef struct p{
	int x, y;
}P;
string mapp[1001];
P nezumi[11];


//幅優先探索を行う
void bfs(){
	for(int i=1 ; i <= n ; i++ ){
		P sp = nezumi[i-1];
		int sx = nezumi[i-1].x;
		int sy = nezumi[i-1].y;
		int gx = nezumi[i].x;
		int gy = nezumi[i].y;

		//二次元配列の初期化をする
		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				d[y][x] = First;
			}
		}
		
		queue<P> q;
		q.push( sp );
		d[sy][sx] = 0;
		while( !q.empty() ){
			P now = q.front();
			q.pop();
			int x = now.x;
			int y = now.y;

			if( x == gx && y == gy ){
				ans += d[gy][gx];

				/*動作確認
				cout << "\n";
				for(int y=0 ; y < h ; y++ ){
					for(int x=0 ; x < w ; x++ ){
						if (d[y][x]==First){cout << "X";}
							else{cout << d[y][x];}
					}
					cout << "\n";
				}*/
				break;
			}

			//redandblackと同じように探索
			for(int i=0 ; i < 4 ; i++ ){
				int newx = x + dx[i];
				int newy = y + dy[i];
				if( newx < 0 || newy < 0 || newx >= w || newy >= h ) continue;
				if( mapp[newy][newx] != 'X' ){
					P next;
					next.x = newx;
					next.y = newy;
					if( d[newy][newx] == First ){
						d[newy][newx] = d[y][x] + 1;
						q.push( next );
					}
				}
			}
		}
	}
}

int main(){
	//標準入力
	cin >> h >> w >> n;
	for(int y=0 ; y < h ; y++ ){
		cin >> mapp[y];
	}
	
	//スタートと数字の確認
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			char c = mapp[y][x];

			//アスキー使っていい感じにしてみる
			if( c >= '1' && c <= '9' ){
				nezumi[ c - '0' ].x = x;
				nezumi[ c - '0' ].y = y;
			}
			if(c == 'S'){
				nezumi[0].x = x;
				nezumi[0].y = y;
			}
		}
	}
	bfs();
	cout << ans << endl;
}

C++: #include <iostream>
#include <queue>
#include <map>

#define rep(i, a, b) for(int i = (a); (i) < (b); (i)++)
#define ft first
#define sd second

using namespace std;

char m[1000][1000];
int dis[1000][1000];
queue<pair<int, int> > state;

int main() {
  int h, w, n;

  cin >> h >> w >> n;

  int sx, sy;
  rep(i, 0, h) {
    rep(j, 0, w) {
      cin >> m[j][i];
      if(m[j][i] == 'S') {
	sx = j;
	sy = i;
      }
    }
  }

  pair<int, int> p;
  p.ft = sx;
  p.sd = sy;

  rep(i, 0, h) {
    rep(j, 0, w) {
      dis[j][i] = -1;
    }
  }
  dis[sx][sy] = 0;
  state.push(p);

  int dx[4] = {-1,   0,  1, 0};
  int dy[4] = { 0,  -1,  0, 1};
  int map2[1000][1000];
  for(int lp = 1; lp <= n; lp ++) {
    rep(i, 0, h) {
      rep(j, 0, w) {
	map2[j][i] = 0;
      }
    }

    map2[sx][sy] = 1;
    while(state.size()) {
      pair<int, int> now = state.front();
      state.pop();
      if(m[now.ft][now.sd] - '0' == lp) {
	sx = now.ft;
	sy = now.sd;
	break;
      }
      
      rep(lp2, 0, 4) {
	int x = now.ft+dx[lp2];
	int y = now.sd+dy[lp2];
	
	if(x < 0 || w <= x || y < 0 || h <= y) continue;
	if(map2[x][y] == 0 && m[x][y] != 'X') {
	  state.push(make_pair(x, y));
	  dis[x][y] = dis[now.ft][now.sd] + 1;
	  map2[x][y] = 1;
	}
      }
    }
    while(state.size()) state.pop();

    state.push(make_pair(sx, sy));
  }

  cout << dis[sx][sy] << endl;
  return 0;
}