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: import sys
import numpy
sys.setrecursionlimit(1000000)

class MouseClass:
	def __init__(self):
		self.X = 0
		self.Y = 0
		self.LIFE = 1
		self.factoriesAble = []
		self.factoriesGone = []
		self.factoriesWill = []
		self.distance = 0

	def get_field(self, field:list):
		self.field = field

	def gen_factoriesInfo(self, factoriesInfo:list):
		self.factoriesAble = [i for i in factoriesInfo if i[2]<=self.LIFE]
		self.factoriesWill = [factory for factory in self.factoriesAble if factory not in self.factoriesGone]

	def findNearestFactory(self, factories:list):
		path = [abs(self.X-factory[0]) + abs(self.Y-factory[1]) for factory in factories]
		return factories[numpy.argmin(path)]

	def goFactory(self, factories:list):
		factory = self.findNearestFactory(factories)
		# print(abs(self.X-factory[0])+abs(self.Y-factory[1]))
		self.distance += self.calcShortestPath(self.X, self.Y, self.field, factory[0:2])
		self.X, self.Y = factory[0], factory[1]
		self.LIFE += 1
		self.factoriesGone.append(factory)

	def calcShortestPath(self, x:int, y:int, field:list, goal:list):
		print(x, y, goal)
		INF = 1000000
		d = []
		queue = []
		H = len(self.field)
		W = len(self.field[0])
		for _ in range(H):
			tmp = []
			for _ in range(W):
				tmp.append(INF)
			d.append(tmp)
				
		queue.append([x, y])
		d[x][y] = 0
		while len(queue)!=0:
			p = queue[0]
			queue.pop(0)
			if p==goal: break

			for dx in [-1, 0, 1]:
				if dx == -1: width = [0]
				if dx == 0: width = [-1, 1]
				if dx == 1: width = [0]
				for dy in width:
					nx = p[0]+dx
					ny = p[1]+dy
					if 0 <= nx < H and 0 <= ny < W:
						isObstacle = field[nx][ny] == "X"
						isNotVisited = d[nx][ny] == INF
						if (not isObstacle) and isNotVisited:
							queue.append([nx, ny])
							d[nx][ny] = d[p[0]][p[1]]+1
		return d[goal[0]][goal[1]] 

class FieldClass:
	def __init__(self):
		self.field = []
		self.Mouse = MouseClass()
		self.factoriesInfo = []

	def loadField(self):
		field = []
		i = 0
		H, W = 0, 0
		LINE_NUM = 0
		field = []
		while True:
			line = sys.stdin.readline().strip()
			LINE_NUM += 1
			if LINE_NUM == 1:
				line = line.split(" ")
				H, W = int(line[0]), int(line[1])
				continue
			self.field.append(list(line))
			if LINE_NUM == H+1: break

		self.Mouse.get_field(self.field)

	def initMousePos(self):
		H = len(self.field)
		W = len(self.field[0])
		for i in range(H):
			for j in range(W):
				if self.field[i][j] == "S":
					self.Mouse.X = i
					self.Mouse.Y = j

	def gen_factoriesInfo(self):
		NUM_LIST = [str(i) for i in range(10)]
		H = len(self.field)
		W = len(self.field[0])
		factories = []
		for i in range(H):
			for j in range(W):
				if self.field[i][j] in NUM_LIST:
					factories.append([i, j, int(self.field[i][j])])
		self.factoriesInfo = factories

Field = FieldClass()
Field.loadField()
Field.initMousePos()
Field.gen_factoriesInfo()

Field.Mouse.gen_factoriesInfo(Field.factoriesInfo)
while True:
	Field.Mouse.goFactory(Field.Mouse.factoriesWill)
	Field.Mouse.gen_factoriesInfo(Field.factoriesInfo)

	# print(Field.Mouse.factoriesAble)
	# print(Field.Mouse.factoriesGone)
	# print(Field.Mouse.factoriesWill)

	if len(Field.Mouse.factoriesGone) == 9: break
print(Field.Mouse.distance)

