I'm learning Dynamic Programming, following the topcoder guide. I just solved the AvoidRoads challenge. It passes all the test cases, but I don't have much experience, so I don't know if it's good.
Linked description contains images and better illustrates the problem.
You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. You will return the number of distinct paths that lead to your destination. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a String[] bad describing which blocks are bad. If (quotes for clarity) "a b c d" is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let's say
width = 6 length = 6 bad = {"0 0 0 1","6 6 5 6"} Returns: 252
My Solution:
def allowed(i, j, x, y, banned_set):
s = "{} {} {} {}"
options = [
s.format(i, j, x, y),
s.format(x, y, i, j)
]
for opt in options:
if opt in banned_set:
return False
return True
def calc(lst, i, j, banned_set):
result = 0
if i-1 >= 0 and allowed(i, j, i-1, j, banned_set):
result += lst[i-1][j]
if j-1 >= 0 and allowed(i, j, i, j-1, banned_set):
result += lst[i][j-1]
return result
def avoid_roads(n, m, banned_set):
n += 1
m += 1
matrix = [[0 for _ in xrange(m)] for _ in xrange(n)]
matrix[0][0] = 1
for i in xrange(n):
for j in xrange(m):
if i == j == 0:
continue
matrix[i][j] = calc(matrix, i, j, banned_set)
return matrix[-1][-1]