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: field = [[4,5,2],[".","X",".",".",1],[".",".",".",".","X"],[".","X","X",".","S"],[".",2,".","X","."]]

for i in range(len(field) - 1):
    for j in range(len(field[1])):
        if field[i+1][j] == "S":
            start_x = j
            start_y = i + 1
            break
# print(start_x,start_y)

def proceed(field,start_x,start_y,start_n,start_N,goal_N):
    # print("start[x]",start_x)
    # print("start[y]",start_y)
    x = [-1,0,1,0]
    y = [0,-1,0,1]
    next_x = []
    next_y = []
    next_N  = []
    # print("s_parameters",start_x,start_y,start_N,start_n,goal_N)

    for s_x,s_y,s_N in zip(start_x,start_y,start_N):
        for p_x,p_y in zip(x,y):
            if 1 <= s_y + p_y < len(field):
                #print("y",s_y + p_y)
                if 0 <= s_x + p_x < len(field[1]):
                    #print("x",s_x + p_x)
                    if field[s_y + p_y][s_x + p_x] != "X":
                        # print("x",s_x + p_x)
                        # print("y",s_y + p_y)
                        next_x.append(s_x + p_x)
                        next_y.append(s_y + p_y)
                        # print("[x]",next_x)
                        # print("[y]",next_y)
                        if field[s_y + p_y][s_x + p_x] == goal_N:
                            # print("GOAL_STATE",s_N)
                            next_N.append(s_N)
                            if s_N == goal_N:
                                # print("check",s_N,goal_N,start_N)
                                print("result",start_n + 1)
                                return  ## return None except 1
                        elif field[s_y + p_y][s_x + p_x] == s_N:
                                next_N.append(s_N + 1)
                                # print("EAT CHEESE",next_N)
                        else:
                            next_N.append(s_N)
    # print("next_N",next_N)
    next_n = start_n + 1
    proceed(field,next_x,next_y,next_n,next_N,goal_N)

proceed(field,[start_x],[start_y],0,[1],field[0][2])

Python: import  copy
h = w = 0
mymap =[]
const_mymap = []
qlist = []
ans = 0
def bfs(n):
    while True:
        if len(qlist) != 0:
            temp = qlist.pop(0)
            x = temp[0]
            y = temp[1]
            deep = temp[2]

            #print(temp)
            if mymap[y][x] == str(n):

                return temp
            mymap[y] = mymap[y][:x] + '*' + mymap[y][x + 1:]

            if x + 1 < w:
                if mymap[y][x + 1] not in '*X':
                    qlist.append([x + 1, y, deep + 1])
            if x - 1 >= 0:
                if mymap[y][x - 1] not in '*X':
                    qlist.append([x - 1, y, deep + 1])
            if y + 1 < h:
                if mymap[y + 1][x] not in '*X':
                    qlist.append([x, y + 1, deep + 1])
            if y - 1 >= 0:
                if mymap[y - 1][x] not in '*X':
                    qlist.append([x, y - 1, deep + 1])
        else:
            break
h, w, n = list(map(lambda x: int(x), input().split(" ")))
for i in range(0, h):
    const_mymap.append(input())

mymap = copy.deepcopy(const_mymap)

for i in range(0, h):
    for j in range(0, w):
        if mymap[i][j] == 'S':
            nstart = [j, i, 0]

qlist.append(nstart)

for i in range (n):
    mymap = copy.deepcopy(const_mymap)
    temp = bfs(i+1)
    #print(temp)
    #print(const_mymap)
    ans = temp[2]
    qlist = []
    qlist.append(temp)
    #print(ans)

print(ans)

Python: import sys
import collections
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 7

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, N = ZZ()
    field = [input() for _ in range(H)]
    D = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(start, goal):
        dist = [[INF] * W for _ in range(H)]
        deq = collections.deque()
        sx, sy = start
        dist[sx][sy] = 0
        deq.append([sx, sy])

        while deq:
            x, y = deq.popleft()
            for dx, dy in D:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and field[nx][ny] != 'X' and dist[nx][ny] == INF:
                    dist[nx][ny] = dist[x][y] + 1
                    deq.append([nx, ny])
        return dist[goal[0]][goal[1]]

    factory = [[] for _ in range(N+1)]
    for i in range(H):
        for j in range(W):
            if field[i][j] == 'S': factory[0] = [i, j]
            elif field[i][j] in {'1', '2', '3', '4', '5', '6', '7', '8', '9'}:
                factory[int(field[i][j])] = [i, j]
    ans = 0
    for i in range(N): ans += bfs(factory[i], factory[i+1])
    print(ans)

    return

if __name__ == '__main__':
    main()

Python: import queue
class unko(Exception):pass
INF=1145141919
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def search(cor_s,dst):
    mem=[[INF for i in range(a[1])]for j in range(a[0])]
    q=queue.Queue()
    q.put(cor_s)
    mem[cor_s[0]][cor_s[1]]=0
    while not q.empty():
        cor=q.get()
        for i in range(4):
            x=cor[0]+dx[i]
            y=cor[1]+dy[i]
            if 0<=x<a[0] and 0<=y<a[1] and s[x][y]!='X' and mem[x][y]==INF:
                mem[x][y]=mem[cor[0]][cor[1]]+1
                if s[x][y]==str(dst):return [[x,y],mem[x][y]]
                else:q.put([x,y])
#
a=[int(num)for num in input().split(' ')]
s=[list(input()) for i in range(a[0])]
pos_s=[]
time=0
for li in s:
    if 'S' in li:pos_s=[s.index(li),li.index('S')]
for i in range(a[2]):
    ret_l=search(pos_s,i+1)
    pos_s=ret_l[0]
    time+=ret_l[1]
print(time)

Python: def bfs(count, x, y, cheese):
    queue = [(count,x,y)]
    while len(queue)>0:
        tempc,tempx,tempy = queue.pop(0)
        print(tempc,tempx,tempy)
        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)