建站平台和网站建设的区别,网站开发api中文手册chm,中文wordpress网站模板,wordpress当前页面id❓剑指 Offer 13. 机器人的运动范围
难度#xff1a;中等
地上有一个 m 行 n 列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff08;不能移动到方格外#xff09;…❓剑指 Offer 13. 机器人的运动范围
难度中等
地上有一个 m 行 n 列的方格从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如当 k 为18时机器人能够进入方格 [35, 37] 因为353718。但它不能进入方格 [35, 38]因为 353819。请问该机器人能够到达多少个格子
示例 1 输入m 2, n 3, k 1 输出3 示例 2 输入m 3, n 1, k 0 输出1 提示
1 n,m 1000 k 20
思路广度优先搜索
我们将行坐标和列坐标数位之和大于 k 的格子看作障碍物那么这道题就是一道很传统的搜索题目我们可以使用广度优先搜索或者深度优先搜索来解决它本文选择使用 广度优先搜索 的方法来讲解。
那么如何计算一个数的数位之和呢
我们只需要对数 x 每次对 10 取余就能知道数 x 的个位数是多少然后再将 x 除 10这个操作等价于将 x 的十进制数向右移一位删除个位数类似于二进制中的 右移运算符不断重复直到 x 为 0 时结束。
代码(C、Java)
C
class Solution {
private:int getsum(int x){int ans 0;while(x 0 ){ans x % 10;x / 10;}return ans;}
public:int movingCount(int m, int n, int k) {if(k 0) return 1;vectorpairint, int dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};queuepairint, int q;q.push(make_pair(0, 0));vectorvectorint visited(m, vectorint(n));visited[0][0] 1;int ans 1;while(!q.empty()){auto [x, y] q.front();q.pop();for(auto dir : dirs){int cur_x x dir.first, cur_y y dir.second;if(cur_x 0 || cur_x m || cur_y 0 || cur_y n || visited[cur_x][cur_y] || getsum(cur_x) getsum(cur_y) k) continue;q.push(make_pair(cur_x, cur_y));visited[cur_x][cur_y] 1;ans;}}return ans;}
};Java
class Solution {private int getsum(int x){int ans 0;while(x 0 ){ans x % 10;x / 10;}return ans;}public int movingCount(int m, int n, int k) {if(k 0) return 1;int[][] dirs {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};Queueint[] q new LinkedListint[]();q.offer(new int[]{0, 0});int[][] visited new int[m][n];visited[0][0] 1;int ans 1;while(!q.isEmpty()){int[] cell q.poll();for(int[] dir : dirs){int cur_x cell[0] dir[0], cur_y cell[1] dir[1];if(cur_x 0 || cur_x m || cur_y 0 || cur_y n || visited[cur_x][cur_y] 1 || getsum(cur_x) getsum(cur_y) k) continue;q.offer(new int[]{cur_x, cur_y});visited[cur_x][cur_y] 1;ans;}}return ans;}
}运行结果 复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn)其中 m 为方格的行数n 为方格的列数。考虑所有格子都能进入那么搜索的时候一个格子最多会被访问的次数为常数所以时间复杂度为 O ( 4 m n ) O ( m n ) O(4mn) O(mn) O(4mn)O(mn)。空间复杂度 O ( m n ) O(mn) O(mn)搜索的时候需要一个大小为 O ( m n ) O(mn) O(mn) 的标记结构用来标记每个格子是否被走过。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
