https://community.topcoder.com/stat?c=problem_statement&pm=1889&rd=4709

AvoidRoads.py

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]