import unittest

class Solution:
    def get_unique_paths_count(self, matrix):
        row_count, col_count = len(matrix), len(matrix[0])
        if row_count == 0 or col_count == 0:
            raise Exception('Unvalid Matrix')
        
        if matrix[0][0] or matrix[-1][-1]:
            return 0
        
        row_paths = [0 for _ in range(col_count)]
        path_count = 0

        for row in range(row_count):
            new_row_paths = []
            for col in range(col_count):
                if row == 0 and col == 0:
                    path_count = 1
                elif matrix[row][col] == 1:
                    path_count = 0
                else:
                    path_count = row_paths[col]
                    path_count += new_row_paths[-1] if col > 0 else 0
                new_row_paths.append(path_count)
            row_paths = new_row_paths 

        return row_paths[-1]
    
    def uniquePathsWithObstacles(self, grid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        
        if grid[0][0] or grid[-1][-1]:
            return 0
        
        m, n = len(grid), len(grid[0])
        
        ways = [0] * (n + 1)
        ways[1] = 1
        
        for row in range(1, m + 1):
            new_ways = [0]
            for col in range(1, n + 1):
                if grid[row - 1][col - 1] == 1:
                    new_ways.append(0)
                else:
                    new_ways.append(new_ways[-1] + ways[col])
            
            ways = new_ways
        
        return ways[-1]

class Test(unittest.TestCase):
    test_data = [([[0,0,0], [0,1,0], [0,0,0]], 2), ([[0,0,0], [1,0,1], [0,0,0]], 1)]

    def test_get_unique_paths_count(self):
        solution = Solution()
        for data in self.test_data:
            actual = solution.uniquePathsWithObstacles(data[0])
            self.assertEqual(actual, data[1])

if __name__ == '__main__':
    unittest.main()