网站建设情况总结,建造师网,上市公司网站分析,嘿呦一二呦1、题目描述
地上有一个m行n列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff08;不能移动到方格外#xff09;#xff0c;也不能进入行坐标和列坐标的数位之和大于k的…1、题目描述
地上有一个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
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;queuepairint, int Q;//队列Q用于存储待访问的格子数量第一个表示横坐标第二个表示纵坐标// 向右和向下的方向数组//以向右x轴正方向和向下y轴正方向移动为例。int dx[2] { 0, 1 };int dy[2] { 1, 0 };//创建一个二维矩阵 vis用于记录矩阵中每个位置是否已经被访问过。//初始时所有位置都被标记为未访问0。vectorvectorint vis(m, vectorint(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()) {// 取出队首的格子位置pairint, 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、queuepairint, int Q
这行代码声明了一个名为 Q 的队列变量用于存储格子的位置信息。Q 是一个队列每个队列元素都是一个二维坐标的整数对表示矩阵中的某个格子的位置。pairint, int 表示一个这样的二维坐标对其中第一个整数表示横坐标第二个整数表示纵坐标。这样定义的队列 Q 可以用来保存待访问的格子位置通常在广度优先搜索算法中会使用队列来实现。通过队列的先进先出特性可以实现按照一定顺序逐步处理格子位置从而完成搜索或遍历操作。
6、 vectorvector vis(m, vector(n, 0));
这行代码声明了一个二维矩阵变量 vis用于记录矩阵中每个位置的访问状态。vis 是一个二维的 vector其中第一维表示矩阵的行数 m第二维表示矩阵的列数 n。这样定义的二维矩阵 vis 有 m 行、n 列。vectorint(n, 0) 为每一行创建一个内部向量创建一个包含 n 个元素的整数型向量并将每个元素的初始值设置为0。这样创建的向量将被用作矩阵 vis 的每一行用于表示对应位置的访问状态。在 vectorint(n, 0) 中vectorint 表示创建一个整数型向量(n, 0) 是一个构造函数的参数指定了向量的大小为 n且将每个元素初始化为0。最终得到的向量将作为矩阵 vis 的一行。在该算法中vis 矩阵用于记录矩阵中每个位置的访问状态。当一个位置被访问时对应位置的值会被设置为1表示已经访问过。这在广度优先搜索等算法中很常见可以避免重复访问同一个位置。
7、for (int i 0; i 2; i) {}
循环遍历一个长度为2的数组是为了考虑当前位置 (x, y) 的相邻位置。在给定的代码中循环遍历的是长度为2的数组 [0, 1]。这是因为在二维矩阵中我们通常只需要考虑横向和纵向的相邻位置即上方、下方、左侧和右侧位置。这个数组的两个元素 [0, 1] 分别表示在横向和纵向上的移动方式。
