Minimum Obstacle Removal to Reach Corner

class Solution {
private:
    vector<vector<int>> moveDirections = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    int findMinObstacles(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> obstacleCount(rows, vector<int>(cols, INT_MAX));
        obstacleCount[0][0] = 0;

        deque<array<int, 3>> workQueue;
        workQueue.push_back({0, 0, 0});  // format: {obstacleCounter, xCoord, yCoord}

        while (!workQueue.empty()) {
            array<int, 3> current = workQueue.front();
            workQueue.pop_front();
            int count = current[0], x = current[1], y = current[2];

            for (auto& direction : moveDirections) {
                int newX = x + direction[0], newY = y + direction[1];

                if (isWithinBounds(matrix, newX, newY) &&
                    obstacleCount[newX][newY] == INT_MAX) {
                    if (matrix[newX][newY] == 1) {
                        obstacleCount[newX][newY] = count + 1;
                        workQueue.push_back({count + 1, newX, newY});
                    } else {
                        obstacleCount[newX][newY] = count;
                        workQueue.push_front({count, newX, newY});
                    }
                }
            }
        }

        return obstacleCount[rows - 1][cols - 1];
    }

private:
    bool isWithinBounds(vector<vector<int>>& matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.size() && y < matrix[0].size();
    }
};

The given code provides a solution to the problem of finding the minimum number of obstacles that must be removed to reach the bottom-right corner of a matrix from the top-left corner. The matrix consists of cells marked as either 0 (free space) or 1 (obstacle). The solution is implemented in C++ and utilizes a breadth-first search (BFS) strategy with some modifications to prioritize paths with fewer obstacles. Here's a concise explanation of how the solution works:

• Initialization:

  • A moveDirections vector contains possible moves: right, left, down, and up.
  • An obstacleCount matrix, initialized to INT_MAX, is used to store the minimum number of obstacles encountered up to each cell.
  • A double-ended queue (deque) named workQueue initialized with the starting point (0,0) and zero obstacles.

• Breadth-First Search Execution:

  • Extract the front element of the queue, representing the current cell and the count of removed obstacles.
  • For each possible move direction:
    • Calculate the new cell coordinates.
    • Check bounds and ensure the new cell has not been visited or has been visited with a higher obstacle count.
    • If the new cell is an obstacle, increment the obstacle count and add the cell to the end of the queue.
    • If the new cell is free, maintain the current obstacle count and add the cell to the front of the queue for priority.

• Queue Management:

  • workQueue manages cells such that cells with fewer obstacles are processed first, optimizing the path discovery towards the target cell (rows-1, cols-1).

• Result:

  • The value at the bottom-right of the obstacleCount matrix gives the minimum number of obstacles that must be removed to reach the target.

By using deque and effective management of queue operations, this solution ensures that paths with fewer obstacles are always processed first, thereby efficiently finding the minimum obstacles that need to be removed to reach the destination.

public class Solution {

    // Possible movement vectors: [down, up, right, left]
    private final int[][] moveDirections = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    };

    public int findMinObstacles(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;

        // Array to keep track of the minimum number of obstacles encountered
        int[][] obstaclesGrid = new int[rows][cols];

        // Start by marking all cells as not visited with a high number
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                obstaclesGrid[row][col] = Integer.MAX_VALUE;
            }
        }

        obstaclesGrid[0][0] = 0; // Start from the top-left corner

        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {0, 0, 0}); // {obstacles count, row index, column index}

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int countObstacles = current[0], currentRow = current[1], currentCol = current[2];

            // Process all possible moves
            for (int[] direction : moveDirections) {
                int nextRow = currentRow + direction[0], nextCol = currentCol + direction[1];

                if (
                    isWithinBounds(grid, nextRow, nextCol) &&
                    obstaclesGrid[nextRow][nextCol] == Integer.MAX_VALUE
                ) {
                    if (grid[nextRow][nextCol] == 1) {
                        // Encountering an obstacle
                        obstaclesGrid[nextRow][nextCol] = countObstacles + 1;
                        queue.addLast(new int[] {countObstacles + 1, nextRow, nextCol});
                    } else {
                        // Free path
                        obstaclesGrid[nextRow][nextCol] = countObstacles;
                        queue.addFirst(new int[] {countObstacles, nextRow, nextCol});
                    }
                }
            }
        }

        return obstaclesGrid[rows - 1][cols - 1];
    }

    // Utility function to check grid borders
    private boolean isWithinBounds(int[][] grid, int row, int col) {
        return row >= 0 && col >= 0 && row < grid.length && col < grid[0].length;
    }
}

