青岛市黄岛区网站建设,沈阳网站公司哪个好,工布江达网站建设,广州物流网站开发面试题13. 机器人的运动范围
难度#xff1a;middle\color{orange}{middle}middle 题目描述
地上有一个 mmm 行 nnn 列的方格#xff0c;从坐标 [0,0][0,0][0,0] 到坐标 [m−1,n−1][m-1,n-1][m−1,n−1] 。一个机器人从坐标 [0,0][0, 0][0,0] 的格子开始移动#xff0c;它…面试题13. 机器人的运动范围
难度middle\color{orange}{middle}middle 题目描述
地上有一个 mmm 行 nnn 列的方格从坐标 [0,0][0,0][0,0] 到坐标 [m−1,n−1][m-1,n-1][m−1,n−1] 。一个机器人从坐标 [0,0][0, 0][0,0] 的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于 kkk 的格子。例如当 kkk 为 18 时机器人能够进入方格 [35, 37] 因为 353718 。但它不能进入方格 [35, 38]因为 353819。请问该机器人能够到达多少个格子
示例 1
输入m 2, n 3, k 1
输出3示例 2
输入m 3, n 1, k 0
输出1提示
1n,m1001 n,m 1001n,m1000k200 k 200k20 算法
(BFS)
这是一个典型的宽度优先搜索问题我们从 (0, 0) 点开始每次朝上下左右四个方向扩展新的节点即可。
扩展时需要注意新的节点需要满足如下条件
之前没有遍历过这个可以用一个 bool 数组来判断没有走出边界横纵坐标的各位数字之和小于 k
最后答案就是所有遍历过的合法的节点个数。
复杂度分析 时间复杂度每个节点最多只会入队一次所以时间复杂度不会超过方格中的节点个数。最坏情况下会遍历方格中的所有点所以时间复杂度就是 O(nm)O(nm)O(nm) 空间复杂度 : O(n)O(n)O(n)
C 代码
class Solution {
public:// 求单个数字的各个位数之和int get_single_num(int x) {int s 0;while (x) {s x % 10;x / 10;}return s;}//求一个方格的坐标位数之和int get_sum(pairint, int p) {return get_single_num(p.first) get_single_num(p.second);}int movingCount(int m, int n, int k) {//m 行 n 列 threshhold - kif (!k) return 1;if (!m || !n) return 0;int res 0;vectorvectorbool st(m, vectorbool(n));queuepairint, int q;q.push({0, 0});int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};while (q.size()) {auto t q.front();q.pop();if (get_sum(t) k || st[t.first][t.second]) continue;res ;st[t.first][t.second] true;for (int i 0; i 4; i ) {int x t.first dx[i], y t.second dy[i];if (x 0 x m y 0 y n)q.push({x, y});}}return res;}
};
