If you 'read' the cells like you'd read a book (left-to-right, top-to-bottom - or, frankly, any direction would work), you could do some primitive run-length encoding, coupled with something similar to kju's replacement suggestion. It's a small amount of processing, but it reduces transmit, and you could obviously preprocess the functions to save on computation.
E.g., a simple grid, as in the right one would normally be represented as such (81 characters):
BBBBBBBBB
XXXBBXXXX
XXXXBBXXX
XXXXBBXXX
XXXXXRRRX
XXXXXXRRX
XXXXXXRRX
XXXXXXRRX
RRRRRRRRR
But can now be represented as this (36 characters):
10B3X2B8X2B7X2B9X3R7X2R7X2R7X2R1X10R
Which is, obviously, far shorter, and fits in one standard string... which makes sync'ing for JIP people painless
Obviously, the 'compression ratio' will vary depending on the individual grid... but given the nature of progressively taking regions (i.e. taking joined up regions), it'd be a very, very rare case in which the compressed string was much more than half the data length of the original.
Oh, as one final point, if you do try and implement this... it may pay to try and log the efficiency of such an algorithm in the four main reading directions (R-L, L-R, T-B, B-T), just to see which produces the best compression ratio for the way the game ends up being played!