Sunday, August 14, 2016

ways from top-left to bottom-right with obstacles

// examples - x are obstacles

m:
631
321
11_
ways: 6

m:
211
1x1
11_
ways: 2

m: 
552x
x321
x11_
ways: 5

m:
1
ways: 1

m:
x
ways: 0

m: 
10xx
1000
1xxx
111_
ways: 5
Using visited is cleaner instead of using 2 negative values for obstacles and unvisited (0 can't be used for unvisited).
int (m):
    if m == null || m.length() == 0 || m[0].length() == 0:
        throw
    rows = m.length()
    cols = m[0].length()
    ti = rows-1, tj = cols-1
    // [ti,tj] could be blocked
    if m[ti,tj] < 0:
        return 0
    return (m, ti, tj, visited = new bool[rows, cols], rows, cols, 0, 0)

int (m, ti, tj, visited, rows, cols, i, j):
    if !(0 <= i < rows) || !(0 <= j < cols):
        return 0
    // obstacle
    if m[i,j] < 0:
        return 0
    if i == ti && j == tj:
        return 1
    // cached value
    if visited[i,j]:
        return m[i,j]
    visited[i,j] = true
    // 2 directions - right, bottom
    m[i,j] = 
        (m, ti, tj, visited, rows, cols, i+1, j) +
        (m, ti, tj, visited, rows, cols, i, j+1)
    return m[i,j]
[Hat tip to MA]

No comments:

Post a Comment