这道题既可以用 DFS,也可以用 BFS
方法一:DFS 深度优先搜索
DFS(Depth First Search,深度优先搜索),特点是“一条道走到黑”、“不撞南墙不回头”,一般用「递归」实现(即栈)。
DFS 做法与【剑指 Offer 12. 矩阵中的路径】基本上一样,大框架不用动,只需要稍作修改即可。两道题目的不同点主要有:
- 起点:12 题需要枚举所有起点;而本题给定了起点,无需枚举。
- 状态重置:12 题需要进行重置;而本题不需要,不符合条件的格子不会进入,符合条件的格子访问后不能重置,否则会重复访问从而出错。
- 目的:12 题的目的是找出是否存在路径;本题的目的是统计符合条件的格子的个数。
时空复杂度
- 时间复杂度:$O(rows*cols)$
- 空间复杂度:$O(rows*cols)$
Java 代码
class Solution {
// 这里为了方便,把变量提到成员变量了,不然方法参数列表太长了
int ans = 0;
int threshold, rows, cols;
boolean[][] visited;
/**
* 方法一:DFS
* 时间复杂度:O(rows*cols)
* 空间复杂度:O(rows*cols)
*/
public int movingCount(int threshold, int rows, int cols) {
this.threshold = threshold;
this.rows = rows;
this.cols = cols;
this.visited = new boolean[rows][cols];
// 起点为 (0,0)
dfs(0, 0);
return ans;
}
// 从坐标 (i,j) 出发搜索符合条件的格子
public void dfs(int i, int j) {
// 如果当前格子不能进入,提前结束
if (!canEnter(i, j)) {
return;
}
// 否则,当前格子可以进入,答案+1
ans++;
// 将当前位置标记已访问
visited[i][j] = true;
// 四个方向
int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
// 尝试从当前位置继续向四个方向走
for (int[] direction : directions) {
// 新格子的坐标
int newi = i + direction[0], newj = j + direction[1];
// 从这个格子开始继续查找与之相邻的其他格子
dfs(newi, newj);
}
// 与前一题搜索字符串不同,此题不需要回溯,也就不需要状态重置,否则会出错
}
// 判断坐标为 (i,j) 的格子能否进入
public boolean canEnter(int i, int j) {
if (i >= 0 && i < rows && j >= 0 && j < cols && !visited[i][j] && digitSum(i) + digitSum(j) <= threshold) {
return true;
}
return false;
}
// 计算一个整数的数位之和
public int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}
方法二:BFS 广度优先搜索
BFS(Breadth First Search,广度优先搜索),类似于“在水中扔一块石头的涟漪”,从起点开始一层一层地向外扩展。一般用「队列」实现。
从起点开始,首先将起点入队,查看其周围一圈的邻居,如果符合也入队。
如此不断地出队并查看其邻居,并将符合条件的邻居入队,直到队列为空。
时空复杂度
- 时间复杂度:$O(rows*cols)$
- 空间复杂度:$O(rows*cols)$
Java 代码
class Solution {
/**
* BFS
* 时间复杂度:O(rows*cols)
* 空间复杂度:O(rows*cols)
*/
public int movingCount(int threshold, int rows, int cols) {
if (rows == 0 || cols == 0) {
return 0;
}
// 记录已访问过的格子
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
// 将起点入队
queue.offer(new int[] { 0, 0 });
// 将起点标记已访问
visited[0][0] = true;
// 起点必可到达,所以 ans 初始是 1
int ans = 1;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int i = cell[0], j = cell[1];
// 尝试当前格子的邻居
for (int[] direction : directions) {
int newi = i + direction[0], newj = j + direction[1];
// 如果当前格子的邻居也可以进入,则将邻居格子也入队
if (canEnter(threshold, rows, cols, newi, newj, visited)) {
queue.offer(new int[] { newi, newj });
visited[newi][newj] = true;
ans++;
}
}
}
return ans;
}
// 判断坐标为 (i,j) 的格子能否进入
public boolean canEnter(int threshold, int rows, int cols, int i, int j, boolean[][] visited) {
if (i >= 0 && i < rows && j >= 0 && j < cols && !visited[i][j] && digitSum(i) + digitSum(j) <= threshold) {
return true;
}
return false;
}
// 计算一个整数的数位之和
public int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}