The provided Java solution defines a method for calculating the minimum number of obstacles needed to be removed to reach the opposite corner of a grid. Here is an overview of the approach and functionality:

• Data Structures:

  • A 2D array obstaclesGrid is used to store the minimum number of obstacles encountered for each cell.
  • A deque queue is used for breadth-first search (BFS) to explore the grid level by level. To optimize the BFS process, cells with fewer obstacles are prioritized.

• Initialization:

  • The moveDirections array defines possible moves: down, up, right, and left.
  • All cells in obstaclesGrid are initialized to Integer.MAX_VALUE to denote that they have not been visited.
  • The start point (top-left corner of the grid) is initialized with zero since no obstacles have been removed to reach this point.

• BFS Process:

  • The process starts from the top-left corner of the grid.
  • In each BFS iteration, the current cell's position and obstacle count are retrieved.
  • All potential moves (up, down, left, right) are evaluated:
    • If the next cell is within bounds and has not been visited yet, then:
      • If there's an obstacle (grid[nextRow][nextCol] == 1), increase the obstacle count and add the cell to the back of the queue.
      • If there's no obstacle, keep the current obstacle count and add the location to the front of the queue to prioritize exploration.

• Result Calculation:

  • After the BFS completes, the value at the bottom-right corner of obstaclesGrid gives the minimum number of obstacles that must be removed to reach that corner from the top-left corner.

• Boundary Check:

  • A helper method isWithinBounds confirms if a given cell coordinate is within the grid limits.

Ensure to implement this method correctly in your grid-based problem solving approach to efficiently calculate minimum path constraints such as obstacle removals. This BFS-based approach ensures optimal performance by handling nodes with potentially fewer obstacles first.

class PathFinder:
    # Movement directions: right, left, down, up
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def findMinObstacles(self, grid):
        def is_within_bounds(x, y):
            return 0 <= x < len(grid) and 0 <= y < len(grid[0])

        rows, cols = len(grid), len(grid[0])

        obstacle_count = [[float("inf")] * cols for _ in range(rows)]
        obstacle_count[0][0] = 0

        deque_nodes = deque([(0, 0, 0)])  # (current_obstacles, x, y)

        while deque_nodes:
            curr_obstacles, x, y = deque_nodes.popleft()

            for dx, dy in self.moves:
                nx, ny = x + dx, y + dy

                if is_within_bounds(nx, ny) and obstacle_count[nx][ny] == float("inf"):
                    if grid[nx][ny] == 1:
                        obstacle_count[nx][ny] = curr_obstacles + 1
                        deque_nodes.append((curr_obstacles + 1, nx, ny))
                    else:
                        obstacle_count[nx][ny] = curr_obstacles
                        deque_nodes.appendleft((curr_obstacles, nx, ny))

        return obstacle_count[rows - 1][cols - 1]

The solution involves finding the minimum number of obstacles to remove in order to reach from the top-left corner to the bottom-right corner of a grid. This is implemented using the Breadth-First Search (BFS) algorithm with a deque to efficiently handle states.

Follow these steps to understand the implementation in Python:

1. Define the PathFinder class with the method findMinObstacles(grid) to process the grid.
2. Initialize moves representing possible movement directions: right, left, down, and up.
3. Helper function is_within_bounds(x, y) checks whether the given coordinates are within the grid boundaries.
4. rows and cols store the dimensions of the grid.
5. A 2D list obstacle_count initialized with 'infinity', representing the initial state where no path has been found yet. The start point (0, 0) is set to zero, indicating no obstacles have been removed at the beginning.
6. A deque initialized with the starting point coordinates and the initial obstacle count.
7. The central loop extracts elements from the deque and explores all possible moves:
   • For each possible move, the new coordinates are calculated.
   • If the new position is within bounds and has not been visited yet (still at 'infinity'), the obstacle at this position is checked.
   • If the new position has an obstacle (grid[nx][ny] == 1), increment the current obstacle count at this position, and the position is added to the end of the deque with the updated count.
   • If there is no obstacle at the new position, it inherits the current obstacle count from the position it came from, and the position is added to the front of the deque for immediate processing.
8. After the loop, the obstacle count at the bottom-right corner of the grid ([rows - 1][cols - 1]) is returned, representing the minimum number of obstacles that need to be removed to move from the top-left to the bottom-right corner.

This implementation ensures that every position is processed in the most efficient order regarding obstacle removal, effectively leading to the optimal solution provided by the BFS algorithm.