2
#yyds干货盘点# 解决剑指offer：机器人的运动范围
source link: https://blog.51cto.com/u_15488507/5242773
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决剑指offer：机器人的运动范围
原创1.简述：
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
数据范围： 0 \le threshold \le 15 \0≤threshold≤15 ，1 \le rows,cols \le 100 \1≤rows,cols≤100
进阶：空间复杂度 O(nm) \O(nm) ，时间复杂度 O(nm) \O(nm)
1,2,3
0,1,3
10,1,100
[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的
5,10,10
2.代码实现：
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
//临时变量visited记录格子是否被访问过
boolean[][] visited = new boolean[rows][cols];
int res = 0;
//创建一个队列，保存的是访问到的格子坐标，是个二维数组
Queue<int[]> queue = new LinkedList<>();
//从左上角坐标[0,0]点开始访问，add方法表示把坐标
// 点加入到队列的队尾
queue.add(new int[]{0, 0});
while (queue.size() > 0) {
//这里的poll()函数表示的是移除队列头部元素，因为队列
// 是先进先出，从尾部添加，从头部移除
int[] x = queue.poll();
int i = x[0], j = x[1];
//i >= rows || j >= cols是边界条件的判断，threshold < sum(i, j)判断当前格子坐标是否
// 满足条件，visited[i][j]判断这个格子是否被访问过
if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j])
continue;
//标注这个格子被访问过
visited[i][j] = true;
res++;
//把当前格子右边格子的坐标加入到队列中
queue.add(new int[]{i + 1, j});
//把当前格子下边格子的坐标加入到队列中
queue.add(new int[]{i, j + 1});
}
return res;
}
//计算两个坐标数字的和
private int sum(int i, int j) {
int sum = 0;
//计算坐标i所有数字的和
while (i != 0) {
sum += i % 10;
i /= 10;
}
//计算坐标j所有数字的和
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum;
}
}
import java.util.Queue;
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
//临时变量visited记录格子是否被访问过
boolean[][] visited = new boolean[rows][cols];
int res = 0;
//创建一个队列，保存的是访问到的格子坐标，是个二维数组
Queue<int[]> queue = new LinkedList<>();
//从左上角坐标[0,0]点开始访问，add方法表示把坐标
// 点加入到队列的队尾
queue.add(new int[]{0, 0});
while (queue.size() > 0) {
//这里的poll()函数表示的是移除队列头部元素，因为队列
// 是先进先出，从尾部添加，从头部移除
int[] x = queue.poll();
int i = x[0], j = x[1];
//i >= rows || j >= cols是边界条件的判断，threshold < sum(i, j)判断当前格子坐标是否
// 满足条件，visited[i][j]判断这个格子是否被访问过
if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j])
continue;
//标注这个格子被访问过
visited[i][j] = true;
res++;
//把当前格子右边格子的坐标加入到队列中
queue.add(new int[]{i + 1, j});
//把当前格子下边格子的坐标加入到队列中
queue.add(new int[]{i, j + 1});
}
return res;
}
//计算两个坐标数字的和
private int sum(int i, int j) {
int sum = 0;
//计算坐标i所有数字的和
while (i != 0) {
sum += i % 10;
i /= 10;
}
//计算坐标j所有数字的和
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum;
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK