2290. Minimum Obstacle Removal to Reach Corner

1class Solution {
2    public int minimumObstacles(int[][] grid) {
3        // Get the dimensions of the grid
4        int rows = grid.length, cols = grid[0].length;
5
6        // Create a deque to hold the positions and the current obstacle count
7        Deque<int[]> queue = new ArrayDeque<>();
8        // Start from the upper left corner (0,0) with 0 obstacles
9        queue.offer(new int[] {0, 0, 0});
10        // Array to iterate over the 4 possible directions (up, right, down, left)
11        int[] directions = {-1, 0, 1, 0, -1};
12        // Visited array to keep track of positions already visited
13        boolean[][] visited = new boolean[rows][cols];
14
15        // Process cells until the queue is empty
16        while (!queue.isEmpty()) {
17            // Poll the current position and the number of obstacles encountered so far
18            int[] position = queue.poll();
19            int currentRow = position[0];
20            int currentCol = position[1];
21            int obstacles = position[2];
22
23            // Check if we have reached the bottom-right corner
24            if (currentRow == rows - 1 && currentCol == cols - 1) {
25                // If we reached the destination, return the number of obstacles encountered
26                return obstacles;
27            }
28
29            // If we have already visited this cell, skip it
30            if (visited[currentRow][currentCol]) {
31                continue;
32            }
33
34            // Mark the current cell as visited
35            visited[currentRow][currentCol] = true;
36
37            // Explore the neighboring cells
38            for (int h = 0; h < 4; ++h) {
39                int nextRow = currentRow + directions[h];
40                int nextCol = currentCol + directions[h + 1];
41
42                // Check the boundaries of the grid
43                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
44                    // If the next cell is free (no obstacle)
45                    if (grid[nextRow][nextCol] == 0) {
46                        // Add it to the front of the queue to be processed with the same obstacle count
47                        queue.offerFirst(new int[] {nextRow, nextCol, obstacles});
48                    } else {
49                        // If there's an obstacle, add it to the end of the queue with the obstacle count incremented by 1
50                        queue.offerLast(new int[] {nextRow, nextCol, obstacles + 1});
51                    }
52                }
53            }
54        }
55        // We include a return statement to satisfy the compiler, although the true return occurs inside the loop
56        return -1; // This will never be reached as the problem guarantees a path exists
57    }
58}
59

1#include <vector>
2#include <deque>
3#include <tuple>
4#include <cstring>
5
6class Solution {
7public:
8    // This function computes the minimum number of obstacles that need to be removed
9    // to move from the top-left corner to the bottom-right corner of the grid.
10    int minimumObstacles(std::vector<std::vector<int>>& grid) {
11        int rows = grid.size();          // The number of rows in the grid
12        int cols = grid[0].size();       // The number of columns in the grid
13      
14        // deque to perform BFS with a slight modification to handle 0-cost and 1-cost paths
15        std::deque<std::tuple<int, int, int>> queue;
16        queue.emplace_back(0, 0, 0);     // Start from the top-left corner (0,0)
17      
18        // Visited array to keep track of visited cells
19        bool visited[rows][cols];
20        std::memset(visited, 0, sizeof(visited));
21      
22        // Direction vectors for up, right, down and left movements
23        int directions[5] = {-1, 0, 1, 0, -1};
24      
25        while (!queue.empty()) {
26            // Get the current cell's row, column, and obstacle count
27            auto [currentRow, currentCol, obstacleCount] = queue.front();
28            queue.pop_front();
29          
30            // If we have reached the bottom-right corner, return the obstacle count
31            if (currentRow == rows - 1 && currentCol == cols - 1) {
32                return obstacleCount;
33            }
34          
35            // Skip this cell if it's already been visited
36            if (visited[currentRow][currentCol]) {
37                continue;
38            }
39          
40            // Mark the current cell as visited
41            visited[currentRow][currentCol] = true;
42          
43            // Loop through the possible movements using the direction vectors
44            for (int dir = 0; dir < 4; ++dir) {
45                int newRow = currentRow + directions[dir];
46                int newCol = currentCol + directions[dir + 1];
47              
48                // Check if the new position is valid and within the grid boundaries
49                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
50                    // If new cell has no obstacles, it has the same obstacle count 'k'
51                    // and it is pushed to the front to give it higher priority
52                    if (grid[newRow][newCol] == 0) {
53                        queue.emplace_front(newRow, newCol, obstacleCount);
54                    }
55                    // If new cell has an obstacle, increase the obstacle count 'k' by 1
56                    // and it is pushed to the back
57                    else {
58                        queue.emplace_back(newRow, newCol, obstacleCount + 1);
59                    }
60                }
61            }
62        }
63      
64        // If the function somehow reaches here (it should not), return -1 as an error signal.
65        // This return statement is logically unreachable because the loop is guaranteed to break
66        // when the bottom-right corner is reached.
67        return -1;
68    }
69};
70

1function minimumObstacles(grid: number[][]): number {
2    const rows = grid.length,
3        columns = grid[0].length; // Define the number of rows and columns of the grid
4    const directions = [ // Directions for traversal: right, left, down, up
5        [0, 1],
6        [0, -1],
7        [1, 0],
8        [-1, 0],
9    ];
10    let obstacleCount = Array.from({ length: rows }, () => new Array(columns).fill(Infinity)); // Initialize obstacle count for each cell with Infinity
11    obstacleCount[0][0] = 0; // Starting point has 0 obstacles
12    let deque = [[0, 0]]; // Double-ended queue to keep track of which cell to visit next
13
14    while (deque.length > 0) {
15        const [currentX, currentY] = deque.shift(); // Extract current cell coordinates
16      
17        for (const [dx, dy] of directions) {
18            const [nextX, nextY] = [currentX + dx, currentY + dy]; // Calculate adjacent cell coordinates
19          
20            if (nextX < 0 || nextX >= rows || nextY < 0 || nextY >= columns) {
21                continue; // Out of bounds check
22            }
23          
24            const currentCost = grid[nextX][nextY]; // Cost of the adjacent cell (0 for open cell, 1 for cell with an obstacle)
25          
26            if (obstacleCount[currentX][currentY] + currentCost >= obstacleCount[nextX][nextY]) {
27                continue; // If the new path isn't better, continue to the next adjacent cell
28            }
29          
30            obstacleCount[nextX][nextY] = obstacleCount[currentX][currentY] + currentCost; // Update the obstacle count for the cell
31          
32            if (currentCost === 0) {
33                deque.unshift([nextX, nextY]); // If no obstacle, add to the front of the queue
34            } else {
35                deque.push([nextX, nextY]); // If there's an obstacle, add to the back of the queue
36            }
37        }
38    }
39
40    return obstacleCount[rows - 1][columns - 1]; // Returns the minimum number of obstacles to reach the bottom-right corner
41}
42