【剑指Offer】13. 机器人的运动范围原创

那今天我们看一下第13题，机器人的运动范围，他这道题是用DFS伸收问题解决的，他用一个回溯的方式。那核心思想是，嗯，先看一下这个题目描述，它是地上有MN。这样一个行列风格。机器人从零，零坐标点开始移动，每次只能上下左右移动一个方格。但是它不能进入以。位数相加之和大于K的格子，这个K，它比如说给定为18，那它这种。然后35 37相加出来的位数之和，它就18。它可以进入这样的，但是它不能进入，比如35 38这两位数之和相加是等于19的，它就已经超过了这个18的限制。那他为了每次只能进入一格，并且所访问过的格子不能再重新访问的话，他必须要用一个单独的。数组啊，布尔类型的，来记录一下我们所有访问过的格子。

那按照这种思路。那用这种回收的方式。去记录湾。然后再。归还他这个状态。然后我们开始做一下，它这个最主要的一个核心难点是要把这个12位数的。字符位，把它拆分成所有。以个位数这种类型相加。计算总和。第二就是这种。深度优先。我们先解决一下这个。创建它所有的标识位问题，要记录它所有访问过的格子。那就是必须要借助到这种布尔类型的数组。刷新一下页面。

一会儿可能会用到这个。累，先给他加点鸡蛋。这个包。这个布尔类型的数组。嗯，我们给它起名叫什么呢。就是visit。以访问过的这个数组。味类型是这个的话，它所有的。数组的个数是多少？他就用这个行列坐标来做吧。那这个行程列就是它现在所有需要的格子数。另外呢，我们最后是要回来他。

嗯，移动了多少个。格子，它能到达多少格子，不是移动了多少格。到达了多少个格子？我们给它一个核心的函数。那现在。有了它这个case。再加上他给我们这个行列。当然，我们还要记录自己的当前所未来位置的行列，以及我们整个标识位的数组。然后通过这些条件去。不断的。神兽雷加。我们现在给这个私有方法开始。

写一下。首先他这个。K是一个int型的。就把上面这个复制过来。还有这个int型的。陈坤。那我们现在要给他这个方法终止的话，他要有一个边界条件，那就首先。

一定要控制他这个当前所在这个行。是吧，要在所受控制范围之内，那就他如果。这个行小于零。或者是这个行。大于等于。我们这个给定的。好的程度。那就会出现问题。那列也是如此，它是如果小于零的话。我是大于这个给定范围。大于等于他给的，因为是下标从零开始的。这种情况下，我们就要返回一个零。就已经这地方没法走了，就数值无法累加。那另外一个条件就是说，呃，一个是他当前这个位置已经走过了。

呃，另外一个就是说，他当前这个位置是无法走的，因为它是不符合我们这个小于K值的要求。他如果是走过的话，那就需要看一下他这个当前位置的数组。那为了求它这个当前的坐标点的位置，那可以单独去先计算出来一下，比如说用这个我们来存一下。那就是当前的这个行列。成绩。看一下他当前这个是否。已经被标记为处。他如果已经是处的话，或者是。就已经。被标记过了，或者是被检查出来。

他不符合这个条件。那也就是说。要单独写个方法过来判断一下。这个check写的对不对，Check some？判断它的价格。先要给他这里面传一些参数就是。当前的这个K，以及我们的行列。他如果说。在这种情况下。那就不满足，可以累加进去的，那当然就要返回这个零先爆红是因为没有写这个检测方法，需要单独再实现一下这个。我们的这个方法，它返回的是布尔类型。再把这个。哎，名次靠谱了一下。

那现在他这个方法就是判断。检测大于K值。我们现在既然要做累加和，先给他出示一个sum条件进行用来累加的。那他要满足我们还能继续累加去给他拆分的话，就必须要保证我们当前的这个数值。这个数值它是不等于零的。那在这个前提下，我们才能一直的去给他缩小范围，他每次要去缩小的时候就必须要去。

做一个取鱼的操作。那这个属于，然后他要缩小范围，每次都要去。呃，把当前的这个数值缩小十倍。也就是说要。呃，去除一个十。那是这样的。是不是这样做？呃，他是。这样他是先出完这个，再等于这个。累加的话是这样。除十，除完十再付给他。嗯，这样写简写，但是可能会造成一个阅读不方便，但是这样写应该没问题。那就是没问题。

那这个列的处理也是一样的。要把这个列值取。然后再把这个列子每次都缩减。那他这样的话，就把这个sum求出来了。那这个时候上面要做个判断。还要满足这个。范围嘛。也就是说，如果它大于。我们给他一个值的话，它就会返回一个false，这样就会出现问题。他如果说啊是小于的，那就会到我们。True。给他返回一个正确的。看一下有没有问题。

这个就爆红。看下是哪里。II。嗯，没什么问题，继续往下写。嗯，他这个啊，这。上层，我们给的。这个参数有问题。应该写成两个零零坐要点。Visited。这样写。下面这个它应该是个数组。

这样就好了。然后。现在的问题就是。嗯，说要把这个当前的这个标识位。刚才已经是。刚才做了个什么事情，刚才在判断这个标识位，现在就要把这个标识位是作作为处的。另外呢，他要不断的去累加，那就要把当前的这个。Degree。给安排上。那他是个核心方法。里面要做的呢，就是。把这个上下左右说递归的情况放进去，首先它这个我们的K。还有我们的行和列。以及。当前我们要进行上下左右便利的节点，它如果是上节点的话，需要先这个。诶先用肉，这是对，就是减一。

然后裂是正常的。然后再给我们这个复制上。写后面好像不太方便看，先先下后边写吧。直接把这个前面的复制过来一下。对，加好友复制上。刚才那个是上。那我们先要做这个下。然后。江这边。来做这个主。

最后呢，来弄这个业务。它这个收尾要有个分号。理论上这样就。行得通。来提交看一下。诶，出现点问题。我看一下是哪儿出现了问题。实际输出是一，那说明这个。申收没有生效吧。看一下是哪里出了问题。啊，刚才出现的问题应该在这两个地方，一个就是说他。当前这个我们要访问的标识位的节点，它应该是呃行列当前行乘它所有的列值，再加上它当前的列值去计算这个注标点，而不是乘完之后呃忘记加了一个列子。

另外呢，他这个判断的时候。呃，要仔细看清他这个。当前这个行比较是跟他说的行比较，它列比较的时候，这个地方应该是列，应该是行，它的总列值。所以这个地方是出错的一个地方。嗯。