navigating every spot of a room
I would walk along the walls to get a contour. Roomba seems to measure reflection time of its IR sensors for this, though this requires high accuracy: a signal sent from 15cm from the wall returns in 1ns.  

When you have the contours you can use a floodfill algorithm to walk the room. This will account for any obstacles or concave contour of the room.

A recursive floodfill isn't very difficult to write if you have a bitmap representation of the room: You call Floodfill(Pt), where Pt is for instance the topleft corner. Floodfill moves you there, and checks if you've been there. If you have, finish. Otherwise, set a flag that you've been at that location and recursively call Floodfill() for all 8 adjacent points. That's all.

If your first direction is east that will walk the robot east until it hits the wall, upon which it goes back and tries the second direction, e.g. south. There it tries east again, as its first direction, and so will walk again from the west wall to the east wall on the next row.

Notice that this is somewhat less efficient than an electronic floodfill, like used by GPUs, because when backtracking the robot has to physically move to its previous point.