题解 | #机器人的运动范围#

深度优先搜索： 可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 

算法解析：
    递归参数： 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
    终止条件： 当 i，j 行列索引越界 或 si + sj 数位和超出目标值 k 或  当前元素已访问过 时，返回 0 ，代表不计入可达解。
    递推工作：
        标记当前单元格 ：将索引 (i, j) 存入辅助数组 res中，代表此单元格已被访问过。
        搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
回溯返回值： 返回辅助数组 res 的长度

图解：

Python版本

class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        def dfs(i, j, k):
            # 边界
            if not 0 <= i < rows&nbs***bsp;not 0 <= j < cols&nbs***bsp;(i, j) in res&nbs***bsp;(i % 10 + i // 10 + j % 10 + j // 10) > k:
                return 0
            # 将访问节点加入可访问集中
            res.add((i, j))
            # 因为从（0， 0）开始，所以只要向下走或向右走就行
            dfs(i+1, j, k)
            dfs(i, j+1, k)
        res = set()
        dfs(0, 0, threshold)
        return len(res)

时间复杂度 O(MN)： M N分别为矩阵的长度和宽度，最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)。
空间复杂度 O(MN) ： 最差情况下，res 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。

算法思想二：广度优先遍历BFS

解题思路：

BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。

算法解析：
    初始化： 将机器人初始点 (0, 0)(0,0) 加入队列 queue ；
    迭代终止条件： queue 为空。代表已遍历完所有可达解。
    迭代工作：
        单元格出队： 将队首单元格的 索引、数位和 弹出，作为当前搜索单元格。
        判断是否跳过： 若 行列索引越界 或  数位和超出目标值 k 或当前元素已访问过 时，执行 continue 。
        标记当前单元格 ：将单元格索引 (i, j) 存入 visited 中，代表此单元格 已被访问过 。
        单元格入队： 将当前元素的 下方、右方 单元格的 索引、数位和 加入 queue 。
返回值： 辅助数组 visited 的长度 len(visited) ，即可达解的数量。

图解：

代码展示：

JAVA版本

import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[][] visited = new boolean[rows][cols];
        int res = 0;
        Queue<int[]> queue= new LinkedList<int[]>();
        // 队列初始化
        queue.add(new int[] { 0, 0, 0, 0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= rows || j >= cols || threshold < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
}

复杂度分析：