<p>A robot on an infinite XY-plane starts at point <code>(0, 0)</code> facing north. The robot receives an array of integers <code>commands</code>, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:</p>

<ul>
	<li><code>-2</code>: Turn left <code>90</code> degrees.</li>
	<li><code>-1</code>: Turn right <code>90</code> degrees.</li>
	<li><code>1 &lt;= k &lt;= 9</code>: Move forward <code>k</code> units, one unit at a time.</li>
</ul>

<p>Some of the grid squares are <code>obstacles</code>. The <code>i<sup>th</sup></code> obstacle is at grid point <code>obstacles[i] = (x<sub>i</sub>, y<sub>i</sub>)</code>. If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.</p>

<p>Return the <strong>maximum squared Euclidean distance</strong> that the robot reaches at any point in its path (i.e. if the distance is <code>5</code>, return <code>25</code>).</p>

<p><strong>Note:</strong></p>

<ul>
	<li>There can be an obstacle at <code>(0, 0)</code>. If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to <code>(0, 0)</code> due to the obstacle.</li>
	<li>North means +Y direction.</li>
	<li>East means +X direction.</li>
	<li>South means -Y direction.</li>
	<li>West means -X direction.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,3], obstacles = []</span></p>

<p><strong>Output:</strong> <span class="example-io">25</span></p>

<p><strong>Explanation: </strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 3 units to <code>(3, 4)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(3, 4)</code>, which squared is <code>3<sup>2</sup> + 4<sup>2 </sup>= 25</code> units away.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,4,-2,4], obstacles = [[2,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">65</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 1 unit and get blocked by the obstacle at <code>(2, 4)</code>, robot is at <code>(1, 4)</code>.</li>
	<li>Turn left.</li>
	<li>Move north 4 units to <code>(1, 8)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(1, 8)</code>, which squared is <code>1<sup>2</sup> + 8<sup>2</sup> = 65</code> units away.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [6,-1,-1,6], obstacles = [[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">36</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 6 units to <code>(0, 6)</code>.</li>
	<li>Turn right.</li>
	<li>Turn right.</li>
	<li>Move south 5 units and get blocked by the obstacle at <code>(0,0)</code>, robot is at <code>(0, 1)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(0, 6)</code>, which squared is <code>6<sup>2</sup> = 36</code> units away.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= commands.length &lt;= 10<sup>4</sup></code></li>
	<li><code>commands[i]</code> is either <code>-2</code>, <code>-1</code>, or an integer in the range <code>[1, 9]</code>.</li>
	<li><code>0 &lt;= obstacles.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-3 * 10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 3 * 10<sup>4</sup></code></li>
	<li>The answer is guaranteed to be less than <code>2<sup>31</sup></code>.</li>
</ul>

class Solution {
public:
    bool isObstacle (int pos_x, int pos_y, const std::map<int, std::vector<std::vector<int>>>& m_vec) {
        int max_euclid = pos_x * pos_x + pos_y * pos_y;

        if (m_vec.count(max_euclid) < 1)
            return false;

        for (const std::vector<int>& vec2d : m_vec.at(max_euclid)) {
            if (vec2d[0] == pos_x && vec2d[1] == pos_y)
                return true;
        }

        return false;
    }

    void step(int steps , const std::map<int, std::vector<std::vector<int>>>& m_vec) { //steps forward in the current direction
        int increment_x;
        int increment_y;

        switch (direction) {
            case 0:
                increment_x = 0;
                increment_y = 1;
                break;
            case 1:
                increment_x = 1;
                increment_y = 0;
                break;
            case 2:
                increment_x = 0;
                increment_y = -1;
                break;
            case 3:
                increment_x = -1;
                increment_y = 0;
                break;
        }
        
        for ( ; steps > 0; steps--) {        
            int next_x = pos_x + increment_x;
            int next_y = pos_y + increment_y;

            if (isObstacle(next_x, next_y, m_vec))
                return;

            pos_x = next_x;
            pos_y = next_y;
        }
    }

    void turnleft(bool leftright) { //left true
        if (leftright && direction == 0) { //turning left while north
            direction = 3; //west

            return;
        }
        
        if (!leftright && direction == 3) {//turning right while west
            direction = 0; //north

            return;
        }

        int dir = leftright ? -1 : 1;

        direction += dir;
    }
    
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int furthest = 0;

        std::map<int, std::vector<std::vector<int>>> m_vec;

        for (const std::vector<int>& vec : obstacles) {
            int max_euclid = vec[0] * vec[0] + vec[1] * vec[1];

            std::vector<std::vector<int>> index;

            if (m_vec[max_euclid].empty()) {
                index = {{vec[0], vec[1]}};
                m_vec[max_euclid] = index;
            }
            else {
                index = m_vec[max_euclid];
                index.push_back({{vec[0], vec[1]}});
                m_vec[max_euclid] = index;
            }
        }

        for (int k : commands) {
            if (k == -2) {
                turnleft(true); //turn left 90 degrees

                continue;
            }
            else if (k == -1) {
                turnleft(false); //turn right 90 degrees

                continue;
            }
            else
                step(k, m_vec); //move forward k units, one at a time.

            int dist = pos_x * pos_x + pos_y * pos_y;

            if (dist > furthest)
                furthest = dist;
        }
        
        return furthest;
    }

    int pos_x = 0;
    int pos_y = 0;
    int direction = 0; //north = 0, east = 1, south = 2, west = 3
};
53273