Unique Paths with Obstacles 🎯

Welcome to our deep dive into the fascinating world of Data Structures and Algorithms! Today, let's explore a classic problem: Unique Paths with Obstacles. This problem is a great way to understand the concept of dynamic programming, which is a powerful tool in the algorithmic arsenal.

What are Unique Paths with Obstacles? 📝

Imagine a grid where each cell can contain one of three things: an obstacle (represented by 'X'), an empty space (represented by '.'), or a destination (represented by 'D'). The goal is to count the number of unique paths from the top-left corner to the bottom-right corner that don't encounter any obstacles.

Breaking it Down 💡

Let's break this problem into smaller parts to make it easier to grasp.

Understanding the Grid: The grid is a 2D array of characters. Each character represents a cell.
Defining a Path: A path is a sequence of cells moving from the top-left to the bottom-right, never crossing an obstacle.
Counting Paths: We want to find the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1), where m and n are the number of rows and columns, respectively.

Solving the Problem ✅

We'll solve this problem using Dynamic Programming. The key idea is to break down the problem into smaller subproblems and solve them recursively, while remembering and reusing the solutions to the subproblems.

Here's a simple example of how we can solve this problem:

python

def uniquePathsWithObstacles(obstacleGrid):
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    # If the first cell is an obstacle, there are no unique paths.
    if obstacleGrid[0][0] == 'X':
        return 0

    # Initialize the dp array with 0s.
    dp = [[0] * n for _ in range(m)]

    # If the first cell is not an obstacle, there is one unique path.
    dp[0][0] = 1

    for i in range(1, m):
        if obstacleGrid[i][0] != 'X':
            dp[i][0] = dp[i-1][0]

    for j in range(1, n):
        if obstacleGrid[0][j] != 'X':
            dp[0][j] = dp[0][j-1]

    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] != 'X':
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

In this code, we first check if the starting cell is an obstacle. If it is, there are no unique paths. If not, we initialize a 2D array dp to store the number of unique paths to each cell. We then fill the dp array row by row, column by column, updating the values as we go along. The final answer is the value in the bottom-right cell of the dp array.

Putting It into Practice 💡

Now that you understand the concept, let's try some exercises to reinforce your understanding.

Remember, practice makes perfect! Keep solving problems and honing your skills. Happy coding! 💡🚀