思路及解答DFS（深度优先搜索）

深度优先搜索算法，也就是 DFS ,⾸先需要初始化数组，注意是 boolean 类型的⼆元数组。边初始化
边计算位数的和，判断如果⼤于等于阈值的话，就直接置为 true ，也就是已经被访问到（但是这⼀部分计⼊结果）。

然后遍历每⼀个元素，只要 i ， j 不在合法的索引范围或者是已经被访问过，都会直接返回
false 。

否则的话，可访问的数量 +1 ，并且递归遍历上下左右四个元素，返回最终的可访问的个数。

DFS 会优先同⼀个⽅向，⼀直⾛下去，不撞南墙不回头，直到条件不满⾜的时候，才会回头。回头之后，每次只会回头⼀步，往另外⼀个⽅向去，同样是⼀头扎进去。

假设有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：

java

public class Solution { public int movingCount(int threshold, int rows, int cols) { if (rows > 0 && cols > 0) { boolean[][] visited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // 如果⼤于阈值，设置已被访问过 visited[i][j] = ((getSum(i) + getSum(j)) > threshold); } } return getNum(visited, 0, 0, 0); } return 0; } // 获取可以被访问的个数 private int getNum(boolean[][] visited, int i, int j, int count) { if (i < 0 || j < 0 || i >= visited.length || j >= visited[0].length || visited[i][j]) { return count; } count++; visited[i][j] = true; count = getNum(visited, i, j + 1, count); count = getNum(visited, i, j - 1, count); count = getNum(visited, i + 1, j, count); count = getNum(visited, i - 1, j, count); return count; } // 计算位数之和 private int getSum(int num) { int result = 0; while (num > 0) { result = result + num % 10; num = num / 10; } return result; } }

• 时间复杂度：最坏的情况是将所有的格⼦都遍历⼀遍， O(m*n) 。
• 空间复杂度：借助了额外的空间保存是否被访问过，同样为O(m*n) 。

BFS（⼴度优先搜索）

⼴度优先搜索，也就是没进⾏⼀步，优先搜索当前点的各个⽅向上的点，不急着往下搜索，等搜索完当前点的各个⽅向的点，再依次把之前搜索的点，取出来，同样先搜索周边的点...

这样直到所有都被搜索完成。

同样有⼀个 4 x 4 的⽅格，从第⼀个开始遍历，假设遍历顺序是上，右，下，左，那么遍历的顺序如下：

在上⾯的过程图示中，我们可以发现，访问是有顺序的，每遍历⼀个新的⽅块，都会标⼀个顺序