Each cell of an $m \times n$ board is filled with some nonnegative integer. Two numbers in the filling are said to be adjacent if their cells share a common side. The filling is called a garden if it satisfies the following two conditions:
(i) The difference between any two adjacent numbers is either 0 or 1 .
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to 0 .

Determine the number of distinct gardens in terms of $m$ and $n$.
The numerical answer is $2^{m n}-1$. But we claim much more, by giving an explicit description of all gardens:
Let $S$ be any nonempty subset of the $m n$ cells. Suppose we fill each cell $\theta$ with the minimum (taxicab) distance from $\theta$ to some cell in $S$ (in particular, we write 0 if $\theta \in S$ ). Then
- This gives a garden, and
- All gardens are of this form.

Since there are $2^{m n}-1$ such nonempty subsets $S$, this would finish the problem. An example of a garden with $|S|=3$ is shown below.
$$
\left[\begin{array}{llllll}
2 & 1 & 2 & 1 & 0 & 1 \\
1 & 0 & 1 & 2 & 1 & 2 \\
1 & 1 & 2 & 3 & 2 & 3 \\
0 & 1 & 2 & 3 & 3 & 4
\end{array}\right]
$$

It is actually fairly easy to see that this procedure always gives a garden; so we focus our attention on showing that every garden is of this form.

Given a garden, note first that it has at least one cell with a zero in it - by considering the minimum number across the entire garden. Now let $S$ be the (thus nonempty) set of cells with a zero written in them. We contend that this works, i.e. the following sentence holds:
Claim - If a cell $\theta$ is labeled $d$, then the minimum distance from that cell to a cell in $S$ is $d$.

Proof. The proof is by induction on $d$, with $d=0$ being by definition. Now, consider any cell $\theta$ labeled $d \geq 1$. Every neighbor of $\theta$ has label at least $d-1$, so any path will necessarily take $d-1$ steps after leaving $\theta$. Conversely, there is some $d-1$ adjacent to $\theta$ by (ii). Stepping on this cell and using the minimal path (by induction hypothesis) gives us a path to a cell in $S$ with length exactly $d$. So the shortest path does indeed have distance $d$, as desired.