A rectangular cell map representation and a neural dynamics based technique are proposed for real-time map building and complete coverage navigation (CCN) of a cleaning robot. The proposed model is compared with a triangular cell map based method proposed by Oh et al. (2004), which combined distance transform path planning, wall-following algorithm, and template based technique. Our method does not need any templates, even in unknown environments. A local map composed of rectangular cells is built through the proposed neural dynamics during CCN with restricted sensory information in unknown environments. The robot is able to dynamically build an accurate map of its immediate limited surroundings for its navigation. Comparison studies to triangular cell map based CCN approach show that the proposed model is capable of planning more reasonable and shorter coverage path in unknown environments