While legged robots are well suited to navigating complex three-dimensional (3-D) environments, their practical applicability is still hampered by the time taken to plan manoeuvres to traverse these challenging environments. We present contact dynamic roadmaps (CDRM), which extend dynamic roadmaps with contact information. The CDRM is precomputed offline to generate a discretized mapping from each leg's workspace to its configuration space, and then adapted online to the environment to rapidly identify collision-free foothold positions. The concept behind this is to perform the expensive foothold candidate generation and collision checking phases offline and store the data for use in the online planner. The CDRM is coupled with a rapidly-exploring random tree planner to generate acyclic full-body motion plans in complex 3-D environments. The performance of the approach is validated and compared in simulation in a wide variety of scenarios that require full-body planning to successfully navigate.