Python: from collections import deque
import copy
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        return True
    return False

h,w,n=map(int,raw_input().split())
g=[[] for _ in xrange(h)]
for i in xrange(h):
    r=raw_input()
    for j in xrange(w):
        if r[j]=="S":
             sy,sx=i,j
        g[i].append(r[j])
d=[[0]*w for i in xrange(h)]
d1=copy.deepcopy(d)
visited=[[0]*w for i in xrange(h)]
visited1=copy.deepcopy(visited)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
q=deque([[sy,sx]])
ans=0
for i in xrange(1,n+1):
    f=0
    while len(q)!=0:
        y,x=q.popleft()
        visited1[y][x]=2
        for j in xrange(4):
            nexty=y+dy[j]
            nextx=x+dx[j]
            if not check(nexty,nextx):continue
            if g[nexty][nextx]!="X" and visited1[nexty][nextx]==0:
                q.append([nexty,nextx])
                d1[nexty][nextx]=d1[y][x]+1
                visited1[nexty][nextx]=1
                if g[nexty][nextx]==str(i):
                    ans+=d1[nexty][nextx]
                    q=deque([[nexty,nextx]])
                    visited1=copy.deepcopy(visited)
                    d1=copy.deepcopy(d)
                    f=1
                    break
        if f==1:break
print(ans)

Python: def step(cheese):
    global x, y, a, d
    gone = set()
    q = [(x, y)]
    steps = 1
    while True:
        nq = []
        for i in q:
            for j in range(4):
                xy = (i[0] + d[j][0], i[1] + d[j][1])
                if a[xy[1]][xy[0]] == cheese:
                    x, y = xy
                    return steps
                elif xy not in gone and a[xy[1]][xy[0]] != "X":
                    gone.add(xy)
                    nq.append(xy)
        q = nq
        steps += 1

h, w, n = map(int, input().split())
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
a = ["X" * (w + 2)]
for _ in range(h):
    a.append("X" + input() + "X")
a.append("X" * (w + 2))
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j] == "S":
            x, y = j, i
            
steps = 0
for i in range(1, n + 1):        
    steps += step(str(i))
print(steps)

Python: from collections import deque
h,w,n = map(int,input().split())
factrys = [None] * (n + 1)
ss = ["X" * (w + 2)]
append = ss.append
for i in range(h):
  s = "X" + input() + "X"
  if "S" in s:
    factrys[0] = (i + 1, s.index("S"))
  for j in range(len(s)):
    if s[j] != 'S' and s[j] != '.' and s[j] != 'X':
      factrys[int(s[j])] = (i + 1, j)
  append(s)
append("X" * (w + 2))

def bfs(i):
  mp = [[False] * (w + 2) for j in range(h + 2)]
  x,y = factrys[i]
  que = deque()
  append = que.append
  popleft = que.popleft
  append((x, y))
  for count in range(1, 10000000):
    sz = len(que)
    for loop in range(sz):
      (x,y) = popleft()
      if ss[x][y] == 'X' or not mp[x][y]:
        continue
      if (x,y) == factrys[i + 1]:
        return count
      mp[x][y] = count
      append((x + 1, y))
      append((x - 1, y))
      append((x, y + 1))
      append((x, y - 1))

ans = 0
for i in range(n):
  ret = bfs(i)
  if ret is None:
    ans += 0
  else:
    ans += ret - 1
print(ans)

Python: from collections import deque
H,W,N=map(int,input().split())
e='X'*(W+2)
M=e+''.join('X'+input()+'X'for _ in[0]*H)+e
m=(1,-1,W+2,-W-2)
def f(s,g):
 p,t=s,0
 q=deque()
 b=[1]*len(M);b[s]=0
 while 1:
  for d in m:
   n=p+d
   if'X'!=M[n]and b[n]:
    if M[n]==g:return(n,t+1)
    b[n]=0;q.append([n,t+1])
  p,t=q.popleft()
s=M.find('S')
a=0
for i in range(1,N+1):
 s,t=f(s,str(i))
 a+=t
print(a)