题目描述

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

题目解析：
典型的回溯问题,可借鉴前一题（矩阵路径）的思路。

分析一下题目，当行数和列数按位求和不大于阈值（threshold），那当前机器人是可以运动的，这个是重要的判断条件。

如何回溯？

假设机器人进入（0,0）点，首先要判断当前的点是否满足上述条件，若满足，则count + 1,并且，将走过的位置标记为已经走过，以免后面回溯回来的时候重复计算。当前的点访问完毕之后，就需要访问上、下、左、右四个方向的点，也就是row - 1、row + 1、col - 1、col + 1。最终机器人会访问所有的点，并给出符合条件的格子总数。

代码分析：

根据模块化的思想，首先，我需要一个计算给定整数按位求和的函数：getNumberSum,代码如下：

    def getNumberSum(self, num):
        """
        本函数用于处理：求出输入进来的数按位求和
        :param num:
        :return:
        """
        n = 0
        while num != 0:
            n += num % 10
            num = num // 10
        return n

其次，我还需要一个判断是否满足threshold的函数：allow，代码如下：

    def allow(self, threshold, row, col):
        """
        本函数用于判断： 行数按位求和值+列数按位求和值是否大于阈值
        :param threshold:
        :param row:
        :param col:
        :return:
        """
        sum_row = self.getNumberSum(row)
        sum_col = self.getNumberSum(col)
        if (sum_row + sum_col) > threshold:
            return False
        else:
            return True

另外，还需要一个递归查找函数：find，代码如下：

    def find(self, threshold, visited_matrix, rows, cols, row, col):
        """
        本函数用于递归查找，并计算个数
        :param threshold:
        :param visited_matrix:
        :param rows:
        :param cols:
        :param row:
        :param col:
        :return:
        """
        count = 0
        if row >= 0 and col >= 0 and row < rows and col < cols and self.allow(threshold,row,col) and visited_matrix[row][col] != 0:
            visited_matrix[row][col] = 0 # 如果访问过就设为0
            count += 1
            count += self.find(threshold, visited_matrix, rows, cols, row - 1, col) + \
                     self.find(threshold, visited_matrix, rows, cols, row + 1, col) +\
                     self.find(threshold, visited_matrix, rows, cols, row, col - 1) +\
                     self.find(threshold, visited_matrix, rows, cols, row, col + 1)
        return count

最后，加一个函数统一封装入口：movingCount，代码如下：

    def movingCount(self, threshold, rows, cols):
        # write code here
        if (rows < 0 or cols < 0 or threshold < 0):
            return 0
        visited_matrix = [[1] * cols for i in range(rows)]
        return self.find(threshold,visited_matrix, rows, cols, 0, 0)

解释一下 ：[[1] * cols for i in range(rows)]

rows = 4

cols = 3

这行代码的返回值是：

[
    [1, 1, 1], 
    [1, 1, 1], 
    [1, 1, 1], 
    [1, 1, 1]
]

很强大的功能，如果有时间可以研究一下其源码。PS:我们研究源码的目的不仅仅是为了看它是如何实现的，写代码也是写策略，很多代码策略就是实际生活中策略的抽象。

完整代码及测试用例和输出如下：

# -*- coding:utf-8 -*-
class Solution:
    def getNumberSum(self, num):
        """
        本函数用于处理：求出输入进来的数按位求和
        :param num:
        :return:
        """
        n = 0
        while num != 0:
            n += num % 10
            num = num // 10
        return n

    def allow(self, threshold, row, col):
        """
        本函数用于判断： 行数按位求和值+列数按位求和值是否大于阈值
        :param threshold:
        :param row:
        :param col:
        :return:
        """
        sum_row = self.getNumberSum(row)
        sum_col = self.getNumberSum(col)
        if (sum_row + sum_col) > threshold:
            return False
        else:
            return True

    def find(self, threshold, visited_matrix, rows, cols, row, col):
        """
        本函数用于递归查找，并计算个数
        :param threshold:
        :param visited_matrix:
        :param rows:
        :param cols:
        :param row:
        :param col:
        :return:
        """
        count = 0
        if row >= 0 and col >= 0 and row < rows and col < cols and self.allow(threshold,row,col) and visited_matrix[row][col] != 0:
            visited_matrix[row][col] = 0 # 如果访问过就设为0
            count += 1
            count += self.find(threshold, visited_matrix, rows, cols, row - 1, col) + \
                     self.find(threshold, visited_matrix, rows, cols, row + 1, col) +\
                     self.find(threshold, visited_matrix, rows, cols, row, col - 1) +\
                     self.find(threshold, visited_matrix, rows, cols, row, col + 1)
        return count

    def movingCount(self, threshold, rows, cols):
        # write code here
        if (rows < 0 or cols < 0 or threshold < 0):
            return 0
        visited_matrix = [[1] * cols for i in range(rows)]
        return self.find(threshold,visited_matrix, rows, cols, 0, 0)


if __name__ == '__main__':
    s = Solution()
    print s.movingCount(9,12,11)
    

本代码尚需优化，行数列数设置40+，就会报运行时错误，有心者可以谷歌，解决方案暂时不展示啦。过牛客网测试用例没问题。

更多精彩内容