赞
踩
地上有一个m行n列的方格,一个机器人从坐标(0,0)的格子开始移动,它每次可以向上下左右移动一个格子,但不能进入行坐标和列坐标的位数之和大于k的格子,请问机器人能够到达多少个格子
- #include <vector> // 包含vector头文件
- #include <queue> // 包含queue头文件
-
- class Solution { // 定义解决方案类
- private:
- int getSum(int x, int y) { // 计算坐标数位之和
- int sum = 0; // 初始化和为0
- while (x > 0) { // 处理x坐标
- sum += x % 10; // 加上个位数
- x /= 10; // 去掉个位数
- }
- while (y > 0) { // 处理y坐标
- sum += y % 10; // 加上个位数
- y /= 10; // 去掉个位数
- }
- return sum; // 返回数位之和
- }
-
- public:
- int movingCount(int m, int n, int k) { // 计算可到达的格子数
- if (k < 0) return 0; // 如果k小于0,无法移动
-
- std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false)); // 记录已访问的格子
- std::queue<std::pair<int, int>> q; // 用于BFS的队列
- int count = 0; // 可到达的格子数
-
- q.push({0, 0}); // 起始点加入队列
- visited[0][0] = true; // 标记起始点为已访问
-
- int dx[4] = {-1, 1, 0, 0}; // x方向的移动
- int dy[4] = {0, 0, -1, 1}; // y方向的移动
-
- while (!q.empty()) { // BFS主循环
- auto [x, y] = q.front(); // 获取当前格子坐标
- q.pop(); // 从队列中移除
- count++; // 增加可到达的格子数
-
- for (int i = 0; i < 4; i++) { // 尝试四个方向的移动
- int nx = x + dx[i], ny = y + dy[i]; // 计算新坐标
- if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && getSum(nx, ny) <= k) { // 检查新坐标是否有效
- q.push({nx, ny}); // 将新坐标加入队列
- visited[nx][ny] = true; // 标记新坐标为已访问
- }
- }
- }
-
- return count; // 返回可到达的格子数
- }
- };
这个实现使用了广度优先搜索(BFS)算法来解决问题。以下是主要的设计思路:
Solution
类,其中包含两个主要函数:
getSum
: 这是一个私有辅助函数,用于计算坐标的数位之和。movingCount
: 这是公共接口函数,用于计算机器人能够到达的格子数量。movingCount
函数中:
visited
来记录已经访问过的格子。q
来进行BFS。这个算法的时间复杂度为O(mn),其中m和n分别是网格的行数和列数。空间复杂度也是O(mn),主要用于存储visited数组和BFS队列。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。