欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode: 874. Walking Robot Simulation

程序员文章站 2024-03-19 08:16:16
...

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;
    }
};

上一篇: UVA 514 stack

下一篇: