Unique Paths II

class Solution {
public:
    int calculatePaths(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
            
        if (grid[0][0] == 1) return 0;
        grid[0][0] = 1;
            
        for (int i = 1; i < rows; i++) {
            grid[i][0] = (grid[i][0] == 0 && grid[i - 1][0] == 1) ? 1 : 0;
        }
            
        for (int j = 1; j < cols; j++) {
            grid[0][j] = (grid[0][j] == 0 && grid[0][j - 1] == 1) ? 1 : 0;
        }
            
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
                } else {
                    grid[i][j] = 0;
                }
            }
        }
            
        return grid[rows - 1][cols - 1];
    }
};

This C++ solution addresses the problem of finding unique paths in a 2D grid where some cells are blocked (represented by 1s). The method calculatePaths takes a grid as input and outputs the number of unique paths from the top-left corner to the bottom-right corner, navigating around blocked cells.

• Start by checking the starting cell (top-left corner). If it's blocked (grid[0][0] == 1), return 0 as no path can start.
• Set the starting cell to 1 to represent the starting point of paths.
• For the first row, iterate through and set the cell to 1 if it's not blocked and the previous cell in the row has a path to it. Otherwise, set it to 0.
• Similarly, configure the first column: each cell depends on whether it is not blocked and the cell above it has a path.
• For all other cells, calculate paths by summing up available paths from the left and above. If a cell is blocked, its path count is set to 0.
• Finally, return the value of the bottom-right corner of the grid (grid[rows - 1][cols - 1]), which holds the count of unique paths to that point from the start.

This approach dynamically builds up the solution by adapting based on cell blockages and efficiently calculates paths using the previous computations for the neighboring cells.

class Solution {
    public int countPaths(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
    
        if (grid[0][0] == 1) {
            return 0;
        }
    
        grid[0][0] = 1;
    
        for (int i = 1; i < rows; i++) {
            grid[i][0] = (grid[i][0] == 0 && grid[i - 1][0] == 1) ? 1 : 0;
        }
    
        for (int j = 1; j < columns; j++) {
            grid[0][j] = (grid[0][j] == 0 && grid[0][j - 1] == 1) ? 1 : 0;
        }
    
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                if (grid[i][j] == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
                } else {
                    grid[i][j] = 0;
                }
            }
        }
    
        return grid[rows - 1][columns - 1];
    }
}

The Java solution provided for the problem "Unique Paths II" involves calculating the number of unique paths through a 2D grid that contains obstacles. Here's the breakdown of the approach:

• The function countPaths takes a 2D integer array grid as input, where the elements can be either 0 (free space) or 1 (obstacle).
• It first checks if the starting point (top-left corner of the grid) is an obstacle. If true, it directly returns 0 as no path can start from here.
• The algorithm initializes the starting point grid[0][0] to 1, indicating the starting position has one path.
• It then iteratively fills the first row and the first column. For each cell (i, 0) or (0, j), set the value to 1 if there's no obstacle and the previous cell in the row or column had a path (value 1). Otherwise, set it to 0.
• The main part of the algorithm calculates paths for the general case (i.e., for cells not in the first row/column). For each cell (i, j), if it's a free space (grid[i][j] == 0), the number of paths to reach it is the sum of the paths to the cell directly above it (grid[i-1][j]) and the cell to the left of it (grid[i][j-1]). If it's an obstacle (grid[i][j] == 1), it sets the number of paths to 0.
• After populating the grid, the value at the bottom-right corner (grid[rows - 1][columns - 1]) represents the total number of unique paths from the top-left to the bottom-right, avoiding all obstacles.

This method efficiently computes the result using dynamic programming, leveraging the fact that the number of paths to each cell only depends on the values of the cells directly above and to the left. This reduces the complexity compared to methods that might explore every possible path individually.

int calculatePaths(int** grid, int rows, int* cols) {
    int numRows = rows;
    int numCols = *cols;
    if (grid[0][0] == 1) return 0;
    grid[0][0] = 1;
    
    for (int i = 1; i < numRows; i++) {
        grid[i][0] = (grid[i][0] == 0 && grid[i - 1][0] == 1) ? 1 : 0;
    }
    
    for (int i = 1; i < numCols; i++) {
        grid[0][i] = (grid[0][i] == 0 && grid[0][i - 1] == 1) ? 1 : 0;
    }
    
    for (int i = 1; i < numRows; i++) {
        for (int j = 1; j < numCols; j++) {
            if (grid[i][j] == 0) {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            } else {
                grid[i][j] = 0;
            }
        }
    }
    return grid[numRows - 1][numCols - 1];
}

The provided C function calculatePaths computes the number of unique paths in a grid where certain cells are blocked. The grid is represented by a 2D array, where 1 indicates an obstacle and 0 indicates a free cell. The goal is to find how many distinct ways there are to travel from the top-left corner to the bottom-right corner of the grid, moving only right or down, and avoiding blocked cells.

• Initialize the number of rows (numRows) and columns (numCols) based on the input parameters.
• If the starting cell (top-left corner) is blocked (grid[0][0] == 1), the function immediately returns 0, indicating no paths are possible.
• Set the starting cell to 1, establishing the base case for dynamic programming which signifies one way to be at the start.
• Initialize the first column: each cell grid[i][0] (for i > 0) can only be reached from the cell directly above it if there is no obstacle. If there's an obstacle or if the cell above is 0 (indicating no path from above), set to 0.
• Initialize the first row: each cell grid[0][i] (for i > 0) can only be reached from the cell directly to the left of it if there is no obstacle. If there's an obstacle or if the cell to the left is 0, set to 0.
• Process the rest of the grid starting from cell grid[1][1]: if a cell is not blocked (grid[i][j] == 0), calculate the number of ways to reach it by adding the number of ways to reach the cell directly above (grid[i - 1][j]) and the cell directly to the left (grid[i][j - 1]). If it is blocked, set the number of ways to reach that cell to 0.
• The value at the bottom-right corner of the grid (grid[numRows - 1][numCols - 1]) provides the total number of unique paths from the top-left to the bottom-right while avoiding obstacles.

Overall, this function efficiently uses dynamic programming to solve the problem, leveraging the previously computed values to build up the solution in an optimal manner. Each cell computation is based on the cells directly connected to it from above and to the left, building up the answer iteratively.

var calculatePaths = function(grid) {
    let rows = grid.length;
    let cols = grid[0].length;
    
    if (grid[0][0] === 1) return 0;
    
    grid[0][0] = 1;
    
    for (let i = 1; i < rows; i++) {
        grid[i][0] = grid[i][0] === 0 && grid[i - 1][0] === 1 ? 1 : 0;
    }
    
    for (let j = 1; j < cols; j++) {
        grid[0][j] = grid[0][j] === 0 && grid[0][j - 1] === 1 ? 1 : 0;
    }
    
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (grid[i][j] === 0) {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            } else {
                grid[i][j] = 0;
            }
        }
    }
    
    return grid[rows - 1][cols - 1];
};

The function calculatePaths in JavaScript is developed to compute the number of unique paths in a 2D grid where some cells might be blocked (obstacles denoted by 1) and cannot be traversed. Here's a concise breakdown of how this code functions:

• Begin by defining the dimensions of the grid, using the variables rows for the number of rows and cols for the number of columns.
• Check if the starting point of the grid (top-left corner) is blocked. If so, return 0 since no path is possible.
• Set the starting cell grid[0][0] to 1, indicating the starting point for path calculations.
• Iterate over the first row (i from 1 to rows - 1). If a cell is not blocked and the cell directly above it has a path value (1), set its value to 1. Otherwise, set to 0.
• Perform a similar computation for the first column (j from 1 to cols - 1), checking if the left cell is viable for path extension.
• For the remaining cells, compute the total paths available by adding the values from the directly above (grid[i - 1][j]) and left (grid[i][j - 1]) cells, provided the current cell is not blocked (grid[i][j] === 0). If blocked, set its value to 0.
• Return the value from the bottom-right corner of the grid, which represents the total number of unique paths from the top-left to the bottom-right, considering all obstacles.

This approach efficiently handles dynamic input sizes and constraints, giving a robust solution for pathfinding in potentially obstructive grids.

class Solution(object):
    def pathWithBlocks(self, grid: List[List[int]]) -> int:
            
        rows = len(grid)
        cols = len(grid[0])
    
        if grid[0][0] == 1:
            return 0
    
        grid[0][0] = 1
    
        for i in range(1, rows):
            grid[i][0] = int(grid[i][0] == 0 and grid[i - 1][0] == 1)
    
        for j in range(1, cols):
            grid[0][j] = int(grid[0][j] == 0 and grid[0][j - 1] == 1)
    
        for i in range(1, rows):
            for j in range(1, cols):
                if grid[i][j] == 0:
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
                else:
                    grid[i][j] = 0
    
        return grid[rows - 1][cols - 1]

The solution provided solves the problem of calculating the number of unique paths in a 2D grid where some cells may be blocked, indicated by a "1". Paths can only travel right or down. The function pathWithBlocks executes this calculation as follows:

1. Initialize the number of rows and columns based on the dimensions of the input grid.
2. Check if the starting point of the grid is blocked. If it is, return 0, as no path is possible from the start.
3. Set the starting cell of the grid to 1, indicating the start of a path count.
4. Fill the first column of the grid: set each cell to 1 if it is not blocked and the cell above it is 1; otherwise, set to 0.
5. Fill the first row of the grid similarly: set each cell to 1 if it is not blocked and the cell to its left is 1; otherwise, set to 0.
6. Iterate over the remainder of the grid starting from cell (1,1):
   • For each cell that is not blocked, sum the paths from the cell directly above and the cell directly to the left to determine the number of paths to the current cell.
   • Set blocked cells to 0.
7. The function finally returns the value of the bottom-right cell in the grid, which contains the count of unique paths from the top-left to the bottom-right, avoiding blocked cells.

This algorithm efficiently calculates the required paths using dynamic programming techniques, adjusting paths dynamically based on blocked and unblocked cells. All operations leverage the grid in-place for space efficiency.