unless memory/disk usage is a constraint (it shouldn't be), track each tile.

Furthermore, definitely go with an object-orienteed model, each tile should have a x,y,z - special attribute, terrain type (including ocean), movement modifiers, etc.

FreeCiv has some (limited) stuff on this - their code is in C and they really only track the x,y (they create and throw away the z iirc).