Robot Problems

Source — https://leetcode.com/problems/robot-room-cleaner/

Points to remember

1. The robot needs to explore all cells. However ,we need to pick one direction from one point at a given moment and go fully with it. We use DFS to do so

DFS()
{
  mark the cell as visited in this dfs
  For all possible directions()
  {
     //make sure the robot can move and the next cell is unvisited
     dfs(with new position)
    //rotate the robot's direction
   }
//Add snippet to update the robot's position and orientation as per the API given below
}

2. In order to check out other directions , we need to adopt DFS on the given API by doing the following

// Moves backward one step while maintaining the orientation.
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();

The above snippet basically backtracks the robot and makes it go back to its previous cell (as per the API) when we exit the current recursion

class Solution {
public:
    set<pair<int,int> >vis;
  int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};    
    void goBack(Robot&obj)
    {
            obj.turnRight();
            obj.turnRight();
            obj.move();
            obj.turnRight();
            obj.turnRight();            
        
    }
    void func(int x,int y,Robot&obj,int dir)
    {
        
        vis.insert(make_pair(x,y));
        obj.clean();
        
        for(int i=0;i<4;i++)
        {
            int idx=(i+dir)%4;
            int newx=x+directions[idx][0];
            int newy=y+directions[idx][1];
            if(vis.find(make_pair(newx,newy))==vis.end()&&obj.move())
            {
                func(newx,newy,obj,idx);
                goBack(obj);
               
                
            }
             obj.turnRight();
            
        }
}
    void cleanRoom(Robot& robot) {
        /*
        if you hit an obstacle moveright again 
        */
        func(0,0,robot,2);
        
    }
};