# Minimize Manhattan distance travel algorithm

I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$\begin{array}{|r|r|r|} \hline \hphantom{-}1 & -1 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array}$$

I know that the sum of each element of the matrix is zero.

And an operation $$f$$ which sums two elements of the matrix together and replaces both of them with this sum. In our example $$f( a_{1,1} a_{1,2} )$$ (where $$a_{r,c}$$ is the element of the matrix at row $$r$$ and column $$c$$) would lead to

$$\begin{array}{|r|r|r|} \hline \hphantom{-}0 & \hphantom{-}0 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array}$$

The cost of this operation is the Manhattan distance between the two points, in this case $$1$$.

Now, I want to find the moves that:

• make each element of the matrix go to $$0$$
• minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!

• What do you mean by "sums two elements"? Do you mean replacing the two elements with their sum? – Yuval Filmus Sep 27 '18 at 16:44
• What does (a1,1) mean? Do you mean the matrix element at (1,1)? What is a1? – D.W. Sep 27 '18 at 20:34
• @D.W. yes, with (a1,1) I meant the matrix element at (1,1). Sorry, I only write those on paper! – Frabetto Sep 28 '18 at 9:01
• @YuvalFilmus yes, replacing the two elements with their sum! – Frabetto Sep 28 '18 at 9:02
• I don't think replacing elements with their sum. Then [[0 1] [1 -2]] would not work. First move: [[0 2] [2 -2]]. Maybe just move one into another. Which satisfies your description. – rus9384 Sep 28 '18 at 22:58