题目描述
地上有一个 m行和 n列的方格,横纵坐标范围分别是 0∼m−1和 0∼n−1。
一个机器人从坐标 (0,0)的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k的格子。
请问该机器人能够达到多少个格子?
注意:
0<=m<=50
0<=n<=50
0<=k<=100
样例1
输入:k=7, m=4, n=5
输出:20
样例2
输入:k=18, m=40, n=40
输出:1484
解释:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。
但是,它不能进入方格(35,38),因为3+5+3+8 = 19。
算法1
DFS搜索
深度优先搜索,递归实现
时间复杂度
$O(n*m)$
Java 代码
class Solution {
private int ans = 1;
private int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
public int movingCount(int threshold, int rows, int cols) {
if (rows == 0 || cols == 0) {
return 0;
}
boolean[][] vis = new boolean[rows][cols];
vis[0][0] = true;
dfs(threshold, rows, cols, 0, 0, vis);
return ans;
}
private void dfs(int threshold, int rows, int cols, int x, int y, boolean[][] vis) {
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 && (getSum(xx, yy) <= threshold) && !vis[xx][yy]) {
ans ++;
vis[xx][yy] = true;
dfs(threshold, rows, cols, xx, yy, vis);
}
}
}
private int getSum(int x, int y) {
int sum = 0;
while (x != 0) {
sum += x % 10;
x /= 10;
}
while (y != 0) {
sum += y % 10;
y /= 10;
}
return sum;
}
}
算法2
BFS搜索
bfs广度优先搜索,队列实现
时间复杂度
$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 K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}