@senthilramamurthy

I don't believe that is the answer.

Start in a clockwise pattern, any pattern is fine, top, right, left, bottom. Let's call this one cycle. For each cycle find the first un-visited position then traverse into it, then restart the cycle. The cycle will be searched in the same order every time. This will eventually visit all spaces in the room.

Your starting point will be 0,0. Use a hash map to keep track of visited positions. The hash will be the to point, and the value is the from point. In this manner, you have a way to backtrack. Make sure you increment accordingly like when traversing a 2d matrix and save it in the hash map. Any walls and cleaned spaces will also be saved in this hash map as visited.

The only scenario that your robot can get stuck is if it enters a space where there are 3 walls and 1 visited node. In that case, you need some logic to check that 4 spaces are already visited and escape it. You could use a queue and another hash map to keep track of un-visited spaces during your traversal. Remove the unvisited spaces from the queue as you traverse. Using both hash tables(visited and un-visited) and the queue, you can make an algorithm to go an un-visited space with the back tracking potential. Then restart your search cycle from there.

In this way, there is no need for a 2d matrix and the potential to back-track to clean spaces where there is only one way in and out. You can also modify the queue to use a stack, so you can back-track to the nearest space.