3. Kate's Way Out

# Функция за намиране на началната позиция на "k" в лабиринта
def find_position(maze):
    position = []
    for row in range(len(maze)):
        for el in maze[row]:
            if el == 'k':
                position.append(row)
                position.append(maze[row].find('k'))
                return position

# Функция за намиране на свободните позиции (' ') в лабиринта
def next_free_spot(maze):
    free_spots = []

    for row in range(len(maze)):
        for el in range(len(maze[row])):
            tmp = []
            if maze[row][el] == ' ':
                tmp.append(row)
                tmp.append(el)
                free_spots.append(tmp)

    return free_spots

# Функция за намиране на пътя в лабиринта
def find_path(position, next_free, maze):
    moves = 0

    while next_free:
        x1, x2 = next_free.pop(0)

        # Проверка за движение наляво
        if position[0] == x1 and position[1] - x2 == 1:
            position = [x1, x2]
            moves += 1
        # Проверка за движение надясно
        elif position[0] == x1 and x2 - position[1] == 1:
            position = [x1, x2]
            moves += 1
        # Проверка за движение надолу
        elif x1 - position[0] == 1 and position[1] == x2:
            position = [x1, x2]
            moves += 1
        # Проверка за движение нагоре
        elif position[0] - x1 == 1 and position[1] == x2:
            position = [x1, x2]
            moves += 1

    # Проверка за излизане от лабиринта
    if position[0] == 0 or position[0] == (len(maze) - 1) or position[1] == 0 or position[1] == len(maze[0]):
        return f'Kate got out in {moves + 1} moves'
    # Съобщение, че Kate не може да излезе от лабиринта
    return 'Kate cannot get out'

# Вход от потребителя - брой редове в лабиринта
m_rows = int(input())
maze = []
moves = 0
free_space = True

# Вход от потребителя - редове на лабиринта
for row in range(m_rows):
    maze.append(input())

# Извикване на функциите и извеждане на резултата
position = find_position(maze)
next_free = next_free_spot(maze)
movement = find_path(position, next_free, maze)
print(movement)