Dynamic Programming - Number of ways to get out of a maze (with obstacles)

Question

I'm trying to code using dynamic programming, a num_of_paths function to get the number of ways out of a maze. The maze taken in is a tuple of n tuples, each with m values. The values inside the tuple is either 0 or 1, and 0 stands for a bomb in that cell. Here is the psuedocode:

1. Initialize an empty table (dictionary), get number of rows n and number of columns m.

2. Fill in the first row. For j in range m:

   2.1. If maze[0][j] is safe, set table[(0, j)] to be 1 because there's one way to go there.

   2.2. If maze[0][j] has a bomb, set table[(0, k)] where k >= j to be 0. Since one cell is broken along the way, all following cells (in the first row) cannot be reached.

3. Fill in first column. For i in range n:

   3.1 If maze[i][0] is safe, set table[(i, 0)] to be 1 because there's one way to go there.

   3.2 If maze[i][0] has a bomb, set table[(i, 0)] and all cells under it to be 0. The reason is same as row.

4. Main DP procedure - fill in the rest of the table. If maze[i][j] has a bomb, set table[(i, j)] = 0. Otherwise, table[(i, j)] = table[(i - 1, j)] + table[(i, j - 1)].

5. Return table[(n - 1, m - 1)].

def num_of_paths(maze):
    # Step 1
    table = {}
    n = len(maze)
    m = len(maze[0])
    # Step 2
    for j in range(m):
        if maze [0][j] == 1: #Safe
            table[(0, j)] = 1
        else: #Bomb
            for k in range(j,):
                table[(0, k)] = 0
    for i in range(n): #Step 3
        if maze[i][0] == 1: #Safe
            table[(i,0)] = 1
        else: #Bomb
            table[(i,0)] = 0
    for j in range(1,m): #Step 4
        for i in range(1,n):
            if maze[i][j] == 0: #Bomb
                table[(i,j)] = 0
            else:
                table[(i,j)] = table[(i - 1, j)] + table[(i, j - 1)]
    return table[(n-1,m-1)] #Step 5

maze  = ((1, 1, 1, 1, 1, 1, 1, 1, 0, 1),
         (1, 0, 0, 1, 1, 1, 0, 0, 1, 1),
         (0, 1, 1, 1, 0, 0, 1, 1, 1, 0),
         (1, 1, 0, 1, 1, 1, 1, 0, 1, 1),
         (0, 1, 0, 1, 0, 0, 1, 0, 1, 0),
         (1, 0, 1, 1, 1, 1, 0, 1, 1, 1),
         (1, 1, 0, 1, 0, 1, 0, 0, 1, 1),
         (0, 1, 1, 1, 1, 1, 1, 1, 1, 0),
         (1, 0, 1, 0, 0, 1, 1, 0, 1, 1),
         (1, 0, 1, 1, 1, 0, 1, 0, 1, 0),
         (1, 1, 0, 1, 0, 1, 0, 1, 1, 1))

I'm getting a KeyError:(0,8) for the 2nd last line. I suspect it's because the key is not inside my dictionary(?) Anyone has suggestions to get around this error, or an alternative method to code?

Answer 1

def num_of_paths(maze):
    # Step 1
    table = {}
    n = len(maze)
    m = len(maze[0])
    # Step 2
    for j in range(m):
        if maze [0][j] == 1: #Safe
            table[(0, j)] = 1
        else: #Bomb
            for k in range(j,m):
                table[(0, k)] = 0
            break
    for i in range(n): #Step 3
        if maze[i][0] == 1: #Safe
            table[(i,0)] = 1
        else: #Bomb
            for k in range(i,n):
                table[(k,0)] = 0
            break
    for j in range(1,m): #Step 4
        for i in range(1,n):
            if maze[i][j] == 0: #Bomb
                table[(i,j)] = 0
            else:
                table[(i,j)] = table[(i - 1, j)] + table[(i, j - 1)]
    return table[(n-1,m-1)] #Step 5

Managed to debug, turns out that there were some errors in my else cases under the 2 for loops.

1. Had to end the inner loop at the end of the row/column
2. Had to break out of the outer for loop

Thanks to everyone who helped!

Answer 2

   def countPaths(maze):
     
    # If the initial cell is blocked,
    # there is no way of moving anywhere
    if (maze[0][0] == -1):
        return 0
 
    # Initializing the leftmost column
    for i in range(R):
        if (maze[i][0] == 0):
            maze[i][0] = 1
 
        # If we encounter a blocked cell in
        # leftmost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # Similarly initialize the topmost row
    for i in range(1, C, 1):
        if (maze[0][i] == 0):
            maze[0][i] = 1
 
        # If we encounter a blocked cell in
        # bottommost row, there is no way of
        # visiting any cell directly below it.
        else:
            break
 
    # The only difference is that if a cell is -1,
    # simply ignore it else recursively compute
    # count value maze[i][j]
    for i in range(1, R, 1):
        for j in range(1, C, 1):
             
            # If blockage is found, ignore this cell
            if (maze[i][j] == -1):
                continue
 
            # If we can reach maze[i][j] from
            # maze[i-1][j] then increment count.
            if (maze[i - 1][j] > 0):
                maze[i][j] = (maze[i][j] +
                              maze[i - 1][j])
 
            # If we can reach maze[i][j] from
            # maze[i][j-1] then increment count.
            if (maze[i][j - 1] > 0):
                maze[i][j] = (maze[i][j] +
                              maze[i][j - 1])
 
    # If the final cell is blocked,
    # output 0, otherwise the answer
    if (maze[R - 1][C - 1] > 0):
        return maze[R - 1][C - 1]
    else:
        return 0

You can visit Geeksforgeeks for the same with some more explanation: Click here