def findPosition(matrix, token)
    matrix.length.times do |i|
        matrix[0].length.times do |j|
            return [i,j] if matrix[i][j] == token
        end
    end 
end

def countLuck(matrix, k)
    m,n = findPosition(matrix, 'M')
    p,q = findPosition(matrix, '*')
    queue = [[m,n]]
    visited = [[m,n]]
    father = Hash.new(-1)
    number_of_sons = Hash.new(-1)
    while not queue.empty?
        i,j = queue.shift
        break if matrix[i][j] == '*'
        valid_states = [ [i,j+1], [i,j-1], [i+1,j], [i-1,j]]
        valid_states = valid_states.select{ |i,j| i>=0 and i < matrix.length and j >=0 and j < matrix[0].length }
        valid_states = valid_states.select{ |i,j| matrix[i][j] != 'X' and not visited.include?([i,j])}
        valid_states.each { |k| father[k] = [i,j]}
        number_of_sons[[i,j]] = valid_states.length        
        queue += valid_states        
        visited += valid_states
    end
    counter = 0
    current_father = father[[p,q]]
    while current_father != -1 
        counter += 1 if number_of_sons[current_father] > 1
        current_father = father[current_father]
    end
    (counter == k) ? "Impressed" : "Oops!"
end