前言

机器人的运动范围仍然和前一篇的寻找矩阵路径相似，都是在一个给定的网格内搜索问题的解，因此思路大体一致，还是利用回溯法来进行求解。

题目(机器人的运动范围)

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

解题思路

虽然本题不是给定一个矩阵进行搜索，但是它给定了可以搜寻的网格边界，因此还是类似矩阵搜索问题解的办法。
首先本题进入格子的条件基本和前一篇相似，只是字符串可以匹配换成了行坐标和列坐标的数位之和小于等于 k。然后，机器人每进入一个格子之后，它可以继续向该格子的左、右、上、下移动一格，所以我们依然只需递归下去求解，并返回递归结束后的格子数即可。也就是说，能进入的格子总数=当前格子(1) + 来自上下左右递归后返回的计数。

算法实现

复杂度分析

时间复杂度

时间复杂度 O(rowsxcols)。

空间复杂度

建立了一个辅助空间布尔矩阵，空间复杂度为 O(rows*cols)。递归工作栈消耗 O(max(rows,cols))。

参考

<<剑指offer2>>