Traverse 2d array
Given a boolean matrix, where a cell that's false denotes an obstacle, calculate the number of ways we can reach the bottom right cell n-1,m-1 starting at top left 0,0.
Solution
- In classic DP fashion, use a matrix to keep of the number of ways to reach previous step
- In this case to calculate the number of ways to reach cell n,m, just add the number of ways to reach n-1,m and n,m-1 cell.
- Ensure the first row and first col are pre-populated with num ways as 1
Code
def num_ways(matrix)
num_ways = [[0] * m] * n
for i in 0..m do
for j in 0..n do
if matrix[i][j] == true # No obstacle
num_ways[i][j] = (i == 0 ? 0 : num_ways[i-1][j]) + (j == 0 ? 0 : num_ways[i-1][j] )
end
end
end
return num_ways[m-1][n-1]
end
Complexity
O(n*m) due to the 2 loops iterating over the matrix.