675. Cut Off Trees for Golf Event

1import java.util.*;
2
3class Solution {
4    private int[] distances = new int[3600]; // Pre-allocating space for distances.
5    private List<List<Integer>> forestGrid;  // The forest as a grid of trees.
6    private int rows;                       // Number of rows in the forest grid.
7    private int cols;                       // Number of columns in the forest grid.
8
9    public int cutOffTree(List<List<Integer>> forest) {
10        this.forestGrid = forest;
11        rows = forest.size();
12        cols = forest.get(0).size();
13        List<int[]> trees = new ArrayList<>();
14
15        // Collecting trees with height > 1 to cut them down in order of height.
16        for (int i = 0; i < rows; ++i) {
17            for (int j = 0; j < cols; ++j) {
18                int treeHeight = forest.get(i).get(j);
19                if (treeHeight > 1) {
20                    trees.add(new int[] {treeHeight, i * cols + j});
21                }
22            }
23        }
24
25        // Sorting trees by their heights because we need to cut trees in increasing order of height.
26        trees.sort(Comparator.comparingInt(a -> a[0]));
27
28        int steps = 0;  // The minimum number of steps to cut all trees.
29        int start = 0;  // Tracking the starting position of the worker (row * columns + column).
30
31        // Looping through the sorted trees to cut.
32        for (int[] tree : trees) {
33            int end = tree[1]; // Tree's position.
34            int stepToTree = bfs(start, end); // Using BFS to find the shortest path to the tree.
35            if (stepToTree == -1) {
36                return -1; // If tree is unreachable return -1.
37            }
38            steps += stepToTree; // Adding the steps to the final result.
39            start = end; // Update start position for the next tree.
40        }
41
42        return steps; // Returning the total number of steps needed to cut all trees.
43    }
44
45    private int bfs(int start, int end) {
46        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // Priority Queue for selecting the node with minimum heuristic distance.
47        queue.offer(new int[] {calculateHeuristic(start, end), start});
48        Arrays.fill(distances, Integer.MAX_VALUE);
49        distances[start] = 0; // Starting point's distance is 0.
50
51        int[] directions = {-1, 0, 1, 0, -1}; // Directions: up, right, down, left.
52
53        // Process nodes in the queue.
54        while (!queue.isEmpty()) {
55            int[] node = queue.poll();
56            int currentState = node[1];
57            if (currentState == end) { // If end is reached.
58                return distances[currentState];
59            }
60
61            // Exploring adjacent squares in the forest.
62            for (int k = 0; k < 4; ++k) {
63                int newX = currentState / cols + directions[k];
64                int newY = currentState % cols + directions[k + 1];
65                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && forestGrid.get(newX).get(newY) > 0) {
66                    if (distances[newX * cols + newY] > distances[currentState] + 1) {
67                        distances[newX * cols + newY] = distances[currentState] + 1;  // Update distance.
68                        queue.offer(new int[] {distances[newX * cols + newY] + calculateHeuristic(newX * cols + newY, end), newX * cols + newY});
69                    }
70                }
71            }
72        }
73
74        return -1; // If no path is found to the end, return -1;
75    }
76
77    // Heuristic function for A* search: computes the Manhattan distance between two points.
78    private int calculateHeuristic(int start, int end) {
79        int startX = start / cols;
80        int startY = start % cols;
81        int endX = end / cols;
82        int endY = end % cols;
83        return Math.abs(startX - endX) + Math.abs(startY - endY);
84    }
85}
86

1class Solution {
2public:
3    int rows; // "m" is renamed to "rows" to be more descriptive
4    int cols; // "n" is renamed to "cols" to be more descriptive
5    vector<int> distances; // "dist" is renamed to "distances"
6
7    int cutOffTree(vector<vector<int>>& forest) {
8        rows = forest.size();
9        cols = forest[0].size();
10        distances.resize(rows * cols); // Using rows * cols instead of a hardcoded value
11        vector<pair<int, int>> trees;
12
13        // Collect all the trees with a height greater than 1 and their locations
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                if (forest[i][j] > 1) {
17                    trees.emplace_back(forest[i][j], i * cols + j);
18                }
19            }
20        }
21
22        // Sort trees based on their height
23        sort(trees.begin(), trees.end());
24        int totalSteps = 0;
25        int currentPos = 0;
26
27        // Attempt to cut each tree in ascending order of height
28        for (auto& tree : trees) {
29            int targetPos = tree.second;
30            int stepsToTree = bfs(currentPos, targetPos, forest);
31            if (stepsToTree == -1) return -1; // If a tree is unreachable, return -1
32            totalSteps += stepsToTree;
33            currentPos = targetPos;
34        }
35
36        return totalSteps;
37    }
38
39    // Breadth-first search to find the shortest path to a tree
40    int bfs(int startPos, int endPos, vector<vector<int>>& forest) {
41        // PriorityQueue to get the node with the minimum distance from queue
42        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
43      
44        // Start from the initial position
45        minHeap.push({distanceHeuristic(startPos, endPos), startPos});
46      
47        // Initially, set all distances to infinity
48        fill(distances.begin(), distances.end(), INT_MAX);
49        distances[startPos] = 0;
50      
51        // Possible moves (up, right, down, left)
52        vector<int> directions = {-1, 0, 1, 0, -1};
53      
54        while (!minHeap.empty()) {
55            int currentPos = minHeap.top().second;
56            minHeap.pop();
57            if (currentPos == endPos) return distances[currentPos]; // Reached target
58          
59            // Explore all adjacent cells
60            for (int k = 0; k < 4; ++k) {
61                int newX = currentPos / cols + directions[k];
62                int newY = currentPos % cols + directions[k + 1];
63              
64                // If the cell is within bounds and not blocked
65                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && forest[newX][newY] > 0) {
66                    int nextPos = newX * cols + newY;
67                    // If a shorter distance is found, update it
68                    if (distances[nextPos] > distances[currentPos] + 1) {
69                        distances[nextPos] = distances[currentPos] + 1;
70                        minHeap.push({distances[nextPos] + distanceHeuristic(nextPos, endPos), nextPos});
71                    }
72                }
73            }
74        }
75      
76        // If the path is not found, return -1
77        return -1;
78    }
79
80    // A heuristic function for estimating distance for priority queue (Manhattan distance)
81    int distanceHeuristic(int startPos, int endPos) {
82        int startX = startPos / cols;
83        int startY = startPos % cols;
84        int endX = endPos / cols;
85        int endY = endPos % cols;
86        return abs(startX - endX) + abs(startY - endY);
87    }
88};
89

