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: from collections import deque

def getStart(field):
    search_field = field[1:]     # cut the first [H,W,N] for min_path matrix
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = deque()
    que.append([start_x,start_y])
    INF = 1000000
    min_path = [[INF] * field[0][1] for i in range(field[0][0])]
    min_path[start_y-1][start_x] = 0
    while len(que) != 0:
        current = que.popleft()
        for d in direction:
            nx = current[0] + d[0]
            ny = current[1] + d[1]
            if 0 <= nx < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                min_path[ny-1][nx] = min_path[current[1]-1][current[0]] + 1
                if field[ny][nx] == gotten_cheese: # at the same cheese-power number
                    distance += min_path[ny-1][nx]
                    if field[ny][nx] == goal_N: # goal
                        print(distance)
                        return
                    else: # not goal, but could eat cheese
                        que = deque([nx,ny])
                        gotten_cheese += 1
                        min_path = [[INF] * field[0][1] for i in range(field[0][0])]
                        min_path[ny-1][nx] = 0
                        break
                else:
                    que.append([nx,ny])


def main(field):
    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

# field = [[10,10,9],
# [".","X",".",".",".","X",".","S",".","X"],
# [6,".",".",5,"X",".",".","X",1,"X"],
# [".",".",".","X","X","X","X",".",".","X"],
# ["X",".",".",9,"X",".",".",".","X","."],
# [8,".","X",2,"X",".",".","X",3,"X"],
# [".",".",".","X","X",".","X",4,".","."],
# ["X","X",".",".",".",".",7,"X",".","."],
# ["X",".",".","X",".",".","X","X",".","."],
# ["X",".",".",".","X",".","X","X",".","."],
# [".",".","X",".",".",".",".",".",".","."]]
#
# main(field)

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        main(matrix)
        break

Python: from queue import Queue
from collections import defaultdict
try:
    d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    
    H, W, N = map(int, input().split())
    
    G = []
    
    sx = sy = 0
    for i in range(H):
        G.append(input())
        for j, c in enumerate(G[i]):
            if c == 'S':
                sx, sy = i, j
    
    Q = Queue()
    Q.put((sx, sy, 0))
    visited = defaultdict(lambda: defaultdict(lambda: False))
    visited[sx][sy] = True
    
    target = 1

    while not Q.empty():
        x, y, step = Q.get()
        if G[x][y] == str(target):
            visited.clear()
            visited[x][y] = True
            while not Q.empty():
                Q.get()
            target += 1
            if target == N + 1:
                print(step)
                break
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and G[nx][ny] != 'X':
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    Q.put((nx, ny, step + 1))
except BaseException as e:
    print(e)

Python: r,c,n=map(int,input().split())
grid=[input() for _ in [0]*r]
visit=[[grid[i][j]=="X" for j in range(c)] for i in range(r)]
cheese=[None for _ in [0]*(n+1)]

for i in range(r):
    for j in range(c):
        if grid[i][j] in ("X","."):
            continue
        elif grid[i][j]=="S":
            cheese[0]=[i,j]
        else:
            cheese[int(grid[i][j])]=[i,j]
cnt=0

for p in range(n):
    aa,bb=cheese[p]
    cc,dd=cheese[p+1]
    q=[[aa,bb]]
    v=[[visit[i][j] for j in range(c)] for i in range(r)]
    v[aa][bb]=True
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    flag=False
    while q:
        qq=[]
        while q:
            i,j=q.pop()
            for dx,dy in d:
                if 0<=i+dx<r and 0<=j+dy<c:
                    if i+dx==cc and j+dy==dd:
                        flag=True
                    if v[i+dx][j+dy]==False:
                        v[i+dx][j+dy]=True
                        qq.append([i+dx,j+dy])
        q=qq
        cnt+=1
        if flag==True:
            break
print(cnt)

Python: from collections import deque
import copy
h,w,n=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=deque([])
place=[[0,0] for _ in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=='S':
            queue.append([i,j,0])
            field[i][j]='.'
        elif field[i][j]!='X' and field[i][j]!='.':
            fact=int(field[i][j])
            field[i][j]='.'
            place[fact-1][0]=i
            place[fact-1][1]=j
#print(place)
#print(field)
ans=0
for i in range(n):
    if 1<=i:
        queue=deque([[place[i-1][0],place[i-1][1],0]])
#        print(queue)
    y=place[i][0]
    x=place[i][1]
    fi=copy.deepcopy(field)
    while True:
        hnow=queue[0][0]
        wnow=queue[0][1]
        time=queue[0][2]
        queue.popleft()
        time+=1
        if hnow+1<h:
            if hnow+1==y and wnow==x:
                break
            elif fi[hnow+1][wnow]=='.':
                fi[hnow+1][wnow]='v'
                queue.append([hnow+1,wnow,time])
        if wnow+1<w:
            if hnow==y and wnow+1==x:
                break
            elif fi[hnow][wnow+1]=='.':
                fi[hnow][wnow+1]='v'
                queue.append([hnow,wnow+1,time])
        
        if 0<=hnow-1:
            if hnow-1==y and wnow==x:
                break
            elif fi[hnow-1][wnow]=='.':
                fi[hnow-1][wnow]='v'
                queue.append([hnow-1,wnow,time])
        
        if 0<=wnow-1:
            if hnow==y and wnow-1==x:
                break
            elif fi[hnow][wnow-1]=='.':
                fi[hnow][wnow-1]='e'
                queue.append([hnow,wnow-1,time])
#        print(queue)
    ans+=time
print(ans)