三个月算法进阶--day52

def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        self.count = 0
        self.m = m
        self.n = n
        self.k = k
        self.tmp = [[""] * n for i in range(m)]
        self.dfs(0, 0)
        return self.count

    def dfs(self, row, col):
        if not 0 <= row < self.m or not 0 <= col < self.n or self.tmp[row][col] == "#":
            return
        numsum = sum([int(i) for i in str(row)]) + sum([int(i) for i in str(col)])
        if numsum > self.k:
            return
        self.count += 1
        self.tmp[row][col] = "#"
        self.dfs(row+1, col)
        self.dfs(row, col+1)
        self.dfs(row-1, col)
        self.dfs(row, col-1)

def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        from queue import Queue
        q = Queue()
        q.put((0, 0))
        s = set()
        while not q.empty():
            x, y = q.get()
            if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.put((nx, ny))
        return len(s)

def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        vis = set([(0, 0)])
        for i in range(m):
            for j in range(n):
                if ((i - 1, j) in vis or (i, j - 1) in vis) and digitsum(i) + digitsum(j) <= k:
                    vis.add((i, j))
        return len(vis)