题目描述

blablabla

样例

blablabla

BFS

Python代码

from collections import deque
class Solution(object):
    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        if not rows or not cols:
            return 0
        res = 1
        memo = set()
        memo.add((0,0))
        q = deque([(0,0)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while q:
            x, y = q.popleft()
            for i in range(4):
                xx = x + dx[i]
                yy = y + dy[i]
                if self.is_valid(xx, yy, rows, cols, threshold) and (xx, yy) not in memo:
                    res += 1
                    q.append((xx, yy))
                    memo.add((xx, yy))
        return res

    def is_valid(self, x, y, m, n, k):
        return 0 <= x < m and 0 <= y < n and self.get_sum(x) + self.get_sum(y) <= k

    def get_sum(self, x):
        res = 0
        while x:
            res += x % 10
            x = x//10
        return res