1// Assuming that 'number' is a valid substitute for 'int' in the original C++ code
2// and we're using arrays and tuples to represent the vectors and pairs.
3
4// Define the number of rows and columns
5let rows: number;
6let cols: number;
7// Define the distances array
8let distances: number[];
9
10// Function to calculate the minimum steps to cut off all trees in a forest
11function cutOffTree(forest: number[][]): number {
12    rows = forest.length;
13    cols = forest[0].length;
14    // Initialize the distances with a size of rows * cols
15    distances = new Array(rows * cols);
16    // Collect trees with height greater than 1
17    const trees: [number, number][] = [];
18
19    // Collect all trees with a height greater than 1 and their locations
20    for (let i = 0; i < rows; ++i) {
21        for (let j = 0; j < cols; ++j) {
22            if (forest[i][j] > 1) {
23                trees.push([forest[i][j], i * cols + j]);
24            }
25        }
26    }
27
28    // Sort trees based on their height
29    trees.sort((a, b) => a[0] - b[0]);
30    let totalSteps = 0;
31    let currentPos = 0;
32
33    // Attempt to cut each tree in ascending order of height
34    for (const tree of trees) {
35        const targetPos = tree[1];
36        const stepsToTree = bfs(currentPos, targetPos, forest);
37        if (stepsToTree === -1) return -1; // If a tree is unreachable, return -1
38        totalSteps += stepsToTree;
39        currentPos = targetPos;
40    }
41
42    return totalSteps;
43}
44
45// Breadth-first search to find the shortest path to a tree
46function bfs(startPos: number, endPos: number, forest: number[][]): number {
47    // PriorityQueue is replaced with an array since JavaScript doesn't have a built-in PriorityQueue
48    type QueueElement = [number, number]; // Format: [heuristic+cost, position]
49    const minHeap: QueueElement[] = [];
50
51    // Start from the initial position
52    minHeap.push([distanceHeuristic(startPos, endPos), startPos]);
53
54    // Initially, set all distances to Infinity
55    distances.fill(Number.MAX_SAFE_INTEGER);
56    distances[startPos] = 0;
57
58    // Possible moves (up, right, down, left)
59    const directions = [-1, 0, 1, 0, -1];
60
61    while (minHeap.length > 0) {
62        // Since JavaScript lacks a built-in PriorityQueue, we manually sort and pop
63        minHeap.sort((a, b) => a[0] - b[0]);
64        const current = minHeap.shift();
65        if (!current) break;
66        const currentPos = current[1];
67      
68        if (currentPos === endPos) return distances[currentPos]; // Reached target
69
70        // Explore all adjacent cells
71        for (let k = 0; k < 4; ++k) {
72            const newX = Math.floor(currentPos / cols) + directions[k];
73            const newY = currentPos % cols + directions[k + 1];
74
75            // If the cell is within bounds and not blocked
76            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && forest[newX][newY] > 0) {
77                const nextPos = newX * cols + newY;
78
79                // If a shorter distance is found, update it
80                if (distances[nextPos] > distances[currentPos] + 1) {
81                    distances[nextPos] = distances[currentPos] + 1;
82                    minHeap.push([distances[nextPos] + distanceHeuristic(nextPos, endPos), nextPos]);
83                }
84            }
85        }
86    }
87
88    // If the path is not found, return -1
89    return -1;
90}
91
92// A heuristic function for estimating distance for priority queue (Manhattan distance)
93function distanceHeuristic(startPos: number, endPos: number): number {
94    const startX = Math.floor(startPos / cols);
95    const startY = startPos % cols;
96    const endX = Math.floor(endPos / cols);
97    const endY = endPos % cols;
98    return Math.abs(startX - endX) + Math.abs(startY - endY);
99}
100