C++ :: Compress 2 Way Sideways Scrolling Shooter?

You are programming a sideways scrolling shooter. This used 2D cell based maps that are very long (over 100,000 characters per row long, 24 rows of 40 characters on screen), and the only way you can get them to fit in memory is to compress each row of the map using run length encoding and to decompress each new column of the map on the right of the screen as the background moves from right to left. You maintain a list of pointers into the RLE data for each row of the screen. Columns that are scrolled off the left are discarded. This works very well and the game only just fits in the available memory. Suddenly the game designer decides that the game should also be able to scroll from left to right at any point, and for any duration. Stunned and dismayed, you explain to him that RLE compression only works in one direction, but he’s adamant. Figure out a way of doing what he wants without using much (no more that 1K of) extra memory. Explain the algorithm used for decompressing in both directions. (assume the RLE algorithm used is: a positive byte N followed by a byte B, indicates a run of N copies of B, a negative byte -N followed by N bytes indicates that those bytes should be copied directly. For example, the sequence 2,2,2,2,5,1,2,9,9,9,9,9 would be coded 4,2, -3,5,1,2, 5,9.)

how can I compress the information? My first thought was making a change to the RLE compression but i gave up on that thinking it wasn't possible.