题目描述
地上有一个$ m$ 行和$ n $列的方格,横纵坐标范围分别是 $0∼m−1$ 和 $0∼n−1$。
一个机器人从坐标 $(0,0)$ 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于$ k$ 的格子。
请问该机器人能够达到多少个格子?
样例
输入:k=7, m=4, n=5
输出:20
算法1
dfs 深度优先搜索
算法思路:
- 从$(0,0)$开始搜索四个方向上的点是否满足题目要求(各位之和不大于k)
- 定义静态变量
res
用于记录答案 - 取一个数的各位之和见下方的
getSum()
方法 - 需要注意算过的点要记录一下,防止重复计算,我这里是用的
vis[][]
数组实现的
时间复杂度
$O(n * m)$
Java 代码
class Solution {
public static int res = 0;
public int movingCount(int threshold, int rows, int cols) {
boolean[][] vis = new boolean[rows][cols];
dfs(threshold, rows, cols, 0, 0, vis);
return res;
}
public void dfs(int threshold, int rows, int cols, int x, int y, boolean[][] vis) {
if (x >= 0 && x < rows && y >= 0 && y < cols && getSum(x) + getSum(y) <= threshold && !vis[x][y]) {
vis[x][y] = true;
res++;
dfs(threshold, rows, cols, x + 1, y, vis);
dfs(threshold, rows, cols, x, y + 1, vis);
dfs(threshold, rows, cols, x - 1, y, vis);
dfs(threshold, rows, cols, x, y - 1, vis);
}
}
private int getSum(int x) {
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
return res;
}
算法2
bfs 广度优先搜索
算法思路:
- 首选把$(0,0)$加入队列,然后进行循环,每次删掉队头,并把符合条件的四个方向的坐标加入队列
- 遍历过程中也需要标记已经计算过的坐标,避免重复计算
时间复杂度
$O(n * m)$
Java 代码
class Solution {
public static int res = 0;
public int movingCount(int threshold, int rows, int cols) {
if (rows == 0 || cols == 0) {
return 0;
}
boolean[][] vis = new boolean[rows][cols];
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(0, 0));
while (!queue.isEmpty()) {
Pair<Integer, Integer> point = queue.poll();
int x = point.getKey(), y = point.getValue();
if (vis[x][y] || (getSum(x) + getSum(y)) > threshold) {
continue;
}
res++;
vis[x][y] = true;
// 四个方向遍历
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx < rows && yy >= 0 && yy < cols) {
queue.push(new Pair<>(xx, yy));
}
}
}
return res;
}
private int getSum(int x) {
int sum = 0;
while (x != 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
}
class Pair<K, V> {
private final K key;
private final V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}