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 <algorithm>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
#define rep(integer,n) for(int integer=0;integer<n;integer++)
#define mp make_pair
#define INF 100000000
typedef pair<int, int> P;

int h, w, n;
char maze[1000][1000];
int i, j;

struct DIR {
	int x, y;
} dir[4] = {
	{1, 0}, // right
	{0, 1}, // up
	{-1, 0}, // left
	{0, -1} // down
};

map<char, int> place;
int dist[1000][1000];

int bfs(int hp) {
	for(int x = 0; x < w; x++) {
		for(int y = 0; y < h; y++) {
			dist[y][x] = INF;
		}
	}
	dist[i][j] = 0;
	queue<P> q;
	q.push(mp(i,j));
	int ans = 0;
	while(!q.empty()) {
		int x = q.front().second;
		int y = q.front().first;
		q.pop();
		if(place[maze[y][x]] == hp) {
			i = y;
			j = x;
			maze[i][j] = '.';
			break;
		}
		for(int k = 0; k < 4; k++) {
			int nx = x + dir[k].x;
			int ny = y + dir[k].y;
			if(0 <= nx && nx < w && 0 <= ny && ny < h && maze[ny][nx] != 'X') {
				if(dist[ny][nx] == INF) {
					dist[ny][nx] = dist[y][x] + 1;
					q.push(mp(ny, nx));
				}
			}
		}
	}
	int ret = dist[i][j];
	return ret;
}

int main() {
	place.insert(mp('1', 1));
	place.insert(mp('2', 2));
	place.insert(mp('3', 3));
	place.insert(mp('4', 4));
	place.insert(mp('5', 5));
	place.insert(mp('6', 6));
	place.insert(mp('7', 7));
	place.insert(mp('8', 8));
	place.insert(mp('9', 9));
	place.insert(mp('.', 10));
	scanf(" %d %d %d", &h, &w, &n);
	rep(x, h) {
		scanf(" %s", &maze[x]);
	}
	int ans = 0;
	for(int x = 0; x < w; x++) {
		for(int y = 0; y < h; y++) {
			if(maze[y][x] == 'S') {
				i = y;
				j = x;
				maze[y][x] = '.';
				break;
			}
		}
	}
	rep(x,n) {
		ans += bfs(x + 1);
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

typedef pair<int, int> P;
const int MAX_N = 1010;
const int INF = 0x3f3f3f3f;

int H, W, N;
char M[MAX_N][MAX_N];

int si[10], sj[10];
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
int d[MAX_N][MAX_N];

int bfs(int m) {
  queue<P> que;
  for (int i = 1; i <= H; i++)
    for (int j = 1; j <= W; j++) d[i][j] = INF;
  d[si[m]][sj[m]] = 0;
  que.push(P(si[m], sj[m]));
  while (!que.empty()) {
    P p = que.front();
    que.pop();
    if (p.first == si[m + 1] && p.second == sj[m + 1]) break;
    for (int i = 0; i < 4; i++) {
      int ni = p.first + di[i], nj = p.second + dj[i];
      if (0 < ni && ni <= H && 0 < nj && nj <= W && M[ni][nj] != 'X' &&
          d[ni][nj] == INF) {
        que.push(P(ni, nj));
        d[ni][nj] = d[p.first][p.second] + 1;
      }
    }
  }
  return d[si[m + 1]][sj[m + 1]];
}

int main() {
  scanf("%d%d%d", &H, &W, &N);
  for (int i = 1; i <= H; i++) {
    char c;
    for (int j = 1; j <= W; j++) {
      do {
        c = getchar();
      } while (c == '\n' || c == ' ');
      if (c == 'S') {
        si[0] = i;
        sj[0] = j;
        c = '.';
      } else if (c >= '1' && c <= N + '0') {
        si[c - '0'] = i;
        sj[c - '0'] = j;
        c = '.';
      }
      M[i][j] = c;
    }
  }
  //   for (int i = 1; i <= H; i++) {
  //     for (int j = 1; j <= W; j++) putchar(M[i][j]);
  //     putchar('\n');
  //   }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += bfs(i);
  }
  printf("%d\n", ans);
  return 0;
}

C++: #include <cstdio>
#include <map>
#include <queue>
#include <string>

using namespace std;

const int INF = -1;
const int MAX_H = 1010;
const int MAX_W = 1010;
const int MAX_N = 10;

int H, W, N;
char field[MAX_H][MAX_W];
int d[MAX_H][MAX_W];
int sx, sy, gx, gy;
int power = 1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

typedef pair<int, int> P;

void reset_d() {
  for (int i = 0; i < H; i++)
    for(int j = 0; j < W; j++) d[i][j] = INF;
}

int bfs(int c) {
  queue<P> que;
  reset_d();
  d[sx][sy] = c;
  que.push(P(sx, sy));
  while(que.size()) {
    P p = que.front(); que.pop();
    for (int i = 0; i < 4; i++) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if ( 0 <= nx && nx <= H && 0 <= ny && ny <= W && field[nx][ny] != 'X' && d[nx][ny] == INF) {
        d[nx][ny] = d[p.first][p.second] + 1;
        que.push(P(nx, ny));
        if (field[nx][ny] - '0' == power) {
          sx = nx;
          sy = ny;
          power++;
          return d[nx][ny];
        }
      }
    }
  }
  return INF;
}

void solve() {
  int c = 0;
  for (int i = 0; i < N; i++) {
    c = bfs(c);
  }
  printf("%d\n", c);
}


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++) {
      if (field[i][j] == 'S') {
        sx = i;
        sy = j;
      }
      if (field[i][j] == 'G') {
        gx = i;
        gy = j;
      }
    }
  }
  solve();
  return 0;
}

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

#define F first
#define S second
#define FR q.front()

using namespace std;

typedef pair<int, int>Pt;

char map[1001][1001];
int zikan[1001][1001];
int mx[] = { 0,1,0,-1 };
int my[] = { 1,0,-1,0 };
pair<int, int> SG[10];
int n, h, w;
char tmp[] = { "S123456789" };

bool check(int, int);

int main() {

	cin >> h >> w >> n;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
			for (int l = 0; l <= n; l++) {
				if (map[i][j] == tmp[l]) SG[l] = make_pair(i, j);
			}

		}
	}

	//for (int i = 0; i <= n; i++) printf("%d %d\n",SG[i].F,SG[i].S);

	int minute = 0;
	for (int i = 0; i < n; i++) {
		queue<Pt> q;
		memset(zikan, -1, sizeof(zikan));
		q.push(SG[i]);
		zikan[SG[i].F][SG[i].S] = 0;
		while (!q.empty()) {
			if (q.front()==SG[i+1]) break;
			for (int l = 0; l < 4; l++) {
				if (check(mx[l] + FR.F, my[l] + FR.S)) {
					zikan[mx[l] + FR.F][my[l] + FR.S] = zikan[FR.F][FR.S] + 1;
					q.push(make_pair(mx[l] + FR.F, my[l] + FR.S));
				}
			}
			q.pop();
		}
		
		minute += zikan[SG[i+1].F][SG[i+1].S];

	}
	cout << minute << endl;
}

bool check(int i, int j) {
	if (i >= 0 && i < h && j >= 0 && j < w && map[i][j]!='X' && zikan[i][j]==-1) return true;
	return false;
}