面试题13.机器人的运动范围

题目描述 (opens new window)

解题方案：

• 标签: dfs
• 整体思路： 从原点出发，沿着四个方向，本题中两个方向就好了，因为可行的区域在原点的右下方，不断拓展，将可到达并且满足坐标数位和不大于k的点加入到队列中，直到左右的可能到达的点被访问到。

算法流程：

• 递归参数：当前元素在矩阵中的索引i和j,是否被访问的标记，矩阵的行列长度
• 终止条件：
  • 行列的索引越界
  • 数位之和大于k
  • 已经被访问过
• 递推：
  • 标记当前元素已经被访问
  • 计算当前元素的下右两个方向的元素的数位和，并开启下层递归