grid compression

Given some n by m grid, we want to convert it into a "compressed" representation. Example:

1 0 1 2 1
0 0 1 2 0
0 0 1 3 0
0 1 1 2 0
0 1 0 2 0

would be represented as:

Set(0, 0, 1)
Fill(1, 0, 1, 2, 0)
Fill(2, 0, 2, 3, 1)
Fill(2, 0, 2, 1, 2)

etc.

Of course there are sub-optimal solutions to this problem, and probably (I'm guessing) in some cases, multiple optimal solutions as well.
What's an algorithm that could solve this? And how fast is said algorithm? Better than O(n^2)?