Kate

possible_directions = []
steps_count = 0
ways_out = list()


def get_maze(rows_count):
    maze_lst = []

    for input_row in range(rows_count):
        input_row = list(input())
        maze_lst.append(input_row)

    return maze_lst


def get_kate_position(maze_lst):
    k_position_x, k_position_y = 0, 0

    for row_index in range(len(maze_lst)):
        if 'k' in maze_lst[row_index]:
            k_position_y = row_index

            for position_index in range(len(maze_lst[row_index])):
                if maze_lst[row_index][position_index] == 'k':
                    k_position_x = position_index
                    return k_position_x, k_position_y

    return


def kate_is_out(k_pos_x, k_pos_y, maze_lst):

    if k_pos_x == 0 or k_pos_x == (len(maze_lst[k_pos_y]) - 1) or k_pos_y == 0 or k_pos_y == (len(maze_lst) - 1):
        return True

    return False


def add_next_directions(k_position_x, k_position_y, maze_lst, forbidden_direction):
    current_directions = list()

    if k_position_x > 0:
        if maze_lst[k_position_y][k_position_x - 1] == " " and forbidden_direction != "left":
            current_directions.append("left")

    if k_position_x < len(maze_lst[k_position_y]) - 1:
        if maze_lst[k_position_y][k_position_x + 1] == " " and forbidden_direction != "right":
            current_directions.append("right")

    if k_position_y > 0:
        if maze_lst[k_position_y - 1][k_position_x] == " " and forbidden_direction != "up":
            current_directions.append("up")

    if k_position_y < len(maze_lst) - 1:
        if maze_lst[k_position_y + 1][k_position_x] == " " and forbidden_direction != "down":
            current_directions.append("down")

    return current_directions


def move_kate(move_direction, k_move_x, k_move_y):

    if move_direction == "left":
        k_move_x -= 1

    elif move_direction == "right":

        k_move_x += 1
    elif move_direction == "up":

        k_move_y -= 1
    elif move_direction == "down":

        k_move_y += 1

    return k_move_x, k_move_y


def ban_direction(current_direction):

    if current_direction == "left":
        banned_direction = "right"

    if current_direction == "right":
        banned_direction = "left"

    if current_direction == "up":
        banned_direction = "down"

    if current_direction == "down":
        banned_direction = "up"

    return banned_direction


# Main starts here
# Read the maze
number_of_rows = int(input())
maze = get_maze(number_of_rows)

# Get Kate position
kate_position_x, kate_position_y = get_kate_position(maze)      # TODO handle None case

# Check is Kate can get out immediately
if kate_is_out(kate_position_x, kate_position_y, maze):
    ways_out.append(steps_count + 1)

# Get the directions where Kate can go initially
possible_directions = add_next_directions(kate_position_x, kate_position_y, maze, None)

k_moved_position_x, k_moved_position_y = kate_position_x, kate_position_y

while possible_directions:

    steps_count += 1
    # print(f"step: {steps_count}, directions: {possible_directions}")

    for direction in possible_directions:

        k_moved_position_x, k_moved_position_y = move_kate(direction, k_moved_position_x, k_moved_position_y)
        # print(steps_count, direction, k_moved_position_x, k_moved_position_y)

        if kate_is_out(k_moved_position_x, k_moved_position_y, maze):
            ways_out.append(steps_count + 1)
            possible_directions = []
            break   # TODO change the directions lists somehow to work with multiple paths

        # set the opposite of the current direction to banned direction not to go back and loop
        next_forbidden_direction = ban_direction(direction)

        possible_directions = add_next_directions(k_moved_position_x, k_moved_position_y, maze, next_forbidden_direction)
        #print(possible_directions)


if len(ways_out) == 0:
    print("Kate cannot get out")
else:
    print(f"Kate got out in {max(ways_out)} moves")