22.12.31 Today’s Leetcode

980. Unique Paths III (hard)

모든 공간을 탐색하는 모든 경로를 찾는 문제, 빈공간의 개수를 이용하여 recursive 하게 구현했다. 맨처음에는 안될줄 알았는데, 빈공간의 개수를 이용하여 recursion depth를 제한해주니까 생각보다 쉽게 Time Exceeded가 뜨지 않고 문제를 해결 할 수 있었다.

class Solution:
    def DFS(self, grid, point, start, end, count):
        m, n = len(grid), len(grid[0])
        if point == end:
            if count == -1:
                return 1
            else:
                return 0
        if point[0] < 0 or point[0] >= m:
            return 0
        if point[1] < 0 or point[1] >= n:
            return 0
        if grid[point[0]][point[1]] == -1:
            return 0

        res = 0
        grid[point[0]][point[1]] = -1
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for p in dirs:
            x = point[0] + p[0]
            y = point[1] + p[1]
            res += self.DFS(grid, [x, y], start, end, count - 1)
        grid[point[0]][point[1]] = 0
        return res

    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        start, end = [0, 0], [0, 0]
        target_count = 0
        for x in range(m):
            for y in range(n):
                if grid[x][y] == 1:
                    start = [x, y]
                if grid[x][y] == 2:
                    end = [x, y]
                if grid[x][y] == 0:
                    target_count += 1
        return self.DFS(grid, start, start, end, target_count)        

258. Add Digits (easy)

class Solution:
    def addDigits(self, num: int) -> int:
        res = 0
        if num < 10:
            return num
        while num > 0:
            print(num, res)
            res += num % 10
            num = num // 10
        return self.addDigits(res)