问题描述
|
1
2
3
4
|
地上有一个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)
