03. Kate's Way Out

rows = int(input())
matrix = [list(input()) for i in range(rows)]
k_row = sum([r for r in range(rows) if "k" in matrix[r]])
k_col = sum([c for c in range(len(matrix[k_row])) if "k" == matrix[k_row][c]])

r = k_row
c = k_col
visited_positions = [[k_row, k_col]]
moves = 0

while True:
    moves += 1
    if matrix[r][c + 1] == " " and c + 1 < len(matrix[r]) and not [r, c + 1] in visited_positions:
        matrix[r][c], matrix[r][c + 1] = matrix[r][c + 1], matrix[r][c]
        c += 1
        visited_positions.append([r, c])
    elif matrix[r][c - 1] == " " and c - 1 >= 0 and not [r, c - 1] in visited_positions:
        matrix[r][c], matrix[r][c - 1] = matrix[r][c - 1], matrix[r][c]
        c -= 1
        visited_positions.append([r, c])
    elif matrix[r - 1][c] == " " and r - 1 >= 0 and not [r - 1, c] in visited_positions:
        matrix[r][c], matrix[r - 1][c] = matrix[r - 1][c], matrix[r][c]
        r -= 1
        visited_positions.append([r, c])
    elif matrix[r + 1][c] == " " and r + 1 < rows and not [r + 1, c] in visited_positions:
        matrix[r][c], matrix[r + 1][c] = matrix[r + 1][c], matrix[r][c]
        r += 1
        visited_positions.append([r, c])
    else:
        moves = 0
        matrix[r][c] = "#"
        r = k_row
        c = k_col
        matrix[r][c] = "k"
        visited_positions = [[k_row, k_col]]
    if r == 0 or r == rows - 1 or c == 0 or c == len(matrix[0]) - 1:
        moves += 1
        print(f"Kate got out in {moves} moves")
        break
    elif matrix[r][c + 1] == "#" and matrix[r][c - 1] == "#" and matrix[r - 1][c] == "#" and matrix[r + 1][c] == "#":
        print("Kate cannot get out")
        break