Trying to map a room with Arduino controlled bot

What you see above is a map of my room. The boxes in black are obstacles and the box in red is my bot.

Now I want my bot to go around the room, avoiding all obstacles, but at the same time, covering the entire floor. Think of it like the robot is painting the floor and it has to paint the entire floor avoiding all obstacles.

Now my first approach was to put 3 HC-SR ultrasonic sensors on 3 sides and listen to them in a sequence, deciding which path is best and then going there. But this method leaves out quite a lot of floor area uncovered.

So how can I cover the entire floor area here?
Presently I am working with Arduino UNO and HC-SR04 but wouldn't hesitate to throw my Pi3 or a few more sensors in there...-

Where are you storing the map info?

There's probably a lot of algorithms to cover the floor area. They are all described on Wikipedia and other sources.

I find the difficult part is navigation. Once you have detected a wall at a distance in front of the robot (my preferred distance is zero) then how does the robot know where it is so it can put that wall on the map?

There have been a lot of questions here over the years for indoor navigation. Very few have given us feedback to say if the suggestions worked. You're dealing with obstacles so you can't easily put beacons on the walls for the robot to orient itself to those fixed points.