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)
}

Python: # -*- coding: utf-8 -*-

from queue import Queue

h,w,n = map(int,input().split())
map = [[0] * w for _ in range(h)]
for i in range(h):
    map[i] = list(input())

que = Queue()
ans = 0
checked = [[-1] * w for _ in range(h)]

def bfs():
    global que,ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == g[0] and xy[1] == g[1]:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                else:
                    if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                        if checked[xy[1]+j][xy[0]+i] == -1 and map[xy[1]+j][xy[0]+i] != "X":
                            checked[xy[1]+j][xy[0]+i] = checked[xy[1]][xy[0]] + 1
                            que.put([xy[0]+i,xy[1]+j])

mark = [[0,0] for _ in range(n+1)]
for i in range(h):
    for j in range(w):
        for k in range(1,n+1):
            if map[i][j] == str(k):
                mark[k] = [j,i]
            elif map[i][j] == "S":
                mark[0] = [j,i]

cnt = 0
for i in range(1,len(mark)):
    que = Queue()
    que.put([mark[i-1][0],mark[i-1][1]])
    g = [mark[i][0],mark[i][1]]
    ans = 0
    checked = [[-1] * w for _ in range(h)]
    checked[mark[i-1][1]][mark[i-1][0]] = 0
    bfs()
    cnt += ans

print(cnt)

Python: def bfs(count, x, y, cheese):
    queue = [(count,x,y)]
    while len(queue)>0:
        tempc,tempx,tempy = queue.pop(0)
        if geo[tempx][tempy] == cheese:
            return tempc,tempx,tempy
        for i in range(4):
            neox = tempx+dx[i]
            neoy = tempy+dy[i]
            if canGoTo(neox,neoy):
                if (tempc+1,neox,neoy) not in queue:
                    queue.append((tempc+1,neox,neoy))

    return (-1,-1,-1)

def canGoTo(x,y):
    if 0<=x<H and 0<=y<W:
        return not visited[x][y]
    return False

dx = [0,1,0,-1]
dy = [-1,0,1,0]

data = input().split(' ')
H,W,N = map(int, data)

#maps
geo = [[None for i in range(W)] for j in range(H)]
visited = [[False for i in range(W)] for j in range(H)]

x,y=-1,-1
for i in range(H):
    line = input()
    for j in range(W):
        p = line[j:j+1]
        geo[i][j] = p
        if p == 'X':
            visited[i][j] = True
        elif p == 'S':
            x,y, = i,j
            
count = 0
for n in range(1,N+1):
    count,x,y = bfs(count,x,y,str(n))
print(count)

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = map(int,input().split(" "))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)