leetcode 每日一题 874. 模拟行走机器人 c++模拟解法

简介: 简单来说就是机器人在一个矩阵上移动 我们要找到一个离原点的一个最大欧式距离的平方

 

题目

机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands :

-2 :向左转 90 度

-1 :向右转 90 度

1 <= x <= 9 :向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上,它将会停留在障碍物的前一个网格方块上,但仍然可以继续尝试进行该路线的其余部分。

返回从原点到机器人所有经过的路径点(坐标为整数)的最大欧式距离的平方。(即,如果距离为 5 ,则返回 25 )

 

注意:

北表示 +Y 方向。

东表示 +X 方向。

南表示 -Y 方向。

西表示 -X 方向。

 

示例 1:

输入:commands = [4,-1,3], obstacles = []

输出:25

解释:

机器人开始位于 (0, 0):

1. 向北移动 4 个单位,到达 (0, 4)

2. 右转

3. 向东移动 3 个单位,到达 (3, 4)

距离原点最远的是 (3, 4) ,距离为 32 + 42 = 25

示例 2:

输入:commands = [4,-1,4,-2,4], obstacles = [[2,4]]

输出:65

解释:机器人开始位于 (0, 0):

1. 向北移动 4 个单位,到达 (0, 4)

2. 右转

3. 向东移动 1 个单位,然后被位于 (2, 4) 的障碍物阻挡,机器人停在 (1, 4)

4. 左转

5. 向北走 4 个单位,到达 (1, 8)

距离原点最远的是 (1, 8) ,距离为 12 + 82 = 65

 

提示:

1 <= commands.length <= 104

commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].

0 <= obstacles.length <= 104

-3 * 104 <= xi, yi <= 3 * 104

答案保证小于 231

简单来说就是机器人在一个矩阵上移动 我们要找到一个离原点的一个最大欧式距离的平方

思路:模拟机器人每一步在二维矩阵上的移动

classSolution {
public:
introbotSim(vector<int>&commands, vector<vector<int>>&obstacles) {
vector<vector<int>>dxy={{0,1},{1,0},{0,-1},{-1,0}}; //先定义机器人移动的四个方向 intx=0,y=0,ans=0,di=0;            //初始化x,y当前节点的位置为0 ,0 ,ans欧式平法和 di为方向 set<pair<int,int>>obSet; //创建一个set集合方便后面的查询障碍物位置for(constauto&ob:obstacles)
    {
obSet.insert(make_pair(ob[0],ob[1]));        //进行遍历 将所有的障碍物添加进集合中    }
for(constauto&cmd :commands)  //进行遍历数组 然后移动     {
if(cmd==-1)                 //如果是-1表示向方向右转90度对应的就是1 0        {
di=(di+1)%4;
        }
elseif(cmd==-2)             //左转对应-1 0  注意di初始初始值为0 方向对应北方 就是0,1位置        {
di=(di+3)%4;
        }
else{
for(intk=0;k<cmd;k++)  //表示移动1到9  进行一格格移动              {
intnx=x+dxy[di][0];    //表示当前x位置不变intny=y+dxy[di][1];    //表示y的位置加一if(obSet.find(make_pair(nx,ny))==obSet.end())//判断新的节点是否有障碍物                {
x=nx;                                    //没有的话就就更新当前节点x yy=ny;
ans=max(ans,x*x+y*y);        //更新最大的值                }
else{break;}                    //如果有障碍就退出当前循环            }
        }
    }
returnans;  
    }
};

image.gif

本题中除了理解上的问题 。

还有涉及到的知识点有:

1. set<pair<int ,int>> 是哈希表的表现形式,存储了所有的障碍物的x y 坐标。方便后面的插入删除查找等相关的操作

2. obSet.insert(make_pair(ob[0], ob[1]))  insert()是一个标准库容器set的成员函数,用在set中插入新的元素 是把障碍物的坐标插入进去。 至于make_pair是将x y 作为一对插入进去。向ob[0] ob[1]分别表示x y 坐标。

那么有人说了那不写make_pair不也一样么 直接将元素插进去不行吗。注意我们用的是哈希表的操作,不是定义的容器   。

在C++中不能直接将两个变量插入到set或者其他容器中,需要将它们封装成一个单一对象,比如一个pair或者一个struct。所以在这种情况下,你需要使用std::make_pair(ob[0], ob[1])将两个坐标值封装成一个对(pair)。

如果你尝试直接将两个变量插入到set,比如:obSet.insert(ob[0], ob[1]),这在C++中是不能编译通过的,会因为参数个数不匹配而报错,因为insert()函数只能接受一个参数。

所以,要存储两个相关联的值(在这里为x坐标和y坐标),一个常见的做法是使用pair。然后你可以使用make_pair()函数来创建一个pair实例并插入到set中。这就是为什么我们需要使用make_pair()的原因。

如果还是不明白 这里是我写的这一个文章是关于c中学习的数组到c++中学的容器的区别数组与容器

3  obSet.find(make_pair(nx,ny))==obSet.end() 这个代码是检查位置nx ny 如果有这个位置,就是这个位置在范围内 那么find就返回一个指向这个项目迭代器 不存在的话就返回end()函数的值,就是返回这个函数的末尾。

在贴一个官方的解法

classSolution{
public:
//定义解决方案函数introbotSim(vector<int>&commands, vector<vector<int>>&obstacles){
//定义了机器人可以走的四个方向//从y轴的负方向(上)开始,然后按照逆时针顺序,分别为上、右、下、左intdirs[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
//这三行定义了机器人的初始位置(px, py)以及初始的面向方向d(起始为1,表示向右)intpx=0, py=0, d=1;
//用哈希表记录所有障碍物的坐标,注意这里通过一个映射将每个二维坐标映射到一个整数,方便哈希表存储unordered_set<int>mp;
for(auto&obstacle : obstacles) {
mp.emplace(obstacle[0]*60001+obstacle[1]);
        }
//res用于记录机器人从初始位置到达的最大欧氏距离intres=0;
//按照命令列表模拟机器人的移动for(intc : commands){
//如果收到的命令c是-2或者-1, 表示转向if(c<0){
//如果命令是-1,右转,如果命令是-2,左转//由于四个方向循环,所以使用取余运算确定确切的方向d+= (c==-1) ?1 : -1;
d%=4;
if(d<0){
d+=4;
                }
            } 
//如果命令是一个正数,那么就表示前进 else {
for(inti=0; i<c; i++){  //c步//在前进前检查前方是否是障碍物,如果是就停止前进if(mp.count((px+dirs[d][0]) *60001+py+dirs[d][1])){
break;
                    } 
//否则更新位置坐标px+=dirs[d][0];
py+=dirs[d][1];
//每走一步都检查是否更新了最大欧氏距离res=max(res, px*px+py*py);
                }
            }
        }
//返回最大欧氏距离returnres;
    }
};

image.gif

目录
相关文章
|
16天前
|
算法 C语言 容器
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(上)
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣
22 0
|
3天前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
3天前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
3天前
|
存储 算法 数据可视化
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
|
3天前
|
存储 算法 数据挖掘
高效搜索技巧:最小覆盖子串解法【力扣75题 python】
高效搜索技巧:最小覆盖子串解法【力扣75题 python】
|
3天前
|
存储 机器学习/深度学习 算法
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
|
4天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
|
15天前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
12 5
|
15天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
23 1
|
16天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
25 1