欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer-机器人的运动范围

程序员文章站 2022-04-15 15:49:29
问题描述 问题分析: 回溯法,每次判断上下左右四个方向是否满足条件 python代码 ......

问题描述

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

 

问题分析:

回溯法,每次判断上下左右四个方向是否满足条件

 

python代码

# coding=utf-8
class solution(object):
    '''
    地上有一个m行n列的方格, 一个机器人从坐标(0,0)的格子开始移动,
    它每次可以向左,向右,向上,向下移动一格, 但不能进入行坐标和列坐标的位数
    之和大于k的格子, 例如:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18;
     但它不能进入方格(35,38),因为3 + 5+3+8 = 19.请问该机器人最多能到达多少个格子?
    '''

    def solve(self, m, n, k):
        is_visited_array = [[false] * n] * m
        count = self.solve_count(0,0,is_visited_array, m, n, k)

        return count

    def solve_count(self, row, col, is_visited_array, m, n, k):
        count = 0
        # print row,col

        if row >= 0 and col >= 0 and row < m and col < n and not is_visited_array[row][col] and self.is_sum(row, col, k) :
            # 雁过留声
            is_visited_array[row][col] = true
            # 上下左右统计
            count = 1 + self.solve_count(row - 1, col, is_visited_array, m, n, k) + self.solve_count(row, col - 1,
                                                                                                     is_visited_array,
                                                                                                     m, n, k) + \
                    self.solve_count(row + 1, col, is_visited_array, m, n, k) + self.solve_count(row, col + 1,
                                                                                                 is_visited_array, m, n,
                                                                                                 k)
        return count

    def is_sum(self, row, col, k):
        #         判断相加和是否符合规矩
        row_sum = 0
        col_sum = 0
        while row > 10:
            row_sum += row / 10
            row /= 10
        row_sum += row

        while col > 10:
            col_sum += col / 10
            col /= 10
        col_sum += col
        return false if row_sum + col_sum > k else true


if __name__ == '__main__':
    print solution().solve(35, 37,18)