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)?

So, update -- it's 2025 now (Trump won again; kms)
Uh, check this out: https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm
Could probably extend this to solve this problem, methinks.