It can take a few tries. Sometimes you'll exit a room to the east, but have to go north to get back. That's not usually immediately obvious, and can mess up your maps.
Source: just played through Trinity for the first time since I was a kid.
My cousin and I tried making a map of the maze by dropping items in each room. We got some parts mapped out reliably, but it was still a long process that ended up with a few questionable paths