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$.