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

public static String countLuck(List<String> matrix, int k) {
    // Write your code here
        List<Integer> start = getStartIndex(matrix);
        Map<String,Integer> map = new HashMap<>();
        map.put("counter",0);
        isSolution(start.get(0), start.get(1), matrix, new HashSet<>(),map);
        return map.get("counter") == k ? "Impressed" : "Oops!";
    }
    private static List<Integer> getStartIndex(List<String> matrix){
        for(int i = 0;i < matrix.size();i++)
            if(matrix.get(i).contains("M")) 
                return Arrays.asList(i,matrix.get(i).indexOf("M"));
        
        return null;
    }
    private static boolean isSolution(int i,int j, List<String> matrix,Set<String> visited,Map<String,Integer> map){
        if(visited.contains(i+","+j)) return false;
        visited.add(i+","+j);
        if(!isValidIndex(i, j, matrix)) return false;
        if(matrix.get(i).charAt(j)=='X') return false;
        if(matrix.get(i).charAt(j)=='*') return true;
        
        int count = 0;
        if(isCellValid(i - 1, j, matrix,visited)) count++;
        if(isCellValid(i, j - 1, matrix,visited)) count++;
        if(isCellValid(i + 1, j, matrix,visited)) count++;
        if(isCellValid(i, j + 1, matrix,visited)) count++;
        if(count > 1){
            map.put("counter", map.get("counter") + 1);
        }
        //Backtrack and add the counts in sub path (i.e. if the correct path)
        Map<String,Integer> localMap = new HashMap<>();
        localMap.put("counter",0);
        if(isSolution(i - 1, j, matrix, visited,localMap)){//top
            map.put("counter", map.get("counter") + localMap.get("counter"));
            return true;
        }else{
             localMap = new HashMap<>();
             localMap.put("counter",0);
             if(isSolution(i, j - 1, matrix, visited,localMap)){//left
                  map.put("counter", map.get("counter") + localMap.get("counter"));
                  return true;
             }
             else{
                localMap = new HashMap<>();
                localMap.put("counter",0);
                if(isSolution(i + 1, j, matrix, visited,localMap)){//bottom
                    map.put("counter", map.get("counter") + localMap.get("counter"));
                    return true;
                }else{
                    localMap = new HashMap<>();
                    localMap.put("counter",0);
                     if(isSolution(i, j + 1, matrix, visited,localMap)) {
                        map.put("counter", map.get("counter") + localMap.get("counter"));
                        return true;
                    }
                }
            }
        }
        return false;           
    }
    private static boolean isCellValid(int i, int j, List<String> matrix,Set<String> visited){
        if(visited.contains(i+","+j)) return false;
        if(!isValidIndex(i, j, matrix)) return false;
        return matrix.get(i).charAt(j) == '.' || matrix.get(i).charAt(j) == '*';
    }
    private static boolean isValidIndex(int i, int j,List<String> matrix){
        return i >= 0 && j >= 0 && i < matrix.size() && j < matrix.get(0).length();
    }

def countLuck(matrix, k):
    for i in range(n):#find start and end
        for j in range(m):
            if matrix[i][j]=='M':
                start=(i,j)
            if matrix[i][j]=='*':
                end=(i,j)
    vist={}#dic for if visited
    cur=[(start,0)]#record every step
    while cur:
        nex=[]
        for (p,q),turn in cur:
            if (p,q)==end:  #if find end then stop
                return 'Impressed' if turn==k else 'Oops!' 
            if (p,q) not in vist: #expansion steps
                vist[(p,q)]=turn
                nexpoint=[]
                for (i,j) in [(0,1),(0,-1),(-1,0),(1,0)]:
                    if 0<=p+i<n and 0<=q+j<m and matrix[p+i][q+j]!='X' and (p+i,q+j) not in vist:
                        nexpoint.append((p+i,q+j))
                #if expansion steps >= 2 then turnning point+1
                count =1 if len(nexpoint)>=2 else 0 
                #push new step into next step
                for (i,j) in nexpoint:
                    nex.append(((i,j),turn+count)) 
        cur=nex #next become current step

def countLuck(matrix, k):
    d = {}
    
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] in ('.', '*', 'M'):
                d[(i, j)] = matrix[i][j]
            
            if matrix[i][j] == 'M':
                q = [(i, j, [0])]
                v = [(i, j)]
                
    while q:
        i, j, p = q.pop(0)
        
        if d[(i, j)] == '*':
            if p[0] == k:
                return 'Impressed'
            else:
                return 'Oops!'
        
        n = len(v)
        p = list(p)
        
        for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            x += i
            y += j
            
            if (x, y) in d and (x, y) not in v:
                v.append((x, y))
                q.append((x, y, p))
                
        if (len(v) - n) > 1:
            p[0] += 1