24.机器人的运动范围

题目描述

地上有一个$m$行和$n$列的方格，横纵坐标范围分别是$0∼m−1$和$0∼n−1$。
一个机器人从坐标$(0,0)$的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于$k$的格子。
请问该机器人能够达到多少个格子？

样例1

输入：k=7, m=4, n=5
输出：20

样例2

输入：k=18, m=40, n=40
输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

数据范围

0<=m<=50
0<=n<=50
0<=k<=100

Code

DFS

class Solution(object):
    def divide_num(self, number):
        # 返回一个数的数位之和
        res = 0
        while number >= 10:
            res += (number % 10)
            number //= 10
        res += number
        return res

    def dfs(self,x,y):
        self.res += 1
        self.state[x][y] = 1

        for i in range(4):
            a = x + self.dx[i]
            b = y + self.dy[i]
            if 0<=a<=self.n and 0<=b<=self.m and not self.state[a][b]:
                if self.divide_num(a) + self.divide_num(b) <= self.k:
                    # 可移动范围
                    self.dfs(a,b)


    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        N = 55
        self.dx = [-1,0,1,0]
        self.dy = [0,1,0,-1]
        self.k = threshold
        self.n = rows - 1
        self.m = cols - 1
        self.state = [[0] * N for i in range(N)]
        self.res = 0

        if rows == 0 and cols == 0:
            return 0
        else:
            self.dfs(0,0)

        return self.res

BFS

from collections import deque

class Solution(object):
    def divide_num(self, number):
        # 返回一个数的数位之和
        res = 0
        while number >= 10:
            res += (number % 10)
            number //= 10
        res += number
        return res

    def bfs(self,x,y):
        queue = deque()
        queue.append((x,y))
        self.res += 1
        self.state[x][y] = 1

        while queue:
            x,y = queue.popleft()

            for i in range(4):
                a = x + self.dx[i]
                b = y + self.dy[i]
                if 0<=a<=self.n and 0<=b<=self.m and not self.state[a][b]:
                    if self.divide_num(a) + self.divide_num(b) <= self.k:
                        queue.append((a,b))
                        self.res += 1
                        self.state[a][b] = 1


    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        N = 55
        self.dx = [-1,0,1,0]
        self.dy = [0,1,0,-1]
        self.k = threshold
        self.n = rows - 1
        self.m = cols - 1
        self.state = [[0] * N for i in range(N)]
        self.res = 0

        if rows == 0 and cols == 0:
            return 0
        else:
            self.bfs(0,0)

        return self.res