剑指Offer13.机器人的运动范围 C++

1、题目描述

• 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
• 示例 1：
  输入：m = 2, n = 3, k = 1
  输出：3
• 示例 2：
  输入：m = 3, n = 1, k = 0
  输出：1

2、VS2019上运行

使用方法一：广度优先搜索BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;class Solution {// 计算 x 的数位之和int get(int x) {int res = 0;for (; x; x /= 10) {res += x % 10;}return res;}
public:int movingCount(int m, int n, int k) {if (!k) return 1;queue<pair<int, int> > Q;//队列Q用于存储待访问的格子数量，第一个表示横坐标，第二个表示纵坐标// 向右和向下的方向数组//以向右（x轴正方向）和向下（y轴正方向）移动为例。int dx[2] = { 0, 1 };int dy[2] = { 1, 0 };//创建一个二维矩阵 vis，用于记录矩阵中每个位置是否已经被访问过。//初始时，所有位置都被标记为未访问（0）。vector<vector<int> > vis(m, vector<int>(n, 0));//m行n列，全部元素设为0//向队列 Q 中插入一个整数对作为元素。这里是将 (0, 0) 作为起始位置插入到队列中Q.push(make_pair(0, 0));vis[0][0] = 1;//将矩阵 vis 中坐标 (0, 0) 的元素设置为 1，表示该位置已被访问。int ans = 1;//变量 ans 用于记录满足特定条件的位置数量while (!Q.empty()) {// 取出队首的格子位置pair<int, int> front = Q.front();Q.pop();//将整数对 front 中的第一个元素和第二个元素分别存储到变量 x 和 y 中。也就是横坐标和纵坐标int x = front.first;int y = front.second;for (int i = 0; i < 2; ++i) {//循环遍历一个长度为2的数组，右和下int tx = dx[i] + x;//计算出下一个横坐标int ty = dy[i] + y;//计算下一个纵坐标// 判断下一个位置是否满足限制条件if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;Q.push(make_pair(tx, ty));//将计算出的下一个位置 (tx, ty) 插入到队列 Q 中，作为待访问的位置。vis[tx][ty] = 1;//该位置已访问ans++;}}return ans;}
};
int main() {int m = 2, n = 3, k = 1;Solution sol;int result = sol.movingCount(m, n, k);cout << result << endl;return 0;
}

3

3、解题思路

• 这段代码是解决一个问题：给定一个 m × n 的矩阵，矩阵中的每个位置代表一个格子。现在有一个机器人位于矩阵的左上角，机器人可以向右或向下移动，但不能移动到数位之和大于 k 的格子。请问，机器人能够到达多少个格子？
  具体的解决思路如下：
• 1.定义一个函数 get(int x)，用来计算数位之和。该函数通过循环将数字 x 每一位上的数字相加，返回数位之和。
• 2.在 movingCount 函数中，首先判断特殊情况，如果 k 为 0，表示没有限制，机器人可以到达任意位置，所以直接返回 1。
• 3.创建一个队列 Q，用于存储待访问的格子位置。队列中的每个元素都是一个整数对，表示格子的横坐标和纵坐标。
• 4.创建两个方向数组 dx 和 dy，用来表示向右和向下移动的偏移量。
• 5.创建一个二维矩阵 vis，用于记录矩阵中的每个位置是否已经被访问过。初始时，所有位置都被标记为未访问（0）。
• 6.将起始位置 (0, 0) 插入到队列 Q 中，并将矩阵 vis 中对应的位置设为已访问（1）。
• 7.定义变量 ans，初始值为 1，用于记录满足限制条件的位置数量。
• 8.使用广度优先搜索算法，不断遍历队列 Q 中的格子位置，进行下一步移动的判断。
• 9.在遍历的过程中，取出队列头部的格子位置，并将其分别存储到变量 x 和 y 中。
• 10.循环遍历方向数组 dx 和 dy 中的元素，分别计算出下一个位置的横坐标 tx 和纵坐标 ty。
• 11.判断下一个位置是否越界、已经访问过、或数位之和大于 k。如果满足其中任一条件，跳过当前循环，进行下一次循环。
• 12.如果下一个位置满足限制条件，将其插入队列 Q 中作为待访问的位置，并将矩阵 vis 中对应的位置设为已访问（1）。
• 13.将计数器 ans 递增，表示发现了一个满足条件的位置。
• 14.当队列 Q 中的格子位置全部遍历完毕时，返回 ans，即满足条件的位置数量。
• 整体思路是通过广度优先搜索算法遍历满足条件的位置，并使用一个队列和一个二维矩阵分别记录待访问的位置和已访问的位置。算法的时间复杂度为 O(m * n)，其中 m 和 n 分别表示矩阵的行数和列数。

4、get函数

  // 计算 x 的数位之和int get(int x) {int res = 0;for (; x; x /= 10) {res += x % 10;}return res;}

• 这段代码定义了一个名为 get 的函数，它的作用是计算一个整数 x 的数位之和。
• 首先，变量 res 被初始化为 0，用于保存数位之和的结果。
• 然后，通过一个 for 循环，循环的条件是 x 不为0，循环体内执行 x = x / 10，即将 x 除以 10，这样可以实现依次取 x 的个位、十位、百位等。
• 在每次循环中，通过 x % 10 取出 x 的个位数，然后将它加到 res 变量上。
• 最后，当循环结束时，函数返回 res，即计算得到的数位之和。
• 例如，如果 x 的值为 12345，那么这个函数将返回的数位之和为 1 + 2 + 3 + 4 + 5 = 15。

5、queue<pair<int, int> > Q

• 这行代码声明了一个名为 Q 的队列变量，用于存储格子的位置信息。
• Q 是一个队列，每个队列元素都是一个二维坐标的整数对，表示矩阵中的某个格子的位置。
• pair<int, int> 表示一个这样的二维坐标对，其中第一个整数表示横坐标，第二个整数表示纵坐标。
• 这样定义的队列 Q 可以用来保存待访问的格子位置，通常在广度优先搜索算法中会使用队列来实现。通过队列的先进先出特性，可以实现按照一定顺序逐步处理格子位置，从而完成搜索或遍历操作。

6、 vector<vector > vis(m, vector(n, 0));

• 这行代码声明了一个二维矩阵变量 vis，用于记录矩阵中每个位置的访问状态。
• vis 是一个二维的 vector，其中第一维表示矩阵的行数 m，第二维表示矩阵的列数 n。这样定义的二维矩阵 vis 有 m 行、n 列。
• vector<int>(n, 0) ，为每一行创建一个内部向量，创建一个包含 n 个元素的整数型向量，并将每个元素的初始值设置为0。这样创建的向量将被用作矩阵 vis 的每一行，用于表示对应位置的访问状态。
• 在 vector<int>(n, 0) 中，vector<int> 表示创建一个整数型向量，(n, 0) 是一个构造函数的参数，指定了向量的大小为 n，且将每个元素初始化为0。最终得到的向量将作为矩阵 vis 的一行。
• 在该算法中，vis 矩阵用于记录矩阵中每个位置的访问状态。当一个位置被访问时，对应位置的值会被设置为1，表示已经访问过。这在广度优先搜索等算法中很常见，可以避免重复访问同一个位置。

7、for (int i = 0; i < 2; ++i) {}；

• 循环遍历一个长度为2的数组是为了考虑当前位置 (x, y) 的相邻位置。
• 在给定的代码中，循环遍历的是长度为2的数组 [0, 1]。这是因为在二维矩阵中，我们通常只需要考虑横向和纵向的相邻位置，即上方、下方、左侧和右侧位置。这个数组的两个元素 [0, 1] 分别表示在横向和纵向上的移动方式。