<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:
    int check(vector<vector<int>>&obst, int x, int y, int nx, int ny){
        // int minx = min(x,nx), maxx = max(x,nx);
        // int miny = min(y,ny), maxy = max(y,ny);
        // for(int i = 0; i < obst.size(); i++){
        //     if(obst[i][0] >= minx && obst[i][0] <= maxx && obst[i][1] >= miny && obst[i][1] <= maxy) return (abs(x + obst[i][0]) + abs(y + obst[i][1]));
        // }
        // return 0;
        int minx = min(x, nx), maxx = max(x, nx);
        int miny = min(y, ny), maxy = max(y, ny);
        for (const auto& obs : obst) {
            if (obs[0] >= minx && obs[0] <= maxx && obs[1] >= miny && obs[1] <= maxy) {
                return (abs(x - obs[0]) + abs(y - obs[1]));
            }
        }
        return 0;
    }
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // queue<pair<char, pair<int,int>>>q;
        // q.push({'N',{0,0}});
        // int finx = 0, finy = 0;
        // int ind = 0;
        // while(!q.empty() && ind<commands.size()){
        //     char dir = q.front().first;
        //     int x = q.front().second.first, y = q.front().second.second;
        //     int command = commands[ind++];
            
            
        //     q.pop();
        //     if(dir == 'N'){
        //         if(command == -1){
        //             q.push({'E',{x,y}});
        //         }
        //         else if(command == -2){
        //             q.push({'W',{x,y}});
        //         }
        //         else{
        //             int newX = x, newY = y + command;
        //             int dist = check(obstacles, x, y, newX, newY);
        //             if(dist){
        //                 // cout<<"HI"<<" ";
        //                 q.push({dir,{newX, y + dist}});
        //             }
        //             else{
        //                 q.push({dir,{x,y}});
        //                 ind++;
        //             }
        //         }
        //     }
        //     else if(dir == 'S'){
        //         if(command == -1){
        //             q.push({'W',{x,y}});
        //         }
        //         else if(command == -2){
        //             q.push({'E',{x,y}});
        //         }
        //         else{
        //             int newX = x, newY = y - command;
        //             int dist = check(obstacles, x, y, newX, newY);
        //             if(dist){
        //                 q.push({dir,{newX, y - dist}});
        //             }
        //             else{
        //                 q.push({dir,{x,y}});
        //                 ind++;
        //             }
        //         }
        //     }
        //     else if(dir == 'E'){
        //         if(command == -1){
        //             q.push({'S',{x,y}});
        //         }
        //         else if(command == -2){
        //             q.push({'N',{x,y}});
        //         }
        //         else{
        //             int newX = x + command, newY = y;
        //             int dist = check(obstacles, x, y, newX, newY);
        //             if(dist){
        //                 q.push({dir,{x + dist, newY}});
        //             }
        //             else{
        //                 q.push({dir,{x,y}});
        //                 ind++;
        //             }
        //         }
        //     }
        //     else{
        //         if(command == -1){
        //             q.push({'N',{x,y}});
        //         }
        //         else if(command == -2){
        //             q.push({'S',{x,y}});
        //         }
        //         else{
        //             int newX = x - command, newY = y;
        //             int dist = check(obstacles, x, y, newX, newY);
        //             if(dist){
        //                 q.push({dir,{x - dist, newY}});
        //             }
        //             else{
        //                 q.push({dir,{x,y}});
        //                 ind++;
        //             }
        //         }
        //     }
            
        //     finx = x, finy = y;
        //     cout<<finx<<" "<<finy<<"\n";
        // }
        // finx = q.front().second.first, finy = q.front().second.second;
        // return finx*finx + finy*finy;
        queue<pair<char, pair<int, int>>> q;
        q.push({'N', {0, 0}});
        int ind = 0;
        char dir = 'N'; // initial direction
        int maxDist = 0;
        while (!q.empty() && ind < commands.size()) {
            auto current = q.front();
            q.pop();
            dir = current.first;
            int x = current.second.first, y = current.second.second;
            int command = commands[ind++];

            if (command == -1) { // Turn right
                if (dir == 'N') dir = 'E';
                else if (dir == 'E') dir = 'S';
                else if (dir == 'S') dir = 'W';
                else if (dir == 'W') dir = 'N';
                q.push({dir, {x, y}});
            } else if (command == -2) { // Turn left
                if (dir == 'N') dir = 'W';
                else if (dir == 'W') dir = 'S';
                else if (dir == 'S') dir = 'E';
                else if (dir == 'E') dir = 'N';
                q.push({dir, {x, y}});
            } else { // Move forward
                int newX = x, newY = y;
                if (dir == 'N') newY += command;
                else if (dir == 'E') newX += command;
                else if (dir == 'S') newY -= command;
                else if (dir == 'W') newX -= command;

                int dist = check(obstacles, x, y, newX, newY);
                if (dist > 0) {
                    // Obstacle detected, move up to just before the obstacle
                    if (dir == 'N') newY = y + dist - 1;
                    else if (dir == 'E') newX = x + dist - 1;
                    else if (dir == 'S') newY = y - dist + 1;
                    else if (dir == 'W') newX = x - dist + 1;
                }

                // Update final position and max distance
                maxDist = max(maxDist, newX * newX + newY * newY);
                q.push({dir, {newX, newY}});
            }
        }
        return maxDist;
    }
};
34021