• + 0 comments

    Java using BFS

    class Result {
      
      public static String countLuck(List<String> matrix, int k) {
            int rows = matrix.size();
            int cols = matrix.get(0).length();
            char[][] matrixArr = new char[rows][cols];
            int startX = -1;
            int startY = -1;
    
            // Parse the input matrix into a 2D char array and locate the starting position 'M'
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    matrixArr[i][j] = matrix.get(i).charAt(j);
                    if (matrixArr[i][j] == 'M') {
                        startX = i;
                        startY = j;
                    }
                }
            }
    
            // Count the "waves" (decision points) to determine the path
            int waves = getWaves(matrixArr, startX, startY);
    
            // Return "Impressed" if the waves match k, otherwise "Oops!"
            return waves == k ? "Impressed" : "Oops!";
        }
    
        private static int getWaves(char[][] matrixArr, int startX, int startY) {
            int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            Queue<int[]> cells = new LinkedList<>();
            boolean[][] visited = new boolean[matrixArr.length][matrixArr[0].length];
            cells.offer(new int[]{startX, startY, 0}); // Starting position and wave count
    
            while (!cells.isEmpty()) {
                int[] curCellPos = cells.poll();
                int curX = curCellPos[0];
                int curY = curCellPos[1];
                int waveCount = curCellPos[2];
    
                // If the current cell is the destination '*', return the wave count
                if (matrixArr[curX][curY] == '*') {
                    return waveCount;
                }
    
                // Mark the current cell as visited
                visited[curX][curY] = true;
    
                // Check if the current cell is a decision point and increase wave count if true
                if (isDecisionPoint(matrixArr, visited, curX, curY)) {
                    waveCount++;
                }
    
                // Add valid neighboring cells to the queue
                for (int[] dir : directions) {
                    int newX = curX + dir[0];
                    int newY = curY + dir[1];
                    if (isValid(matrixArr, newX, newY) &&
                            (matrixArr[newX][newY] == '.' || matrixArr[newX][newY] == '*') &&
                            !visited[newX][newY]) {
                        cells.offer(new int[]{newX, newY, waveCount});
                    }
                }
            }
    
            // Return 0 if the destination is unreachable (edge case)
            return 0;
        }
    
        private static boolean isDecisionPoint(char[][] matrixArr, boolean[][] visited, int x, int y) {
            int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int paths = 0;
    
            // Check all four directions for valid and unvisited paths
            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (isValid(matrixArr, newX, newY) &&
                        (matrixArr[newX][newY] == '.' || matrixArr[newX][newY] == '*') &&
                        !visited[newX][newY]) {
                    paths++;
                }
            }
    
            // A decision point occurs when there is more than one valid path
            return paths > 1;
        }
    
        private static boolean isValid(char[][] matrixArr, int x, int y) {
            int rows = matrixArr.length;
            int cols = matrixArr[0].length;
    
            // Check if the coordinates are within bounds
            return x >= 0 && x < rows && y >= 0 && y < cols;
        }
    }