03. Kate's Way Out (backtracking)

def isSafe(maze, x, y, sol):
    if 0 <= x < row and 0 <= y < col and maze[x][y] != "#" and sol[x][y] == 0:
        return True
    return False


def solveMaze(maze):
    sol = [[0 for j in range(col)] for i in range(row)]
    if not solveMazeUtil(maze, x, y, sol):
        return "Kate cannot get out"
    else:
        moves = sum([1 for r in range(row) for c in range(col) if sol[r][c] == 1])
        return f"Kate got out in {moves} moves"


def solveMazeUtil(maze, x, y, sol):
    if isSafe(maze, x, y, sol):
        if x == row - 1 or y == col - 1 or x == 0 or y == 0:
            sol[x][y] = 1
            return True
        sol[x][y] = 1
        if solveMazeUtil(maze, x + 1, y, sol):
            return True
        if solveMazeUtil(maze, x, y + 1, sol):
            return True
        if solveMazeUtil(maze, x - 1, y, sol):
            return True
        if solveMazeUtil(maze, x, y - 1, sol):
            return True
        sol[x][y] = 0
        return False


row = int(input())
maze = [list(input()) for i in range(row)]
col = len(maze[0])
x = sum([r for r in range(row) if "k" in maze[r]])
y = sum([c for c in range(len(maze[x])) if "k" == maze[x][c]])

print(solveMaze(maze))