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

3次阅读

共计 592 个字符,预计需要花费 2 分钟才能阅读完成。

13. 机器人的静止范畴


留神是只能从坐标 [0,0] 开始走,所以不肯定能走到 [10,1] 这种中央。

思路一:深度优先遍历 dfs


计算能走到多少个方格,那么就不能 反复 ,上一个题 12. 矩阵中的门路(深度优先搜寻(DFS)),是利用先标 ’\0’ 后还原的办法失去,但此题须要计算方格数
这里须要建设一个数组记录,
具体点,建设一个与矩阵等大的二维布尔数组,!!留神布尔类型默认值是 false。


  • 优化个位十位的和

    • 数位和的个别求法:

       个位: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;
      
  • 官网:

思路二:广度优先遍历 BFS

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

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

  • 留神:

    • 这里有个 LinkedList<int[]>,往 Set 里传入的是一个数组的形式:!!

      queue.poll(new int[] {0,0,0,0,})
    • xi,xj 就是 i、j 的个位十位数之和,一次只会渐变一个,要么 xi,要么 xj。

操作:

正文完
 0