LeetCode: 874. Walking Robot Simulation

LeetCode: 874. Walking Robot Simulation

题目描述

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

  • -2: turn left 90 degrees
  • -1: turn right 90 degrees
  • 1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.
The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1]).
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

解题思路

模拟机器人行走的过程,并记录到达的每个位置与原点的距离的最大值。

AC 代码

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<pair<int, int>> obset;

        for(int i = 0; i < obstacles.size(); ++i)
        {
            obset.insert({obstacles[i][0], obstacles[i][1]});
        }

        int dirs[][2] = {{0,1}, {1, 0}, {0, -1}, {-1, 0}};
        int north = 0, east = 1, south = 2, west = 3;
        int curDir = north;
        long long int ans = 0;
        pair<int, int> curPos{0,0};
        for(size_t i = 0; i < commands.size(); ++i)
        {
            if(commands[i] == -2)
            {
                --curDir;
                if(curDir == -1) curDir = 3;
            }
            else if(commands[i] == -1)
            {
                ++curDir;
                curDir %= 4;
            }
            else
            {        
                for(int j = 0; j < commands[i]; ++j)
                {
                    pair<int, int> nextPos;
                    nextPos.first = curPos.first + dirs[curDir][0];
                    nextPos.second = curPos.second + dirs[curDir][1];

                    if(obset.find(nextPos) != obset.end())
                    {
                        break;
                    }
                    curPos = nextPos;
                }
                long long int len = (long long)curPos.first*(long long)curPos.first +
                               (long long)curPos.second*(long long)curPos.second;

                if(len > ans) 
                {
                    ans = len;
                }
            }
        }

        return ans;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
07-24 12:30
湘潭大学 营销
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务