def count_luck(matrix, k)
  @matrix = matrix
  @rows = matrix.length
  @cols = matrix[0].length

  # Find the coordinates of starting point and destination
  start_r, start_c, des_r, des_c = 0, 0, 0, 0
  (0..@rows - 1).each do |r|
    (0..@cols - 1).each do |c|
      start_r, start_c = r, c if matrix[r][c] == 'M'
      des_r, des_c = r, c if matrix[r][c] == '*'
    end
  end

  # Use BFS with a queue store the coordinates of each possible move
  # and the turn count to reach that position
  @visited = {}
  queue = [[start_r, start_c, 0]]
  until queue.empty?
    cur_r, cur_c, turn = queue.shift
    @visited[[cur_r, cur_c]] = true
    return turn == k ? 'Impressed' : 'Oops!' if cur_r == des_r && cur_c == des_c

    # Generate the next moves from current position
    next_moves = generate_next_moves(cur_r, cur_c)
    if next_moves.length > 1
      turn += 1
      next_moves.each { |move| queue << (move << turn) }
    else
      queue << (next_moves[0] << turn) unless next_moves.empty?
    end
  end
end

def generate_next_moves(row, col)
  res = []
  res << [row - 1, col] if valid_move?(row - 1, col)
  res << [row + 1, col] if valid_move?(row + 1, col)
  res << [row, col - 1] if valid_move?(row, col - 1)
  res << [row, col + 1] if valid_move?(row, col + 1)
  res
end

def valid_move?(row, col)
  row >= 0 && row < @rows && col >= 0 && col < @cols && @matrix[row][col] != 'X' && !@visited[[row, col]]
end