## Finding the number of paths in a maze with obstacles

bob navigates a maze hackerrank

unique paths in a grid with obstacles

maze solving algorithm

count number of ways to reach destination

find all paths from source to destination in matrix

number of paths in a matrix

shortest path in a binary maze leetcode

I've been working on this leetcode problem, which is essentially finding the number of valid paths in a maze given some `obstacleGrid`

matrix. If `obstacleGrid[i][j] == 1`

, then we have an obstacle at (i,j) and we have zero otherwise, which a valid spot. We can only move down and right with the goal of starting from the upper left to the bottom right.

I have written the code below:

def uniquePathsWithObstacles(self, obstacleGrid): # obstruction at the start if (obstacleGrid[0][0] == 1): return 0 # obstruction at the end if (obstacleGrid[-1][-1] == 1): return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) memo = [[0] * n] * m # starting move memo[0][0] = 1 # now check the first row for j in range(1, n): memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0 # now check the first column for i in range(1, m): memo[i][0] = 1 if (obstacleGrid[i][0] == 0 and memo[i-1][0] != 0) else 0 # now check everything else for i in range(1, m): for j in range(1, n): if (obstacleGrid[i][j] == 1): memo[i][j] = 0 else: memo[i][j] = memo[i-1][j] + memo[i][j-1] return memo[-1][-1]

I took the obvious DP approach and I know the idea works but something is wrong with the code; for some reason I don't think my `memo`

matrix is being updated properly? I feel like the problem is staring at me in the face but for some reason I can't see it. Any help appreciated!

Edit: For `obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]`

and if I had a `print(memo)`

right before the return statement, I get `[[1, 1, 2], [1, 1, 2], [1, 1, 2]]`

. This happens to give me the right answer, but the `memo`

matrix is wrong!

One problem lies in the line `memo = [[0] * n] * m`

.
This does not really create `m`

copies of the same list, but instead, it only creates the `[0] * n`

list once and then creates `memo`

as a list of `m`

references to this list. Any change to any of these lists therefore modifies all other lists!

You can try this yourself:

memo = [[0] * 3] * 4 memo[0][1] = 1 print(memo)

This gives `[[0, 1, 0], [0, 1, 0], [0, 1, 0], [0, 1, 0]]`

.

Instead, you have to initialize each list on their own, e.g.,

memo = [] for i in range(m): memo.append([0] * n)

**Count number of ways to reach destination in a Maze using BFS ,** Given a maze with obstacles, count number of paths to reach A cell in the given maze has value -1 if it is a blockage or dead-end, else 0. Please Improve this article if you find anything incorrect by clicking on the "Improve� Count number of ways to reach destination in a Maze. Given a maze with obstacles, count number of paths to reach rightmost-bottommost cell from topmost-leftmost cell. A cell in given maze has value -1 if it is a blockage or dead end, else 0. From a given cell, we are allowed to move to cells (i+1, j) and (i, j+1) only.

I just tried to do this with recursion as an comparison rather than an answer.

import numpy as np def number_of_paths(obstacles): """ Calculate the number of paths available in a maze with obstacles, with only right and down moves, from top left to bottom right. Args: obstacles (ndarray): binary matrix with 1 representing obstacle Returns: int: the number of paths """ if obstacles[0,0] == 1: raise ValueError # cannot start on an obstacle count = 0 if obstacles.shape == (2,1): return 1 if obstacles.shape == (1,2): return 1 if obstacles.shape[1] > 1 and obstacles[0,1] == 0: count += number_of_paths(obstacles[:,1:]) if obstacles.shape[0] > 1 and obstacles[1,0] == 0: count += number_of_paths(obstacles[1:,:]) return count

**Find total number of unique paths in a maze from source to ,** Positions in the maze will either be open or blocked with an obstacle. The robot can only move to positions without obstacles i.e. solution should find paths which � Given a 2D array A[M][N], aka Grid / Maze / Matrix. Write an algorithm to count the number of unique paths to reach A[M-1][N-1] from A[0][0] At any cell (x, y), you can either go to (x+1, y) or (x, y+1) if there's no obstacle. Example. Input A[3][3] with values {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0 and 1 represent for empty and obstacle respectively

your code is correct and 1 line must be updated per the below:

def uniquePathsWithObstacles(self, obstacleGrid): # obstruction at the start if (obstacleGrid[0][0] == 1): return 0 # obstruction at the end if (obstacleGrid[-1][-1] == 1): return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) memo = [[0] * n for i in range(m)] # starting move memo[0][0] = 1 # now check the first row for j in range(1, n): #memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0 memo[0][j] = 1 if (obstacleGrid[0][j] == 0 and memo[0][j-1] != 0) else 0 # now check the first column for i in range(1, m): memo[i][0] = 1 if (obstacleGrid[i][0] == 0 and memo[i-1][0] != 0) else 0 # now check everything else for i in range(1, m): for j in range(1, n): if (obstacleGrid[i][j] == 1): memo[i][j] = 0 else: memo[i][j] = memo[i-1][j] + memo[i][j-1] return memo[-1][-1]

**Finding the number of paths in a maze with obstacles,** One problem lies in the line memo = [[0] * n] * m . This does not really create m copies of the same list, but instead, it only creates the [0] * n list� Find the total number of unique paths which the robot can take in a given maze to reach the destination from given source. Positions in the maze will either be open or blocked with an obstacle. The robot can only move to positions without obstacles i.e. solution should find paths which contain only cells which are open.

**Recursion: Solving a Maze,** Positions in the maze will either be open or blocked with an obstacle. Positions We'll solve the problem of finding and marking a solution path using recursion. Count all possible path in maze is one more grid problem which is asked in Amazon and Microsoft interviews and can be solved using dynamic programming. Before going into details of solution, let’s understand the problem. Problem statement is find total number of paths in a given maze or grid to reach at right most bottom cell from leftmost top cell.

**Unique Paths With Obstacles,** Problem. Given a 2D array A[M][N], aka Grid / Maze / Matrix. Write an algorithm to count the number of unique paths to reach A[M-1][N-1] from� Then I get 462, but I have to consider obstacles so I minus 462 with paths from each obstacles to $, and I get numbers : 21 70 6 15 10 3, surprisingly after I use 462-21-70-6-15-10-3, I get a number which is much bigger than 9, I think if I use the total paths without obstacles to minus total path obstacles blocked, it should be the total path

**Count all possible paths in maze,** Problem statement is find total number of paths in a given maze or grid to to smaller one and solving smaller problems lead to solution of bigger problem. 2. If a path doesn’t reach destination or we have explored all possible routes from the current cell, we backtrack. To make sure that the path is simple and doesn’t contain any cycles, we keep track of cells involved in current path in a matrix and before exploring any cell, we ignore the cell if it is already covered in current path.

##### Comments

- How do you know it's wrong? Can you give a simple example of
`obstacleGrid`

with your result and the expected result? - Remove
`self`

from the function definition, unless this is a class method. The code as is gives an error:`TypeError: uniquePathsWithObstacles() missing 1 required positional argument: 'obstacleGrid'`

- Thank you! Your suggestion works. Also
`memo = [[0 for i in range(n)] for i in range(m)]`

worked as well! In terms of good Python coding, is there a preferable way? - You're right, good idea! Your one-liner is more pythonic, I think. But you could even do
`[[0]*n for i in range(m)]`

. - @AyumuKasugano: What you wrote is good and is consistent. The way I see the most is
`memo = [[0] * n for _ in range(m)]`

, which may be faster if somewhat inconsistent.