Laberinto (

"""
    Reads a matrix of integers from the input, where:
        - Walls are represented by -1
        - Targets are represented by 1
        - Empty spaces are represented by 0
"""

# Verifies if the current state is a solution by checking if the last cell is reached and all targets are visited
def isSol(matrix, pi, pj):
    global targets

    # If the current position is not the last cell, return False
    if pi != len(matrix)-1 or pj != len(matrix[0])-1: 
        return False

    # If any target is not visited, return False
    for t in targets:
        if matrix[t[0]][t[1]] == 0: 
            return False

    # If the last cell is not visited, return False otherwise return True
    return matrix[-1][-1] != 0

# Returns the factible children of the current state
def get_children(matrix, pi, pj):
    # Auxiliar arrays to move in the matrix in the i and j axis (right, down, left, up)
    di = [1, 0, -1, 0] 
    dj = [0, 1, 0, -1]

    # Array to store the factible children
    cands = []
    
    # Iterate over the possible children
    for k in range(4):
        # Calculate the new position in the new hypothetical child
        newI = pi + di[k]
        newJ = pj + dj[k]

        # Make several checks to verify if the new position is factible
        fail_conditions = [
            newI < 0, newJ < 0,  # If the new position is out of bounds 
            newI >= len(matrix), newJ >= len(matrix[0]),  # If the new position is out of bounds
            matrix[newI][newJ] == -1, # If the new position is a wall
            matrix[newI][newJ] > 0 # If the new position is already visited
        ]
        
        # If any of the conditions is true, continue to the next iteration
        if any(fail_conditions):
            continue

        # If the new position passed all checks, append it to the candidates array
        cands.append((newI, newJ))

    return cands

# Backtracking function to find the best solution
def bt(matrix, best, pi, pj):
    # If the current state is a solution, update the best solution
    if isSol(matrix, pi, pj):
        # Update the best solution to the minimum between the current best solution and the current solution
        best["score"] = min(matrix[-1][-1], best["score"])  

    # Iterate over the factible children of the current state
    for child in get_children(matrix, pi, pj):
        # Auxiliar variable to store the number of steps to reach the current child
        steps = matrix[pi][pj]
        
        # Backtrack to the child
        matrix[child[0]][child[1]] = steps+1  # Update the matrix with the number of steps to reach the child
        bt(matrix, best, child[0], child[1])  # Call the backtracking function recursively
        matrix[child[0]][child[1]] = 0        # Reset the matrix to the previous state once the recursion is done


# =============================================================================
if __name__ == "__main__":
    rows, cols, prods = map(int, input().strip().split())
    matrix = []
    targets = []
    
    # Read the matrix from the input
    # The matrix is parsed so that the targets are stored in the targets array and the matrix only contains the walls and empty spaces
    for i in range(rows):
        line = list(map(int, input().strip().split()))
        matrix.append([])
        for j, e in enumerate(line):
            if e == 1:
                targets.append((i,j))
                matrix[i].append(0)
                continue
            matrix[i].append(e)

    best = {"score": float("inf"), "step": 0}
    bt(matrix, best, 0, 0)
    print(best)