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 <utility>
#include <queue>

using namespace std;

const int MAX_H=1000,MAX_W=1000;
const int INF=10000000;

int H,W,N;
char f[MAX_H][MAX_W+1];

typedef pair<int,int> P;

P fac[9];	//???????????\??´?????????
int d[MAX_H][MAX_W];

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

int bfs(P s,P g){
	//s??????g?????§??????????????¢
	//d????????????
	for (int i=0;i<H;i++){
		for (int j=0;j<W;j++){
			d[i][j]=INF;
		}
	}
	queue<P> que;
	//?§???????????????????0
	d[s.second][s.first]=0;
	que.push(s);
	while (!que.empty()){
		P p=que.front();
		que.pop();
		if (g==p){
			break;
		}
		//4???????????¢?´¢
		for (int i=0;i<4;i++){
			int x=p.first+dx[i],y=p.second+dy[i];
			if (x>=0 && x<W && y>=0 && y<H && f[y][x]!='X' && d[y][x]==INF){
				d[y][x]=d[p.second][p.first]+1;	//???????????´??°
				que.push(P(x,y));
			}
		}
	}
	return d[g.second][g.first];
}

int main(){
	cin>>H>>W>>N;
	P s;
	for (int i=0;i<H;i++){
		cin>>f[i];
		for (int j=0;j<W;j++){
			if ('1'<=f[i][j] && f[i][j]<='9'){
				fac[(int)(f[i][j]-'1')].first=j;
				fac[(int)(f[i][j]-'1')].second=i;
			}
			else if (f[i][j]=='S'){
				s.first=j;
				s.second=i;
			}
		}
	}
	int res=0;
	for (int i=0;i<N;i++){
		res+=bfs(s,fac[i]);
		s=fac[i];
	}
	cout<<res<<endl;
	return 0;
}

C++: #include<iostream>
#include<map>
#include<queue>
#include<string.h>

using namespace std;

typedef pair<int,int> P;
queue<P> q;
int sx,sy;
int gx,gy;
int g;
char field[1000][1000];
int d[1000][1000];
int H,W,N;
int hp=1;
int ans=0;

int bfs(){
	memset(d,-1,sizeof(d));
	P p;
	q.push(P(sx,sy));
	d[sx][sy]=0;
	while(q.size()){
		if(q.front().first==gx&&q.front().second==gy) break;
		p=q.front();
		q.pop();
		for(int i=-1;i<=1;i++){
			for(int j=-1;j<=1;j++){
				if((i==0||j==0)&&(i!=0||j!=0)){
					if(p.first+i>=0&&p.first+i<=H-1&&p.second+j>=0&&p.second+j<=W-1&&d[p.first+i][p.second+j]<0){
						if(field[p.first+i][p.second+j]!='X'){
							q.push(P(p.first+i,p.second+j));
							d[p.first+i][p.second+j]=d[p.first][p.second]+1;
						}
					}
				}
			}
		}
		
	}
	return d[gx][gy];
}
int main(){
	cin>>H>>W>>N;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin>>field[i][j];
		}
	}
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(field[i][j]=='S')
			{
				sx=i;
				sy=j;
			}
			if(field[i][j]==49)
			{
				gx=i;
				gy=j;
			}
		}
	}
	ans+=bfs();
	for(int i=0;i<N-1;i++){
		for(int j=0;j<H;j++){
			for(int k=0;k<W;k++){
				if(field[j][k]==49+i)
				{
					sx=j;
					sy=k;
				}
				if(field[j][k]==50+i)
				{
					gx=j;
					gy=k;
				}
			}
		}
		while(q.size()){
			q.pop();
		}
		memset(d,-1,sizeof(d));
		ans+=bfs();
	}

	cout<<ans<<endl;
}

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

#define fi first
#define se second
#define x second
#define y first

typedef pair<int,int> pii;

vector<string> in;
int H, W, N;

int search_length(char s, char g) {
	queue<pair<pii, int> > que;
	int vx[] = {1, -1, 0, 0};
	int vy[] = {0, 0, 1, -1};
	for(int i = 0; i < in.size(); i++) {
		for(int j = 0; j < in[i].size(); j++) {
			if(in[i][j] == s) {
				que.push(pair<pii, int>(pii(i, j), 0));
				j = in[i].size();
				i = in.size();
			}
		}
	}
	int visited[1024][1024] = {0};
	while(!que.empty()) {
		pair<pair<int,int>, int> tmp;
		tmp = que.front(); que.pop();
		for(int i = 0; i < 4; i++) {
			int x_, y_;
			x_ = tmp.fi.x + vx[i]; y_ = tmp.fi.y + vy[i];
			if(!(x_ < 0 || (int)in[0].size() <= x_ || y_ < 0 || (int)in.size() <= y_)) {
				if(in[y_][x_] == g) {
					return tmp.se + 1;
				}
				if(!visited[y_][x_] && in[y_][x_] != 'X') {
					visited[y_][x_] = 1;
					que.push(pair<pii,int>(pii(y_, x_), tmp.se + 1));
				}
			}
		}
	}
	cout << "reach" << endl;
	return -1;
}

int main() {
	cin >> H >> W >> N;
	int ret = 0;
	for(int i = 0; i < H; i++) {
		string tmp;
		cin >> tmp;
		in.push_back(tmp);
	}

	for(int i = 0; i < N; i++) {
		ret += search_length(i == 0 ? 'S' : (i + '0'), i + 1 + '0');
	}
	cout << ret << endl;
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void solve(vector<vector<char> >& board, int H, int W, int N, 
           int x, int y, int power, int count, int step, int& ret) {
  int prev_value = board[x][y];
  if (step >= ret) return;
  if (board[x][y] >= 1 && board[x][y] <= 9) {
    power++;
    count++;
    board[x][y] = '.';
    if (count == N) {
      ret = min(ret, step);
      board[x][y] = prev_value;
      return;
    }
  }

  //board[x][y] = 'X';
  for (int i = 0; i < 4; ++i) {
    int next_x = x + dir[i][0];
    int next_y = y + dir[i][1];
    if (next_x >= 0 && next_x < H
        && next_y >= 0 && next_y < W
        && board[next_x][next_y] != 'X') {
        if (board[next_x][next_y] >= 1 
            && board[next_x][next_y] < 9
            && power < board[next_x][next_y]) 
          continue;
        solve(board, H, W, N, next_x, next_y, power, count, step + 1, ret);
    }
  }
  board[x][y] = prev_value;
}

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  vector<vector<char> > board(H, vector<char>(W));
  char c;
  int x, y;
  for (int h = 0; h < H; ++h) {
    for (int w = 0; w < W; ++w) {
      cin >> c;
      if (c >= '1' && c <= '9') {
        c = c - '0';
      }
      board[h][w] = c;
      if (c == 'S') {
        x = h;
        y = w;
      }
    }
  }
  int ret = H * W;
  board[x][y] = '.';
  solve(board, H, W, N, x, y, 1, 0, 0, ret);
  cout << ret << endl;
}