关于java:offer-13-机器人的运动范围-深度优先遍历-DFS

机器人的静止范畴

办法一：深度优先遍历 dfs

回溯返回值：返回 1 + 右方搜寻的可达解总数 + 下方搜寻的可达解总数，代表从本单元格递归搜寻的可达解总数。
计算能走到多少个方格，那么就不能反复，上一个题 12. 矩阵中的门路（深度优先搜寻（DFS）），是利用先标 ’\0’ 后还原的办法失去，但此题须要计算方格数
这里须要建设一个数组记录，
具体点，建设一个与矩阵等大的二维布尔数组，！！留神布尔类型默认值是 false。

办法二：广度优先遍历 BFS

朝一个方向走到底再回退

DFS 是一条路始终走直到 false，递归 +boolean 数组
BFS 是右下一起走，直到走完，队列 +boolean 数组

  遍历到一个点，就把右，下的点都传到数组里。

本题往 LinkedList 外面传的是数组的模式，也就是队列元素是数组

传入四个参数，位数和也传入了

下面那个：xi，xj 就是 i、j 的个位十位数之和，一次只会渐变一个，要么 xi，要么 xj。

• 优化个位十位的和

  • 数位和的个别求法：

    个位：x%10,x 的模
    十位：x/10

  • 因为题中阐明了最大只到两位数，且机器一次只走一步，因而只有两种状况：

    i;j=1,2, 这样，11，12，这样，位和 x 只会减少 1,xi++，xj++
    i;i=19,20，这样，29,30 这样，位和 x 就会多缩小 8，xi-8,xj-8，

  • 因而能够优化为：

    (i+1)%10 = 0 ?xi=xi-8:xi=xi+1;