当前位置：首页 > news >正文

机器人运动范围检测 c++

news 2025/7/13 20:49:21

地上有一个m行n列的方格，一个机器人从坐标（0，0）的格子开始移动，它每次可以向上下左右移动一个格子，但不能进入行坐标和列坐标的位数之和大于k的格子，请问机器人能够到达多少个格子

#include <vector> // 包含vector头文件
#include <queue> // 包含queue头文件class Solution { // 定义解决方案类
private:int getSum(int x, int y) { // 计算坐标数位之和int sum = 0; // 初始化和为0while (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。
- 从(0,0)开始，将其加入队列并标记为已访问。
- 使用一个while循环进行BFS，每次从队列中取出一个格子，然后尝试向四个方向移动。
- 对于每个新的可能位置，我们检查：
  1. 是否在网格范围内
  2. 是否已经被访问过
  3. 数位之和是否不大于k
- 如果满足所有条件，我们将新位置加入队列，并标记为已访问。
- 每访问一个新的格子，我们就将计数器加1。
最后返回计数器的值，即为机器人能够到达的格子数量。