Python实现机器人运动范围计算：回溯算法详解

何川

发布时间：2026-10-13| 5人浏览过

原创

本文介绍如何使用Python解决机器人运动范围问题。给定m行n列的方格和阈值k，机器人从(0,0)出发，仅能进入行坐标和列坐标数位之和小于等于k的格子。通过回溯算法递归探索四个相邻方向，统计可达格子总数。文章包含完整代码实现及逻辑解析，适用于算法学习与面试准备。

机器人运动范围问题概述

机器人运动范围的Python实现方案如下：

问题描述：存在一个m行n列的方格矩阵。机器人从坐标(0,0)的位置开始移动，每次可以向左、右、上、下四个方向移动一格。限制条件是机器人不能进入行坐标和列坐标的数位之和大于k的格子。

举例说明：当阈值k为18时，机器人可以进入坐标为(35,37)的格子，因为3+5+3+7=18，满足条件；但机器人不能进入坐标为(35,38)的格子，因为3+5+3+8=19，超过了阈值k。请问在该规则下，机器人总共能够到达多少个格子？

回溯算法核心逻辑

解决方案采用回溯算法。

算法逻辑：在尝试进入坐标(i,j)时，首先检查该坐标的数位之和是否满足条件。如果满足，则继续判断其上下左右四个相邻格子是否可达。

具体代码实现如下：

Python代码实现


# -*- coding:utf-8 -*-
class Solution:
 def movingCount(self, threshold, rows, cols):
  # write code here
  matrix = [[True for i in range(cols)] for j in range(rows)]
  result = self.findgrid(threshold, rows, cols, matrix, 0, 0)
  return result
 
 def judge(self, threshold, i, j):
  if sum(map(int,str(i)+str(j))) <= threshold:
   return True
  else:
   return False
  
 def findgrid(self, threshold, rows, cols, matrix, i, j):
  count = 0
  if i < rows and i>=0 and j<cols and j>=0 and self.judge(threshold, i, j) and matrix[i][j]:
   matrix[i][j] = False
   count = 1+ self.findgrid(threshold, rows, cols, matrix, i-1, j) \
     + self.findgrid(threshold, rows, cols, matrix, i+1, j) \
     + self.findgrid(threshold, rows, cols, matrix, i, j-1) \
     + self.findgrid(threshold, rows, cols, matrix, i, j+1)
  return count

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。