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 = []

    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.pop(0)

        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:

                    distance += min_path[ny-1][nx]

                    if field[ny][nx] == goal_N: # goal

                        print(distance)

                        return

                    else: # not goal, but could eat cheese

                        que = []

                        que.append([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])



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


def bfs(field,H,W,start_x,start_y,tmp_N):

    direction = [[-1,0],[1,0],[0,-1],[0,1]]

    que = []

    que.append([start_x,start_y])

    INF = 1000000

    min_path = [[INF] * W for i in range(H)]

    min_path[start_y][start_x] = 0

    while len(que) != 0:

        current = que.pop(0)

        for d in direction:

            nx = current[0] + d[0]

            ny = current[1] + d[1]

            if 0 <= nx < W and 0 <= ny < H and field[ny][nx] != "X" and min_path[ny][nx] == INF:

                min_path[ny][nx] = min_path[current[1]][current[0]] + 1

                if field[ny][nx] == tmp_N: # at the same cheese-power number

                    return nx,ny,min_path[ny][nx]

                else:

                    que.append([nx,ny])



def getField():

    matrix = []

    first = input().strip()

    H,W,N = list(map(int,first.split()))

    for i in range(H):

        row = list(input().strip())

        for j in range(W):

            if row[j].isdigit():

                row[j] = int(row[j])

        matrix.append(row)

    return matrix,H,W,N



def getStart(field):

    for y in range(len(field)):

        for x in range(len(field[0])):

            if field[y][x] == "S":

                return x,y



def main():

    matrix,H,W,N = getField()

    sx,sy = getStart(matrix)

    distance = 0

    for k in range(N):

        if k != 0:

            tmp_x,tmp_y,tmp_dist = bfs(matrix,H,W,tmps[0],tmps[1],k+1)

            distance += tmp_dist

            tmps = [tmp_x,tmp_y]

        else:

            tmp_x,tmp_y,tmp_dist = bfs(matrix,H,W,sx,sy,k+1)

            distance += tmp_dist

            tmps = [tmp_x,tmp_y]

    print(distance)





if __name__=='__main__':

    main()
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 = []
    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.pop(0)
        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:
                    distance += min_path[ny - 1][nx]
                    if field[ny][nx] == goal_N:  # goal
                        print(distance)
                        return
                    else:  # not goal, but could eat cheese
                        que = []
                        que.append([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])


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

def bfs(field, H, W, start_x, start_y, tmp_N):
    direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = []
    que.append([start_x, start_y])
    INF = 1000000
    min_path = [[INF] * W for i in range(H)]
    min_path[start_y][start_x] = 0
    while len(que) != 0:
        current = que.pop(0)
        for d in direction:
            nx = current[0] + d[0]
            ny = current[1] + d[1]
            if (
                0 <= nx < W
                and 0 <= ny < H
                and field[ny][nx] != "X"
                and min_path[ny][nx] == INF
            ):
                min_path[ny][nx] = min_path[current[1]][current[0]] + 1
                if field[ny][nx] == tmp_N:  # at the same cheese-power number
                    return nx, ny, min_path[ny][nx]
                else:
                    que.append([nx, ny])


def getField():
    matrix = []
    first = input().strip()
    H, W, N = list(map(int, first.split()))
    for i in range(H):
        row = list(input().strip())
        for j in range(W):
            if row[j].isdigit():
                row[j] = int(row[j])
        matrix.append(row)
    return matrix, H, W, N


def getStart(field):
    for y in range(len(field)):
        for x in range(len(field[0])):
            if field[y][x] == "S":
                return x, y


def main():
    matrix, H, W, N = getField()
    sx, sy = getStart(matrix)
    distance = 0
    for k in range(N):
        if k != 0:
            tmp_x, tmp_y, tmp_dist = bfs(matrix, H, W, tmps[0], tmps[1], k + 1)
            distance += tmp_dist
            tmps = [tmp_x, tmp_y]
        else:
            tmp_x, tmp_y, tmp_dist = bfs(matrix, H, W, sx, sy, k + 1)
            distance += tmp_dist
            tmps = [tmp_x, tmp_y]
    print(distance)


if __name__ == "__main__":
    main()

-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): +def bfs(field, H, W, start_x, start_y, tmp_N): -    gotten_cheese = 1 -    distance = 0 -    min_path = [[INF] * field[0][1] for i in range(field[0][0])] -    min_path[start_y - 1][start_x] = 0 +    min_path = [[INF] * W for i in range(H)] +    min_path[start_y][start_x] = 0 -                0 <= nx < field[0][1] -                and 1 <= ny < field[0][0] + 1 +                0 <= nx < W +                and 0 <= ny < H -                and min_path[ny - 1][nx] == INF +                and min_path[ny][nx] == INF -                min_path[ny - 1][nx] = min_path[current[1] - 1][current[0]] + 1 -                if field[ny][nx] == gotten_cheese: -                    distance += min_path[ny - 1][nx] -                    if field[ny][nx] == goal_N:  # goal -                        print(distance) -                        return -                    else:  # not goal, but could eat cheese -                        que = [] -                        que.append([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 +                min_path[ny][nx] = min_path[current[1]][current[0]] + 1 +                if field[ny][nx] == tmp_N:  # at the same cheese-power number +                    return nx, ny, min_path[ny][nx] -def main(field): -    sx, sy = getStart(field) -    bfs(field, sx, sy, field[0][2]) +def getField(): +    matrix = [] +    first = input().strip() +    H, W, N = list(map(int, first.split())) +    for i in range(H): +        row = list(input().strip()) +        for j in range(W): +            if row[j].isdigit(): +                row[j] = int(row[j]) +        matrix.append(row) +    return matrix, H, W, N -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 +def getStart(field): +    for y in range(len(field)): +        for x in range(len(field[0])): +            if field[y][x] == "S": +                return x, y + + +def main(): +    matrix, H, W, N = getField() +    sx, sy = getStart(matrix) +    distance = 0 +    for k in range(N): +        if k != 0: +            tmp_x, tmp_y, tmp_dist = bfs(matrix, H, W, tmps[0], tmps[1], k + 1) +            distance += tmp_dist +            tmps = [tmp_x, tmp_y] +        else: +            tmp_x, tmp_y, tmp_dist = bfs(matrix, H, W, sx, sy, k + 1) +            distance += tmp_dist +            tmps = [tmp_x, tmp_y] +    print(distance) + + +if __name__ == "__main__": +    main()