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
# Your code here!

import sys
from queue import Queue
sys.setrecursionlimit(100000)

Delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = sys.maxsize

def bfs(start, target):
    d = [[INF] * w for i in range(h)]
    
    queue = Queue()
    queue.put(start)
    d[start[1]][start[0]] = 0

    while (queue.qsize()):
        p = queue.get()

        for delta in Delta:
            dx = p[0] + delta[0]
            dy = p[1] + delta[1]
            if not (0 <= dx and dx < w and 0 <= dy and dy < h):
                continue

            value = matrix[dy][dx]

            if value.isdigit() and value == target:
                return d[p[1]][p[0]] + 1, (dx, dy)

            if value != "X" and d[dy][dx] == INF:
                if value == "." or value == "S" or value.isdigit():
                    queue.put((dx, dy))
                    d[dy][dx] = d[p[1]][p[0]] + 1

    
def findStart(matrix):
    for j, row in enumerate(matrix):
        for i, cell in enumerate(row):
            if cell == "S":
                return (i, j)    

while (True):
    line = sys.stdin.readline().rstrip()
    if line == "":
        break

    h, w, c = (int(i) for i in line.split())

    matrix = []
    count = 0
    for i in range(h):
        matrix.append(list(input().rstrip()))
    
                
    start = findStart(matrix)
    for i in range(1, c+1):
        res, start = bfs(start, str(i))
        count += res 

    print(count)

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):
                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: h,w,n = map(int, input().split())
stage = [input() for i in range(h)]
starts = [str(i) for i in range(n)]
goals = [str(i+1) for i in range(n)]
starts_y = [0 for i in range(n)]
starts_x = [0 for i in range(n)]
goals_y = [0 for i in range(n)]
goals_x = [0 for i in range(n)]

starts[0] = "S"
for y in range(h):
	for x in range(w):
		if stage[y][x] in starts:
			starts_y[starts.index(stage[y][x])] = y
			starts_x[starts.index(stage[y][x])] = x
		if stage[y][x] in goals:
			goals_y[goals.index(stage[y][x])] = y
			goals_x[goals.index(stage[y][x])] = x

move_y = [1,-1,0,0]
move_x = [0,0,1,-1]
sum = 0

for start_y, start_x, goal_y, goal_x in zip(starts_y, starts_x, goals_y, goals_x):
	bfs_map = [[-1 for j in range(w)] for i in range(h)]
	data_y = [start_y]
	data_x = [start_x]
	bfs_map[start_y][start_x] = 0
	goal = False
	
	while len(data_y) != 0 and not goal:
		y = data_y.pop(0)
		x = data_x.pop(0)
		goal = False
	
		for i in range(4):
			ny = y + move_y[i]
			nx = x + move_x[i]
			
			if ny >= 0 and ny < h and nx >= 0 and nx < w:
				if bfs_map[ny][nx] == -1 and stage[ny][nx] != "x":
					bfs_map[ny][nx] = bfs_map[y][x]+1
					data_y.append(ny)
					data_x.append(nx)
			if bfs_map[goal_y][goal_x] != -1:
				sum += bfs_map[goal_y][goal_x]
				goal = True
				break

print(sum)

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: import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


diff_row = [-1,0,0,1]
diff_col = [0,-1,1,0]

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

def rangeCheck(row,col):
    global H,W
    return row >= 0 and row <= H-1 and col >= 0 and col <= W-1

loc = [None]*(N+1)

base_map = [input() for _ in range(H)]
for row in range(H):
    for col in range(W):
        if base_map[row][col] in ["." ,"X"]:
            continue
        if base_map[row][col] == "S":
            loc[0] = (row,col)
        else:
            loc[int(base_map[row][col])] = (row,col)

ans = 0
for i in range(N):
    start_row,start_col = loc[i]
    goal_row,goal_col = loc[i+1]
    table = [[BIG_NUM]*W for _ in range(H)]

    table[start_row][start_col] = 0
    Q = deque()
    Q.append((start_row,start_col))

    while len(Q) > 0:
        tmp_row,tmp_col = Q.popleft()

        if tmp_row == goal_row and tmp_col == goal_col:
            ans += table[goal_row][goal_col] #重みは全て1なので、最短経路は最初にgoalに到達するはず
            break

        for k in range(4):
            adj_row = tmp_row+diff_row[k]
            adj_col = tmp_col+diff_col[k]
            if rangeCheck(adj_row, adj_col) == False or base_map[adj_row][adj_col] == "X"  \
                    or table[adj_row][adj_col] <= table[tmp_row][tmp_col]+1:
                continue
            table[adj_row][adj_col] = table[tmp_row][tmp_col]+1
            Q.append((adj_row,adj_col))

print("%d"%(ans))