Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class AvoidRoads:
def badDict(self, bad):
bd = {}
for b in bad:
bd[b] = True
return bd
def numWays(self, width, height, bad):
M = [[0] * (width+1) for i in range(height+1)]
M[0][0] = 1
bd = self.badDict(bad)
for h in range(height + 1):
for w in range(width + 1):
if h == 0 and w == 0:
continue
paths = 0
if w - 1 >= 0:
path1 = "%d %d %d %d" % (w - 1, h, w, h)
path2 = "%d %d %d %d" % (w, h, w - 1, h)
if not bd.get(path1, False) and not bd.get(path2, False):
paths += M[h][w-1]
if h - 1 >= 0:
path1 = "%d %d %d %d" % (w, h - 1, w, h)
path2 = "%d %d %d %d" % (w, h, w, h - 1)
if not bd.get(path1, False) and not bd.get(path2, False):
paths += M[h-1][w]
M[h][w] = paths
return M[height][width]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.