Unique Paths II
2D/3D DP and Grids DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Grid Unique Paths with Obstacles (Maze Obstacles Problem), Dynamic Programming, Memoization, Tabulation, Space Optimization, Recursion, Arrays, Two-dimensional Array Traversal, Time Complexity, Space Complexity, Grid Traversal, dynamic programming, recursion with memoization, tabulation, grid traversal, space optimization, matrix traversal, Number of Islands / Flood Fill.
Unique Paths II There is an N x M grid. The grid contains some obstacles. A cell is a 'blockage' if its value is 1. A value of 0 represents a non blocked cell. No path is possible through a blocked cell. The task is to count the total number of unique paths from the top left corner (0, 0) of the grid to the bottom right corner (N 1, M 1). At every cell, you can only move either down or towards the right. Input Specification The first line contains two integers, N and M, representing the dimensions of the grid. The next N lines each contain M integers, representing the grid. Each integer will be either 0 (non blocked) or 1 (blocked). Output Specification Output a single integer, the total number of unique paths from the top left to the bottom right corner. Sample Test Case Input: Output: