Actually you can fly in any direction. Just take the Shamal or AT-400, (no other planes, because Shamal and AT-400 works best) and fly in one direction, any direction, but it has to be a corner. Before that, make sure your fat and muscle is full coz you need to fly for about a total of 5 hours to get the map full of territories (178 territories total). You don't have to fly for 5 hours in one go, you can do it like me, 2 hours, 2 hours, 1 hour.
To go back to San Andreas, just drown yourself. Or you can fly back, (that takes about 15 minutes).
Remember, Shamal or AT-400, they can auto-pilot. So once you got your right direction, go do something else to past time. Play another console, watch television, anything.