Leetcode-Solutions/LC980.py at master · pratul2789/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution(object):
    def uniquePathsIII(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        if not grid:
            return 0

        sx,sy = -1,-1
        dx,dy = -1,-1
        validSteps = 0

        dirs = [(-1,0),(0,1),(1,0),(0,-1)]

        def helper(i,j,totalSteps,validSteps):

            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == -1:
                return 0
            count = 0

            if i == dx and j == dy and totalSteps == validSteps:
                return 1

            grid[i][j] = -1

            for d in dirs:
                r,c = i + d[0], j + d[1]

                count += helper(r,c,totalSteps+1,validSteps)

            grid[i][j] = 0
            return count


        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] != -1:
                    validSteps += 1

                if grid[i][j] == 1:
                    sx,sy = i,j

                if grid[i][j] == 2:
                    dx,dy = i,j

        grid[sx][sy] = 0

        return helper(sx,sy,1,validSteps)