问题描述

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为 3+5+3+7=18 。但它不能进入方格 [35, 38] ，因为 3+5+3+8=19 。请问该机器人能够到达多少个格子？

解题思路

从左上角(0,0)开始，采用广度优先搜索算法：

• 判断当前点的右相邻格子能否到达，若能并且该格子不在队列则入队
• 判断当前点的下相邻格子能否到达，若能并且该格子不在队列则入队
• 出队，循环操作，直到队列为空

Python实现

class Solution(object):
    def movingCount(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """ 
        def num_sum(num):
            s = 0
            while num:
                s += num % 10
                num = num//10
            return s
                
        res = [(0,0)]
        for i,j in res:
            if i+1 <= m-1 and num_sum(i+1)+num_sum(j) <= k and (i+1,j) not in res:
                res.append((i+1,j))
            if j+1 <= n-1 and num_sum(i)+num_sum(j+1) <= k and (i,j+1) not in res:
                res.append((i,j+1))
        return len(res)