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

Solution: The numerical answer is $2^{mn}-1$.
But we claim much more, by giving an explicit description of all gardens:
\begin{quote}
  Let $S$ be any nonempty subset of the $mn$ 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
  \begin{itemize}
    \ii This gives a garden, and
    \ii All gardens are of this form.
  \end{itemize}
\end{quote}
Since there are $2^{mn}-1$ such nonempty subsets $S$,
this would finish the problem.
An example of a garden with $|S| = 3$ is shown below.
\[
  \begin{bmatrix}
    2 & 1 & 2 & 1 & \mathbf{\color{red}0} & 1 \\
    1 & \mathbf{\color{red}0} & 1 & 2 & 1 & 2 \\
    1 & 1 & 2 & 3 & 2 & 3 \\
    \mathbf{\color{red}0} & 1 & 2 & 3 & 3 & 4 \\
  \end{bmatrix}
\]

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:
\begin{claim*}
  If a cell $\theta$ is labeled $d$,
  then the minimum distance from that cell
  to a cell in $S$ is $d$.
\end{claim*}
\begin{proof}
  The proof is by induction on $d$, with $d = 0$ being by definition.
  Now, consider any cell $\theta$ labeled $d \ge 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 \emph{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 \emph{exactly} $d$.
  So the shortest path does indeed have distance $d$, as desired.
\end{proof}