Problem

Given a 2D array A[M][N], aka Grid / Maze / Matrix, with obstacles

Write an algorithm to count the number of unique paths to reach to A[M-1][N-1] from A[0][0]

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

Expected output 2

Dynamic programming bottom-up approach