这是我参与11月更文挑战的第13天,活动详情查看:2021最后一次更文挑战
5911. 模拟行走机器人 II
给你一个在 XY 平面上的 width x height 的网格图,左下角 的格子为 (0, 0) ,右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一("North","East","South" 和 "West")。一个机器人 初始 在格子 (0, 0) ,方向为 "East" 。
机器人可以根据指令移动指定的 步数 。每一步,它可以执行以下操作。
沿着当前方向尝试 往前一步 。
如果机器人下一步将到达的格子 超出了边界 ,机器人会 逆时针 转 90 度,然后再尝试往前一步。
如果机器人完成了指令要求的移动步数,它将停止移动并等待下一个指令。
请你实现 Robot 类:
- Robot(int width, int height) 初始化一个 width x height 的网格图,机器人初始在 (0, 0) ,方向朝 "East" 。
- void move(int num) 给机器人下达前进 num 步的指令。
- int[] getPos() 返回机器人当前所处的格子位置,用一个长度为 2 的数组 [x, y] 表示。
- String getDir() 返回当前机器人的朝向,为 "North" ,"East" ,"South" 或者 "West" 。
示例 1:
输入:
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出:
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
解释:
Robot robot = new Robot(6, 3); // 初始化网格图,机器人在 (0, 0) ,朝东。
robot.move(2); // 机器人朝东移动 2 步,到达 (2, 0) ,并朝东。
robot.move(2); // 机器人朝东移动 2 步,到达 (4, 0) ,并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.move(2); // 朝东移动 1 步到达 (5, 0) ,并朝东。
// 下一步继续往东移动将出界,所以逆时针转变方向朝北。
// 然后,往北移动 1 步到达 (5, 1) ,并朝北。
robot.move(1); // 朝北移动 1 步到达 (5, 2) ,并朝 北 (不是朝西)。
robot.move(4); // 下一步继续往北移动将出界,所以逆时针转变方向朝西。
// 然后,移动 4 步到 (1, 2) ,并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"
复制代码
提示:
- 2 <= width, height <= 100
- 1 <= num <=
- move ,getPos 和 getDir 总共 调用次数不超过
次。
解题思路
模拟机器人在外圈的移动,使用x,y维护机器人当前所在的位置,每次移动时判断机器人是否会移出边界,如果会出界,就改变移动方向
- 当移动步数超出外圈周长时,说明这次移动会超过一圈,所以我们可以将其对外圈周长取模,来获取其实际移动的距离。如果取模的结果等于0的话,说明会跑回原点,但是可能存在特殊情况,就是起始位置的下一步就是边界点的情况,跑完一圈以后方向可能会改变,因此我们需要对取模结果进行判断,如果取模等于0,我们需要将结果置为外圈的长度。
代码
class Robot {
public:
int dir[4][2] = {{0, 1},
{1, 0},
{0, -1},
{-1, 0 }};
string name[4] = {"East", "North", "West", "South"};
int x=0,y=0,idx=0,round;
int row,col;
Robot(int width, int height) {
this->row=height;
this->col=width;
this->round=2*(height+width)-4;
}
bool is_valid(int x,int y){
return x>=0&&x<row&&y>=0&&y<col;
}
void move(int num) {
num%=round;
if(num==0) num=round;
for (int i = 0; i < num; ++i) {
int nx=x+dir[idx][0],ny=y+dir[idx][1];
if (!is_valid(nx,ny)){
idx++;
idx%=4;
}
x+=dir[idx][0],y+=dir[idx][1];
}
}
vector<int> getPos() {
return {y,x};
}
string getDir() {
return name[idx];
}
};
/**
* Your Robot object will be instantiated and called as such:
* Robot* obj = new Robot(width, height);
* obj->move(num);
* vector<int> param_2 = obj->getPos();
* string param_3 = obj->getDir();
*/
复制代码
近期评论