The God Delusion

You are God, building the universe. While arranging the silicon crystals you run into a problem: aluminium impurities have stolen the silicon atoms' electrons, and the crystals are demanding their electrons back. Luckily you caught it early, so the crystals are still small. Even a god has little time to spare, so you must return every electron to its proper atom in the fewest possible moves.

There is only one way to move an electron: take an electron from an atom and slide it into a neighbouring atom that currently has none. One move is one such slide.

Model the crystal lattice as a planar rectangular grid in which every atom is connected to its four neighbours (up, down, left, right). For a grid of $h$ rows and $w$ columns there are $n = h \times w$ atoms, numbered $0$ to $n-1$. The atom in row $i$ and column $j$ (rows and columns are counted from $0$) has number $i \times w + j$.

The electrons are numbered $1$ to $n-1$, and exactly one atom has no electron (shown as $0$ in the grid). Your goal is to move each electron $k$ onto the atom with the same number $k$, leaving atom $0$ without an electron. Find the minimum number of moves needed.

The input consists of several test cases. The first line of each test case contains two integers $h$ and $w$ ($2 \le h, w \le 5$, $h \times w \le 10$). The next $h$ lines each contain $w$ integers giving the electron currently at that grid position; a $0$ marks the atom with no electron.

A line containing only 0 0 ends the input.

For each test case, print on one line the minimum number of moves required to return every electron to the atom with its own number.